This page visualizes the Quicksort algorithm, first developed by British computer scientist C. A. R. Hoare in 1959. The animation demonstrates two of its most well-known partitioning strategies: the Lomuto scheme and Hoare's original scheme. When you run the animation, both algorithms sort an identical, randomly shuffled array, allowing for a side-by-side comparison of their performance. Each swap operation is captured and rendered as a distinct frame in the animation.
Notice that the Hoare partition scheme on the right typically finishes much faster, requiring fewer steps (swaps) to sort the array. This is because Hoare's method uses two pointers that move towards each other, resulting in fewer overall swaps compared to the single-pointer method used by the Lomuto scheme (popularized by Jon Bentley and Nico Lomuto). While Lomuto's scheme is often considered more straightforward to implement, Hoare's is generally more efficient in practice.
// Lomuto Partition Scheme
partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j from low to high - 1:
if arr[j] < pivot:
i++
swap arr[i] and arr[j]
swap arr[i + 1] and arr[high]
return i + 1
// Hoare Partition Scheme
partition(arr, low, high):
pivot = arr[floor((low + high) / 2)]
i = low - 1
j = high + 1
while true:
do i++ while arr[i] < pivot
do j-- while arr[j] > pivot
if i >= j:
return j
swap arr[i] and arr[j]