Hoare Partition Scheme
What you'll learn: You'll discover a more efficient way to partition an array for Quicksort by moving two pointers toward each other from opposite ends.
The Core Idea
The Hoare Partition Scheme is an alternative to Lomuto's approach. Instead of moving a single pointer forward, Hoare uses two pointers—one starting at the left edge, one at the right—and moves them toward each other. Each pointer searches for elements that are on the wrong side of the pivot, then swaps them when both have found misplaced elements.
Think of it like two inspectors walking toward each other in a warehouse: the left inspector looks for items that are "too large" (should be on the right), and the right inspector looks for items "too small" (should be on the left). When both find a problem, they swap the items. They continue until they meet in the middle.
Why It's More Efficient
Hoare's scheme typically performs three times fewer swaps than Lomuto's on average. It also doesn't always place the pivot in its final position immediately—the pivot might end up slightly off-center—but it guarantees that after partitioning, all elements to the left of the meeting point are ≤ all elements to the right.
The two-pointer approach means you're scanning the entire array from both ends simultaneously, which reduces redundant comparisons and better handles arrays with many duplicate elements.
Key Characteristics
- Uses two pointers moving inward from opposite ends
- Fewer swaps than Lomuto (better constant factors)
- Pivot doesn't necessarily end up in its final sorted position
- Requires slightly more careful implementation to avoid infinite loops
Key Takeaway:
The Hoare Partition Scheme efficiently partitions arrays by moving two pointers from opposite ends toward each other, swapping misplaced elements as they go—resulting in fewer swaps and better overall performance than the simpler Lomuto scheme.