Selection Sort

Refer for animated applets :http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/heapSort/heapSort.html

Algorithm :
for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
→ invariant: a[k] smallest of a[i..n]
swap a[i,k]
→ invariant: a[1..i] in final position
end

java code :

void selectionSort(int[] a) {
int length = a.length;
for (int i = 0; i < length - 1; i++) {
int minPos = i;
for (int j = i + 1; j < length; j++) {
if (a[j] < a[minPos]) {
minPos = j;
}
}
// swapping min element position with i th position
int temp = a[minPos];
a[minPos] = a[i];
a[i] = temp;
}
}

Properties :
Not stable
O(1) extra space
Θ(n2) comparisons
Θ(n) swaps
Not adaptive


Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) comparisons (see arithmetic progression). Each of these scans requires one swap for n − 1 elements (the final element is already in place).


Among simple average-case Θ(n2) algorithms, selection sort almost always outperforms bubble sort and gnome sort, but is generally outperformed by insertion sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.

While selection sort is preferable to insertion sort in terms of number of writes (Θ(n) swaps versus Ο(n2) swaps), it almost always far exceeds (and never beats) the number of writes that cycle sort makes, as cycle sort is theoretically optimal in the number of writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory.