Selection Sort

Selection sort is a simple sorting algorithm that repeatedly selects the minimum element from an unsorted portion of the array and swaps it with the first unsorted element. The algorithm maintains two subarrays: one that is sorted and one that is unsorted. The sorted subarray is built up from left to right, while the unsorted subarray is reduced from right to left.

Features

• Stable sorting algorithm
• In-place sorting algorithm

Implementation

Pseudocode

procedure selectionSort(A : list of sortable items)
    n = length(A)
    for i = 0 to n-2 do
        minIndex = i
        for j = i+1 to n-1 do
            if A[j] < A[minIndex] then
                minIndex = j
            end if
        end for
        swap(A[i], A[minIndex])
    end for
end procedure

Java

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Runtime Analysis

The displayed selection sort scans every remaining suffix, so it makes $N(N-1)/2$ comparisons and takes $\Theta (N^2)$ time even when the input is already sorted. Its runtime is not $\Theta (N+K)$ in the inversion count $K$.

Best and worst cases

The displayed implementation performs $N-1$ outer iterations. On iteration $i$, it scans the unsorted suffix to locate its minimum, regardless of the input order. Thus both best and worst cases take $\Theta (N^2)$ comparisons.

There is one swap per outer iteration (possibly swapping a position with itself), for $N-1$ swaps overall. Selection sort does not perform one swap per inversion.

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.