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.f90 
program sort_selection
    implicit none
    integer :: arr(5) = [5, 1, 4, 2, 8]
    integer :: n, i, j, min_idx, tmp
    n = 5
    do i = 1, n - 1
        min_idx = i
        do j = i + 1, n
            if (arr(j) < arr(min_idx)) then
                min_idx = j
            end if
        end do
        if (min_idx /= i) then
            tmp = arr(i)
            arr(i) = arr(min_idx)
            arr(min_idx) = tmp
        end if
    end do
    print '(*(I0,1X))', arr
end program sort_selection

Complexity

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

Implementation notes

  • Fortran: skip the swap when min_idx == i to match the lesson spec's frame counts. Do not delegate to a library 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.