Course contentsShow
← Computer Science
Lesson 766 of 2,87218. Sorting AlgorithmsFree lesson

Hoare Partition Scheme

Learn the more efficient Hoare partitioning with two-pointer approach from opposite ends of the array.

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.