Selection sort

1. find the minimum value in the list
2. swap it with the value in the first position
3. find the minimum value amongst the remaining values
4. swap it with the value in the second position
5. repeat until the list is sorted

This 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. It is generally out performed by insertion sort.

Selection sort is not a stable sort.

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

Implementations of Selection Sort

Implementation in 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

Implementation in Java (iterative):
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;
}
}