Lomuto vs. Hoare Partition Schemes
A deep dive into the two most common partitioning strategies used in the Quick Sort algorithm.
At a Glance
| Feature | Lomuto Scheme | Hoare Scheme |
|---|---|---|
| Pivot Choice | Typically the last element | Typically the first element |
| Pivot Position | Places pivot in its final sorted position | Does NOT place pivot in its final position |
| Efficiency | Slightly less efficient; more swaps | More efficient; fewer swaps on average |
| Implementation | Simpler and more intuitive to understand | Slightly more complex to implement correctly |
| Recursive Calls | `quickSort(low, p-1)` and `quickSort(p+1, high)` | `quickSort(low, p)` and `quickSort(p+1, high)` |
Lomuto Scheme
The Lomuto scheme is often taught first because it's more intuitive. It works by maintaining a pointer for the 'smaller elements' section and swapping the pivot into its final place at the end.
Pros:
- Easier to understand and visualize.
- Guarantees the pivot is in its final sorted position after partitioning.
Cons:
- Performs more swaps than Hoare's scheme.
- Degrades to O(n²) when all elements are equal.
Hoare Scheme (Used on this site)
The Hoare scheme, the original method proposed by Tony Hoare, is generally more efficient. It uses two pointers that scan towards each other from opposite ends of the array, swapping elements that are on the wrong side.
Pros:
- Faster in practice due to fewer swaps (about 3x fewer).
- Handles the case of all equal elements gracefully.
Cons:
- Slightly less intuitive to implement correctly.
- The pivot's final position is not known after the partition, which affects the recursive calls.