Sorting

Selection Sort

Repeatedly find the index of the smallest remaining element and swap it into the next "sorted prefix" slot. Unlike bubble sort, only one swap per pass.

Algorithm

Canonical input [5, 1, 4, 2, 8] sorts in two real swaps; the last two passes find min_idx == i and skip the swap.

Basic Implementation

basic.py 
arr = [5, 1, 4, 2, 8]
n = len(arr)
for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
        if arr[j] < arr[min_idx]:
            min_idx = j
    if min_idx != i:
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(arr)

Complexity

  • Time: O(n^2) regardless of input order
  • Space: O(1)
  • Stable: no
  • Swaps: at most n-1

Implementation notes

  • Python: skip the swap when min_idx == i to match the lesson spec's frame counts. Do not delegate to sorted() / list.sort().
  • The replay highlights j (scanning) versus min_idx (running minimum) distinctly, then animates the per-pass swap.
running minimum Track the index of the smallest value seen during a scan.