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].

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.

Basic Implementation

basic.sh
Replay: real traced execution (multi-file project)
#!/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'

  1. arr ← [5, 1, 4, 2, 8]

    2set -euo pipefail3arr=(5 1 4 2 8)4n=${#arr[@]}
    values this step[5, 1, 4, 2, 8]arr

  2. n ← 5

    3arr=(5 1 4 2 8)4n=${#arr[@]}5i=0
    values this step5n[5, 1, 4, 2, 8]arr

  3. swapped ← 0

    6while [ "$i" -lt "$((n - 1))" ]; do7	swapped=08	j=0
    values this step0swapped

  4. arr[j] > arr[j+1] ← true

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this steptruearr[j] > arr[j+1][5, 1, 4, 2, 8]arr0j5arr[j]1arr[j+1]

  5. arr ← [1, 5, 4, 2, 8], swapped ← 1

    11tmp=${arr[j]}12arr[j]=${arr[j+1]}13arr[j+1]=$tmp
    values this step[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]arr1swapped

  6. arr[j] > arr[j+1] ← true

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this steptruearr[j] > arr[j+1][1, 5, 4, 2, 8]arr1j5arr[j]4arr[j+1]

  7. arr ← [1, 4, 5, 2, 8], swapped ← 1

    11tmp=${arr[j]}12arr[j]=${arr[j+1]}13arr[j+1]=$tmp
    values this step[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]arr1swapped

  8. arr[j] > arr[j+1] ← true

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this steptruearr[j] > arr[j+1][1, 4, 5, 2, 8]arr2j5arr[j]2arr[j+1]

  9. arr ← [1, 4, 2, 5, 8], swapped ← 1

    11tmp=${arr[j]}12arr[j]=${arr[j+1]}13arr[j+1]=$tmp
    values this step[1, 4, 5, 2, 8] → [1, 4, 2, 5, 8]arr1swapped

  10. arr[j] > arr[j+1] ← false

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this stepfalsearr[j] > arr[j+1][1, 4, 2, 5, 8]arr3j5arr[j]8arr[j+1]

  11. swapped ← 0

    6while [ "$i" -lt "$((n - 1))" ]; do7	swapped=08	j=0
    values this step0swapped

  12. arr[j] > arr[j+1] ← false

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this stepfalsearr[j] > arr[j+1][1, 4, 2, 5, 8]arr0j1arr[j]4arr[j+1]

  13. arr[j] > arr[j+1] ← true

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this steptruearr[j] > arr[j+1][1, 4, 2, 5, 8]arr1j4arr[j]2arr[j+1]

  14. arr ← [1, 2, 4, 5, 8], swapped ← 1

    11tmp=${arr[j]}12arr[j]=${arr[j+1]}13arr[j+1]=$tmp
    values this step[1, 4, 2, 5, 8] → [1, 2, 4, 5, 8]arr1swapped

  15. arr[j] > arr[j+1] ← false

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this stepfalsearr[j] > arr[j+1][1, 2, 4, 5, 8]arr2j4arr[j]5arr[j+1]

  16. swapped ← 0

    6while [ "$i" -lt "$((n - 1))" ]; do7	swapped=08	j=0
    values this step0swapped

  17. arr[j] > arr[j+1] ← false

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this stepfalsearr[j] > arr[j+1][1, 2, 4, 5, 8]arr0j1arr[j]2arr[j+1]

  18. arr[j] > arr[j+1] ← false

    9while [ "$j" -lt "$((n - i - 1))" ]; do10	if [ "${arr[j]}" -gt "${arr[j+1]}" ]; then11		tmp=${arr[j]}
    values this stepfalsearr[j] > arr[j+1][1, 2, 4, 5, 8]arr1j2arr[j]4arr[j+1]

  19. done ← true

    18if [ "$swapped" -eq 0 ]; then19	break20fi
    values this steptruedone0swapped

  20. stdout ← [1, 2, 4, 5, 8]

    28done29printf ']\n'
    values this step[1, 2, 4, 5, 8]stdout[1, 2, 4, 5, 8]arr

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.