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

Canonical input arr=(5 1 4 2 8) finishes in four outer passes and yields [1, 2, 4, 5, 8].

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'

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.