Splitting around a pivot
Partitioning rearranges an array around a chosen pivot value so that everything smaller sits to its left and everything larger sits to its right. The pivot then occupies its final sorted position. This single operation powers quicksort and quickselect.
The pointer scheme
A common scheme keeps a boundary pointer marking the end of the smaller than pivot region. A scanning pointer walks the array, and whenever it finds an element less than the pivot, you swap that element into the boundary region and advance the boundary.
- Scan each element against the pivot.
- Swap small elements into the growing left region.
- Place the pivot at the boundary when the scan finishes.
After this single linear pass the pivot is correctly positioned, even though the two sides remain unsorted among themselves.
Why it matters
Because partition fixes one element and splits the rest into two independent groups, you can recurse on the groups to sort, or recurse on just one group to select an order statistic without sorting the whole array.
Key idea
Partitioning sweeps once, swapping smaller elements into a growing left region, so the pivot reaches its final position and the array splits into two groups ready for recursion.