Transwiki:Selection sort implementations

From Wikibooks, the open-content textbooks collection

This page was transwikied from another project and needs to be adopted. This page needs to be moved to the main namespace, either as the main page of a book, or as a chapter of another book. After moving, please remove {{Tw-adopt}} from this page.

A Wikibookian suggests that this book or chapter be merged into Algorithm implementation/Sorting/Selection sort. Please discuss whether or not this merge should happen on the discussion page.

This article describes implementations of the selection sort sorting algorithm in a variety of real-world programming languages.

Contents 1 Core implementations 1.1 C 1.2 Ocaml 2 Additional implementations 2.1 BASIC 2.2 C# 2.3 Java

[edit] Core implementations

[edit] C

This is an implementation of the unstable variant:

int selectionSort(int data[], int count) {
        int i, j;
        int tmp;
        int minimum;
        for (i = 0; i < count - 1; i++) {
                minimum = i; /* current minimum */
                /* find the global minimum */
                for (j = i + 1; j < count; j++) {
                        if (data[minimum] > data[j]) {
                                /* new minimum */
                                minimum = j;
                        }
                }
                /* swap data[i] and data[minimum] */
                tmp = data[i];
                data[i] = data[minimum];
                data[minimum] = tmp;
        }
        return 0;
}

This is an implementation of the stable variant:

void selectionSort(int data[], int count)
{
	int i, j, m, mi;
        for (i = 0; i < count - 1; i++) {
        	/* find the minimum */
        	mi = i;
                for (j = i+1; j < count; j++) {
        	    if (data[j] < data[mi]) {
	        	mi = j;
        	    }
        	}
	        m = data[mi];
        	/* move elements to the right */
        	for (j = mi; j > i; j--) {
        	    data[j] = data[j-1];
        	}
        	data[i] = m;
        }
}

[edit] Ocaml

(* Gets the minimum element of the list *)
let rec min lst =
    match lst with
       x::[] -> x
     | (x::tl) -> let mintl = min tl in
                    if x < mintl then x else mintl;;

(* Removes a given element from the list *)
let rec remove(x,lst) =
    match lst with
       [] -> []
     | (y::tl) -> if x=y then tl else y::(remove(x,tl));;

(* Sorts a list by repeatedly extracting the minimum *)
let rec selectionSort(lst) =
    match lst with
       [] -> []
     | _  -> let m = min lst in m::(selectionSort(remove(m,lst)));;

[edit] Additional implementations

[edit] BASIC

For i = 1 To n - 1
   min = i
   For j = i + 1 To n
      If x(min) > x(j) Then
         min = j
      End If
   Next j
   temp = x(i)
   x(i) = x(min)
   x(min) = temp
Next i

[edit] C#

public void sortArray(int[] intArray)
{
  int min, temp;

  for( int i = 0; i < intArray.Length; i++ )
  {
    min = i;

    for( int j = i+1; j < intArray.Length; j++ )
    {
      if( intArray[j] < intArray[min] )
      {
        min = j;
      }
    }
    // swap the values
    temp = intArray[i];
    intArray[i] = intArray[min];
    intArray[min] = temp;
  }
}

//fixed by geneticlone

[edit] Java

An iterative implementation:

   public static void selectionSort (int[] numbers)
   {
      int min, temp;

      for (int index = 0; index < numbers.length-1; index++)
      {
         min = index;
         for (int scan = index+1; scan < numbers.length; scan++)
            if (numbers[scan] < numbers[min])
               min = scan;

         // Swap the values
         temp = numbers[min];
         numbers[min] = numbers[index];
         numbers[index] = temp;
      }
   }

A recursive implementation:

public static int findMin(int[] array, int index) {
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}

public static void selectionSort(int[] array) {
    selectionSort(array, 0);
}

public static void selectionSort(int[] array, int left) {
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}

public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}