Sorting

Quick Sort (Lomuto)

Choose the last item as a pivot, partition smaller values to its left, then recurse on the two sides.

Algorithm

Basic Implementation

basic.lua 
local function partition(arr, low, high)
	local pivot = arr[high]
	local i = low - 1
	for j = low, high - 1 do
		if arr[j] <= pivot then
			i = i + 1
			arr[i], arr[j] = arr[j], arr[i]
		end
	end
	arr[i + 1], arr[high] = arr[high], arr[i + 1]
	return i + 1
end

local function quick_sort(arr, low, high)
	if low < high then
		local pivot_index = partition(arr, low, high)
		quick_sort(arr, low, pivot_index - 1)
		quick_sort(arr, pivot_index + 1, high)
	end
end

local arr = {4, 1, 5, 2, 3}
quick_sort(arr, 1, #arr)
io.write("[")
for k = 1, #arr do
	if k > 1 then io.write(", ") end
	io.write(tostring(arr[k]))
end
io.write("]\n")

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.

Initial partition state for [4, 1, 5, 2, 3].i0i1i2i3i441523j startspivot

Step 2 - Swap small values left

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

After scanning values before the pivot: [1, 2, 5, 4, 3].i0i1i2i3i412543<= 3<= 3> 3> 3pivot

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

Pivot lands at index 2 and splits the remaining work.left rangepivotright range[1, 2]3 at i2[4, 5]quick_sort(0,1)fixedquick_sort(3,4)

Complexity

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

Implementation notes

  • local arr = {4, 1, 5, 2, 3} is sorted in place by quick_sort(arr, 1, #arr).
  • partition(arr, low, high) chooses the pivot with local pivot = arr[high]; in the first call, Lua slot 5 holds pivot 3.
  • Lua source indexes are 1-based: local i = low - 1 starts at 0, and for j = low, high - 1 do scans slots 1 through 4.
  • The partition comparison is if arr[j] <= pivot then, so only values at or below the pivot move to the left side.
  • Swaps use Lua multiple assignment: arr[i], arr[j] = arr[j], arr[i].
  • The replay labels positions in zero-based cross-language form: it keeps 4 right of pivot 3, swaps 1 left, keeps 5 right, then swaps 2 left.
  • Those partition steps change the table from [4, 1, 5, 2, 3] to [1, 4, 5, 2, 3], then [1, 2, 5, 4, 3].
  • The final pivot swap arr[i + 1], arr[high] = arr[high], arr[i + 1] puts 3 in Lua slot 3; the trace reports that as pivot index 2.
  • quick_sort recurses on low..pivot_index - 1 and pivot_index + 1..high; the replay summarizes the left side [1, 2] and right side [4, 5].
  • The final io.write loop prints [1, 2, 3, 4, 5].
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.