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] finishes after four passes, with two real swaps (passes 0 and 1) and two skip-swap passes (min_idx == i). Final array [1, 2, 4, 5, 8].

running minimum `min_idx` tracks the index of the smallest value seen in `arr[i..]`.
sorted prefix After each pass, `arr[0..i]` is the final sorted prefix.

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.

First pass over [5, 1, 4, 2, 8]: 1 is the running minimum.i0i1i2i3i451428imin

Step 2 - Swap 5 and 1

The smallest value moves into the first sorted slot.

After swap: [1, 5, 4, 2, 8].i0i1i2i3i415428sorted

Step 3 - Second scan finds 2

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

Second pass: 2 is selected from the suffix.i0i1i2i3i415428sortedimin

Step 4 - Sorted after two swaps

Swapping 5 and 2 gives [1, 2, 4, 5, 8]; later passes find no real swap.

After the second real swap: [1, 2, 4, 5, 8].i0i1i2i3i412458sortedsorted

Basic Implementation

basic.rb 
arr = [5, 1, 4, 2, 8]
n = arr.length
i = 0
while i < n - 1
	min_idx = i
	j = i + 1
	while j < n
		if arr[j] < arr[min_idx]
			min_idx = j
		end
		j = j + 1
	end
	if min_idx != i
		tmp = arr[i]
		arr[i] = arr[min_idx]
		arr[min_idx] = tmp
	end
	i = i + 1
end
puts arr.inspect

Complexity

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

Implementation notes

  • Ruby: same loop shape as Python / Java / JavaScript / C++ / C / Go / Rust / C# / Kotlin / Swift / Scala. The if min_idx != i guard is the canonical skip-swap variant from the lesson spec.
  • min_idx = i keeps the running-minimum invariant visible; the three-line tmp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = tmp swap mirrors the bubble-sort lesson rather than collapsing into parallel assignment.
  • The replay highlights the current min_idx distinctly from the scanning index j so the viewer sees the running minimum travel.