Selection Sort

Idea

Selection Sort repeatedly picks the minimum (or maximum) from the unsorted part and places it at the end of the sorted part until done.

Algorithm

1. In each pass, find the minimum in the unsorted part and swap with its first element.
2. Repeat $n-1$ passes until fully sorted.

Pseudo-code:

for i = 0 to n-2:
    min = i
    for j = i+1 to n-1:
        if A[j] < A[min]:
            min = j
    if min != i:
        swap(A[i], A[min])

Code Implementation

void SelectSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;                     // the index of the smallest element
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[min]) min = j;  // found a smaller element
        }
        if (min != i) {                  // swap it into the end of the sorted part
            int tmp = A[i];
            A[i] = A[min];
            A[min] = tmp;
        }
    }
}

The Connection to Heap Sort

Simple selection sort has to scan the remaining part on every pass, so the number of comparisons is always $\frac{n(n-1)}{2}$. Heap sort uses the heap structure to bring the cost of “finding the smallest element” down from $O(n)$ to $O(\log n)$, which lowers the overall complexity from $O(n^2)$ to $O(n\log n)$.

Complexity

• Best/worst/avg: $O(n^2)$
• Space: $O(1)$
• Stability: unstable

Exercises

Exercise 1

Run selection sort on $A = [64, 25, 12, 22, 11]$ and show each pass.

Exercise 2

What are the time and space complexities of selection sort?