Partitioning

Partitioning is the core of quick sort. It rearranges the array so elements smaller than the pivot are on the left, and larger are on the right.

How Partitioning Works

Use two pointers: one tracks the boundary of smaller elements, the other scans the array.

Step-by-Step Example

Partition [5, 2, 8, 1, 9, 3] with pivot = 3 (last element):

1. Initialize: i = -1 (boundary of smaller elements)
2. Scan j from 0 to 4:
   • j=0: 5 > 3, do nothing
   • j=1: 2 < 3, increment i, swap → [2, 5, 8, 1, 9, 3]
   • j=2: 8 > 3, do nothing
   • j=3: 1 < 3, increment i, swap → [2, 1, 8, 5, 9, 3]
   • j=4: 9 > 3, do nothing
3. Place pivot: swap arr[i+1] with pivot → [2, 1, 3, 5, 9, 8]

Result: Elements < 3 are left, elements > 3 are right, pivot is in correct position.

Implementation

Key Points

1. Pivot selection: Usually last element (can be optimized)
2. Two pointers: i (boundary), j (scanner)
3. Swap smaller: When element < pivot, move to left side
4. Place pivot: After scanning, pivot goes to i+1

Pivot Selection Strategies

What’s Next?

Now that you understand partitioning, let’s see the complete quick sort algorithm in action.