Selection sort

Selection sort is a sort algorithm that works as follows:

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

An example:\n* original: 3 9 6 1 2\n* smallest is 1: 1 9 6 3 2\n* smallest is 2: 1 2 6 3 9\n* smallest is 3: 1 2 3 6 9\n* smallest is 6: 1 2 3 6 9 In Java, this might be written:\n

\n   public static void selectionSort (int[] numbers)\n   {\n      int min, temp;
     for (int index = 0; index < numbers.length-1; index++)\n      {\n         min = index;\n         for (int scan = index+1; scan < numbers.length; scan++)\n            if (numbers[scan] < numbers[min])\n               min = scan;
        // Swap the values\n         temp = numbers[min];\n         numbers[min] = numbers[index];\n         numbers[index] = temp;\n      }\n   }\n

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):

\nint find_min_index (float [], int, int);\nvoid swap (float [], int, int);\n \n/* selection sort on array v of n floats */\n \nvoid selection_sort (float v[], int n) {\n  int  i;\n \n  /* for i from 0 to n-1, swap v[i] with the minimum\n   * of the i'th to the n'th array elements\n   */\n  for (i=0; i mini = start;\n  for (i=start+1; i

Here's another implementation in Python:

\ndef selsort(iterable):\n    """A simple selection-sort implementation in python"""\n    seq = list(iterable)\n    return [seq.pop(seq.index(min(seq))) for i in xrange(len(seq))]\n

\n\n Category:Sort algorithms