Partitioning Arrays Around a Pivot
What you'll learn: How to rearrange an array so all elements smaller than a chosen "pivot" value come before those that are larger—a foundational technique for efficient sorting.
Core Idea
Imagine you're organizing books on a shelf by height, but you pick one book as your reference point (the "pivot"). You move all shorter books to the left of it and all taller books to the right. That's partitioning!
In an array, you choose one element as the pivot (often the last element, first element, or middle one). Then you rearrange the array so that:
- All values less than the pivot appear before it
- All values greater than the pivot appear after it
- The pivot ends up in its "correct" sorted position
You don't fully sort the array—just organize it around that one value.
How It Works
Start with two pointers or indices: one scanning from the left, one working from positions you've checked. As you iterate through the array:
- Compare each element to the pivot
- If smaller than the pivot, swap it toward the front section
- If larger, leave it for the back section
- Place the pivot between the two sections
After partitioning [8, 3, 7, 1, 9, 5] around pivot 5, you might get [3, 1, 5, 7, 9, 8]. Notice 3 and 1 are before 5; 7, 9, and 8 are after. The exact order within each section doesn't matter yet.
Why It Matters
This operation is the heart of quicksort, one of the fastest sorting algorithms. By repeatedly partitioning smaller and smaller sections, you eventually sort the entire array efficiently.
Key Takeaway: Partitioning rearranges an array around a pivot value so smaller elements migrate left and larger ones right, creating two unsorted groups separated by the pivot—the foundation of quicksort.