Selection Sort

Selection sort works by repeatedly selecting the minimum element from the unsorted portion of the array and placing it at the front. After each pass, the sorted region on the left grows by one element and the unsorted region on the right shrinks by one.

The algorithm mirrors how most people sort a hand of cards laid face-up on a table: scan all the cards, pick up the smallest, place it in position 1. Scan the remainder, pick up the smallest, place it in position 2. Repeat until done.

The defining characteristic is that selection sort makes at most n-1 swaps — exactly one per pass. Bubble sort can make O(n²) swaps in the worst case. When writes to storage are expensive — spinning disks, flash memory with limited write cycles, remote storage — selection sort's minimal swap count is a real practical advantage even though its comparison count is identical to bubble sort's.

Step-by-Step Trace

Starting array: [64, 25, 12, 22, 11]

Each pass scans the unsorted region (right side) to find the minimum, then swaps it to the front of that region.

Pass 1 — find min in [64, 25, 12, 22, 11], swap to index 0:

[64, 25, 12, 22, 11]
 ↑                       current start
         min=12          scanning... final min is 11 at index 4
[11, 25, 12, 22, 64] ✓   swap(0, 4): 11 placed, 64 displaced

Pass 2 — find min in [25, 12, 22, 64], swap to index 1:

[11 | 25, 12, 22, 64]
      ↑                  current start
         min=12          scanning... min is 12 at index 2
[11, 12, 25, 22, 64] ✓✓  swap(1, 2): 12 placed, 25 displaced

Pass 3 — find min in [25, 22, 64], swap to index 2:

[11, 12 | 25, 22, 64]
          ↑              current start
              min=22     scanning... min is 22 at index 3
[11, 12, 22, 25, 64] ✓✓✓ swap(2, 3): 22 placed, 25 displaced

Pass 4 — find min in [25, 64], swap to index 3:

[11, 12, 22 | 25, 64]
             ↑           current start
             min=25      scanning... min is 25 at index 3 (already in place)
[11, 12, 22, 25, 64] ✓✓✓✓ no swap needed (min already at front)

Result: [11, 12, 22, 25, 64] — sorted in 4 passes, 4 comparisons groups, 3 actual swaps.

Naive Implementation

fn selection_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
 
    // Outer loop: grow the sorted prefix one element at a time.
    // After iteration i, arr[0..=i] is sorted.
    for i in 0..n - 1 {
        // Assume the element at position i is the minimum.
        let mut min_idx = i;
 
        // Scan the unsorted region [i+1, n) to find the true minimum.
        for j in i + 1..n {
            if arr[j] < arr[min_idx] {
                min_idx = j; // found a smaller element — update min index
            }
        }
 
        // Only swap if the minimum is not already in position i.
        // This avoids a pointless write when the element is in place.
        if min_idx != i {
            arr.swap(i, min_idx);
        }
    }
}

This is clean and correct, but it still scans the full unsorted region to find only one extreme value (the min) per pass. The optimized version does the same scan but extracts two pieces of information — the min and the max — so each pass places two elements instead of one.

Optimized Implementation

Double-ended selection sort: in each pass, scan the unsorted region once and simultaneously record both the minimum and maximum indices. Swap the minimum to the left boundary and the maximum to the right boundary. The unsorted region shrinks by two elements per pass, halving the number of passes.

fn selection_sort_optimized(arr: &mut Vec<i32>) {
    let mut left = 0;               // left boundary of unsorted region
    let mut right = arr.len() - 1;  // right boundary of unsorted region
 
    while left < right {
        let mut min_idx = left;
        let mut max_idx = left;
 
        // Single scan of [left, right] to find both min and max.
        for k in left..=right {
            if arr[k] < arr[min_idx] {
                min_idx = k;
            }
            if arr[k] > arr[max_idx] {
                max_idx = k;
            }
        }
 
        // Place the minimum at the left boundary.
        if min_idx != left {
            arr.swap(left, min_idx);
        }
 
        // The max may have been at `left`, which we just swapped away.
        // If so, correct max_idx to point to its new location.
        if max_idx == left {
            max_idx = min_idx;
        }
 
        // Place the maximum at the right boundary.
        if max_idx != right {
            arr.swap(right, max_idx);
        }
 
        // Shrink the unsorted region from both ends.
        left += 1;
        right -= 1;
    }
}

The subtle correction if max_idx == left { max_idx = min_idx; } handles the case where the maximum happened to be sitting at left before we moved the minimum there. After the first swap, the old maximum is now at min_idx, so we update the pointer accordingly.

Time Complexity

Counting comparisons precisely.

Pass i (0-indexed) scans the unsorted region [i, n-1], making n-1-i comparisons. Summing over all n-1 passes:

Total comparisons = (n-1) + (n-2) + ... + 1
                  = Σ k  for k = 1 to n-1
                  = n(n-1) / 2

For n = 5 this is 5×4/2 = 10. Check against the trace: pass 1 makes 4 comparisons, pass 2 makes 3, pass 3 makes 2, pass 4 makes 1. Total = 10. Correct.

The critical property: comparison count does not depend on the input.

Unlike bubble sort, which can terminate early when a pass makes no swaps, selection sort always scans the entire unsorted region to be certain it has found the true minimum. There is no early-exit mechanism for comparisons. A sorted array and a reverse-sorted array both produce exactly n(n-1)/2 comparisons.

Swaps are always exactly n-1 (or fewer).

Each pass places one element via at most one swap. With n-1 passes, at most n-1 swaps occur total. In the best case (array already sorted), zero swaps occur because the min_idx != i guard fires n-1 times and all are false. In the worst case, exactly n-1 swaps occur.

Selection sort is not adaptive — its time complexity is Θ(n²) in all cases because the comparison count is fixed.

Space Complexity

Selection sort is O(1) auxiliary space. The only variables added beyond the input array are min_idx, max_idx, and the loop counter — a constant number of registers. All swaps happen in-place. No extra array, buffer, or recursion stack is allocated.