Selection sort

Selection sort is a sort algorithm that works as follows:

find the smallest value in the list
switch it with the value in the first position
find the next smallest value in the list
switch it with the value in the second position
repeat until all values are in their proper places

An example:

original: 3 9 6 1 2
smallest is 1: 1 9 6 3 2
smallest is 2: 1 2 6 3 9
smallest is 3: 1 2 3 6 9
smallest is 6: 1 2 3 6 9

In Java, this might be written:

  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;

     }

  }

The naÃÂ¯ve algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case run-time of &Theta(n²), assuming that comparisons can be done in constant time. Thus it is outperformed on almost-sorted lists by insertion sort.

Heapsort greatly improves the basic algorithm by using a heap data structure to speed up finding and removing the lowest datum.

Implementations

Here is a simple implementation of selection sort in C (from pd lecture notes):

int find_min_index (float [], int, int);
void swap (float [], int, int);

/* selection sort on array v of n floats */

void selection_sort (float v[], int n) {
 int  i;


 /* for i from 0 to n-1, swap v[i] with the minimum

  * of the i'th to the n'th array elements

  */

 for (i=0; i
   swap (v, i, find_min_index (v, i, n));

} 

/* find the index of the minimum element of float array v from
* indices start to end

*/

int find_min_index (float v[], int start, int end) {
 int  i, mini;



 mini = start;

 for (i=start+1; i
   if (v[i] < v[mini]) mini = i;

 return mini;

}

/* swap i'th with j'th elements of float array v */
void swap (float v[], int i, int j) {
 float	t;


 t = v[i];

 v[i] = v[j];

 v[j] = t;

}

Here's another implementation in Python:

def selsort(iterable):
   """A simple selection-sort implementation in python"""

   seq = list(iterable)

   return [seq.pop(seq.index(min(seq))) for i in xrange(len(seq))]