Sorting

Selection Sort

On each pass, scan the unsorted suffix for the minimum and swap it into place. The prefix grows by one sorted element per outer iteration.

Algorithm

Basic Implementation

basic.sh 
#!/usr/bin/env bash
set -euo pipefail
arr=(5 1 4 2 8)
n=${#arr[@]}
i=0
while [ "$i" -lt "$((n - 1))" ]; do
	min_idx=$i
	j=$((i + 1))
	while [ "$j" -lt "$n" ]; do
		if [ "${arr[j]}" -lt "${arr[min_idx]}" ]; then
			min_idx=$j
		fi
		j=$((j + 1))
	done
	if [ "$min_idx" -ne "$i" ]; then
		tmp=${arr[i]}
		arr[i]=${arr[min_idx]}
		arr[min_idx]=$tmp
	fi
	i=$((i + 1))
done
printf '['
sep=''
for v in "${arr[@]}"; do
	printf '%s%d' "$sep" "$v"
	sep=', '
done
printf ']\n'

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

Complexity

  • Time: O(n^2)
  • Space: O(1)

Implementation notes

  • Bash: explicit nested while with a manual three-line swap. Bash has no in-process minimum-by-index helper; piping to awk would fork another process and skip the educational scanning loop.
  • min_idx=$i resets at the top of each pass so the swap step branches on a clean comparison.
  • The replay records each compare frame, the chosen min_idx, and whether the trailing swap fired so the viewer sees the prefix grow one element per pass.
inner scan for minimum For each `i`, walk `j` from `i+1` to the end and track the index of the smallest element.
swap into place After the scan, swap `arr[i]` with `arr[min_idx]`. Skip the swap when `min_idx == i` so the replay records a no-op instead of a redundant write.