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

Basic Implementation

basic.R 
arr <- c(5, 1, 4, 2, 8)
n <- length(arr)
i <- 1
while (i <= n - 1) {
	min_idx <- i
	j <- i + 1
	while (j <= n) {
		if (arr[j] < arr[min_idx]) {
			min_idx <- j
		}
		j <- j + 1
	}
	if (min_idx != i) {
		tmp <- arr[i]
		arr[i] <- arr[min_idx]
		arr[min_idx] <- tmp
	}
	i <- i + 1
}
cat("[", paste(arr, collapse = ", "), "]\n", sep = "")

Complexity

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

Implementation notes

  • R: same loop shape as Python / Java / JavaScript / C++ / C / Go / Rust / C# / Kotlin / Swift / Scala / Ruby / PHP / Lua / Perl. 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.
  • The replay highlights the current min_idx distinctly from the scanning index j so the viewer sees the running minimum travel.
running minimum `min_idx` tracks the index of the smallest value seen in `arr[i..n]`.
sorted prefix After each pass, `arr[1..i]` is the final sorted prefix.