Quick Sort (Lomuto)

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this Bash DSA implementation can be compared directly with the other languages.

pivot The final element is moved to the boundary between smaller and larger values.

partition One scan rearranges the current range before the recursive calls.

Visual walkthrough

The pinned first partition uses [4, 1, 5, 2, 3] with pivot 3. The diagrams track the boundary, swaps, and recursive ranges.

Step 1 - Choose the last value as pivot

The pivot is arr[4] = 3, and i starts just before the current range.

Step 2 - Swap small values left

1 and 2 are <= pivot, so they move into the left partition.

Step 3 - Place pivot, then recurse

Swapping pivot 3 into index 2 gives [1, 2, 3, 4, 5]; recurse on [1, 2] and [4, 5].

Basic Implementation

                            basic.sh
                        

                            #!/usr/bin/env bash
set -euo pipefail

partition() {
	local low=$1
	local high=$2
	local pivot=${arr[high]}
	local i=$((low - 1))
	local j
	local tmp
	for ((j = low; j < high; j++)); do
		if ((arr[j] <= pivot)); then
			i=$((i + 1))
			tmp=${arr[i]}
			arr[i]=${arr[j]}
			arr[j]=$tmp
		fi
	done
	tmp=${arr[i+1]}
	arr[i+1]=${arr[high]}
	arr[high]=$tmp
	pivot_index=$((i + 1))
}

quick_sort() {
	local low=$1
	local high=$2
	if ((low < high)); then
		partition "$low" "$high"
		local p=$pivot_index
		quick_sort "$low" "$((p - 1))"
		quick_sort "$((p + 1))" "$high"
	fi
}

arr=(4 1 5 2 3)
pivot_index=0
quick_sort 0 $((${#arr[@]} - 1))
printf '['
sep=''
for v in "${arr[@]}"; do
	printf '%s%d' "$sep" "$v"
	sep=', '
done
printf ']\n'

                        

Complexity

Time: O(n^2) worst, O(n log n) average
Space: O(log n) average call stack
Stable: no

Implementation notes

arr=(4 1 5 2 3) is the pinned Bash indexed array, and quick_sort mutates it in place by index.
quick_sort "$low" "$high" receives integer bounds. if ((low < high)) is Bash arithmetic evaluation for the recursive base case.
partition "$low" "$high" chooses the last element as the pivot with pivot=${arr[high]}.
i=$((low - 1)) marks the end of the smaller-or-equal region. The scan variable j walks from low to high - 1.
if ((arr[j] <= pivot)); then is a numeric comparison. When it passes, i moves right and the tmp lines swap arr[i] with arr[j].
After the scan, another tmp swap moves the pivot into arr[i+1], and pivot_index=$((i + 1)) tells quick_sort where to split.
The recursive calls sort low..p-1 and p+1..high. Lomuto quicksort is not stable because swaps can move equal values around.

First partition replay

pivot 3 in [4, 1, 5, 2, 3]
4 > 3: keep right side
1 <= 3: swap into left side -> [1, 4, 5, 2, 3]
5 > 3: keep right side
2 <= 3: swap into left side -> [1, 2, 5, 4, 3]
pivot swap: [1, 2, 3, 4, 5]

Final output uses the shared Bash formatter: printf '[', for v in "${arr[@]}", printf '%s%d' "$sep" "$v", and printf ']\n'.