Selection Sort - Fortran DSA

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.

running minimum Track the index of the smallest value seen during a scan.

Visual walkthrough

The pinned input [5, 1, 4, 2, 8] sorts with two real swaps. The frames keep the running minimum and swap positions visible.

Step 1 - First scan finds 1

In the first pass, min_idx moves from 5 to 1.

Step 2 - Swap 5 and 1

The smallest value moves into the first sorted slot.

Step 3 - Second scan finds 2

In the unsorted suffix, 2 is smaller than 5 and becomes the next minimum.

Step 4 - Sorted after two swaps

Swapping 5 and 2 gives [1, 2, 4, 5, 8]; later passes find no real 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.