Sorting

Bubble Sort

Repeatedly walk the array, swapping adjacent out-of-order pairs. After each pass the largest unsorted element bubbles to its final position; stop early when a clean pass finds nothing to swap.

Algorithm

Canonical input arr=(5 1 4 2 8) finishes in three 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
	swapped=0
	j=0
	while [ "$j" -lt "$((n - i - 1))" ]; do
		if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then
			tmp=${arr[j]}
			arr[j]=${arr[j+1]}
			arr[j+1]=$tmp
			swapped=1
		fi
		j=$((j + 1))
	done
	if [ "$swapped" -eq 0 ]; then
		break
	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) worst case, O(n) best with the early-termination check
  • Space: O(1)

Implementation notes

  • Bash: explicit nested while with a manual three-line swap (tmp=${arr[j]}; arr[j]=${arr[j+1]}; arr[j+1]=$tmp) keeps the move visible. The shell has no sort for in-process arrays; piping to sort -n would promote the integers to text, fork another process, and skip the educational sorting loop entirely.
  • The swapped flag uses 0 / 1 integer semantics and is checked with [ "$swapped" -eq 0 ] so the early-termination branch is explicit.
  • The replay records each compare frame, each swap frame, and the swapped == 0 -> break frame at the end of pass 3 so the viewer sees the early-exit fire.
adjacent swaps A single pass compares each adjacent pair `arr[j], arr[j+1]` and swaps when out of order.
early termination A `swapped` flag detects an already-sorted suffix; clearing it ends the outer loop before doing unnecessary passes.