QuickSort: How to Choose the Pivot and Partition Process Illustrated¶
1. What is QuickSort?¶
QuickSort is a classic sorting algorithm based on the divide-and-conquer principle: it breaks a large problem into smaller subproblems, solves them recursively, and merges the results. The core steps are: select a pivot, partition the array into two parts (left < pivot, right > pivot), then recursively sort the subarrays.
QuickSort has excellent average-case efficiency (average time complexity O(n log n)), but poor pivot selection can degrade it to O(n²). Thus, “pivot selection” and “partitioning” are critical.
2. How to Choose the Pivot?¶
The pivot is the “navigator” of QuickSort. A good pivot ensures balanced partitioning and faster sorting; a bad pivot can lead to unbalanced partitions and reduced efficiency. Common pivot selection methods:
1. Leftmost/Rightmost Element (Simple but Risky)¶
Select the first or last element as the pivot.
- Disadvantage: If the array is already sorted (e.g., [1,2,3,4,5]), choosing the leftmost element (1) results in an empty left partition and a right partition of size n-1. This causes O(n²) time complexity in the worst case.
- Example: Array [1,2,3,4,5] with pivot 1 → right partition [2,3,4,5]. Recursive sorting of this subarray repeats the pattern, leading to O(n²).
2. Middle Element (Avoids Extremes)¶
Select the middle element (e.g., index n//2 for an array of length n).
- Advantage: More balanced than left/right extremes, reducing worst-case scenarios.
- Disadvantage: Still risky for nearly sorted arrays (e.g., [1,3,5,7,9] with pivot 5 → partitions [1,3] and [7,9], which works but may still fail in edge cases).
3. Median-of-Three (Most Recommended)¶
Select the median of the first, middle, and last elements as the pivot. This avoids sorted array degradation and ensures balanced partitions.
- Example: Array [1,2,3,4,5] → first=1, middle=3, last=5 → median=3. Partitioning results in left [1,2] and right [4,5], enabling efficient recursion.
- Advantage: Almost always avoids unbalanced partitions, maintaining O(n log n) time complexity.
3. Partition Process: Splitting the Array¶
Partition is the core step, aiming to place the pivot in its correct position and split the array into “left < pivot” and “right > pivot”. Here, the two-pointer technique is used with the array [5,3,8,4,2,7,1,6] (pivot = 5, leftmost element):
Step 1: Initialization¶
Array: [5,3,8,4,2,7,1,6], pivot = 5, left pointer i=0, right pointer j=7.
Step 2: Move Right Pointer to Find “Smaller”¶
The right pointer j moves left to find the first element < pivot:
- j=7: arr[j]=6 >5 → move left;
- j=6: arr[j]=1 <5 → swap with arr[i] → array becomes [1,3,8,4,2,7,5,6], i=1.
Step 3: Move Left Pointer to Find “Larger”¶
The left pointer i moves right to find the first element > pivot:
- i=1: arr[i]=3 ≤5 → move right;
- i=2: arr[i]=8 >5 → swap with arr[j] → array becomes [1,3,5,4,2,7,8,6], j=5.
Step 4: Repeat Until Pointers Meet¶
- j=5: arr[j]=7 >5 → move left;
- j=4: arr[j]=2 <5 → swap with arr[i] → array becomes
[1,3,2,4,5,7,8,6],i=3; - i=3: arr[i]=4 ≤5 → move right;
- i=4: arr[i]=5 ≤5 → move right;
- i=5: arr[i]=7 >5 → swap with arr[j] → array becomes
[1,3,2,4,5,7,8,6],i=j=5.
Final Result¶
The pivot (5) is placed at index 5. The array splits into:
- Left subarray: [1,3,2,4] (all <5);
- Right subarray: [7,8,6] (all >5).
4. Summary¶
QuickSort’s efficiency hinges on “correct pivot selection + efficient partitioning”:
- Pivot Selection: Prefer the median-of-three method to avoid worst-case O(n²) by ensuring balanced partitions.
- Partitioning: Use two pointers to split the array into “left < pivot” and “right > pivot”, then recursively sort the subarrays.
This approach ensures QuickSort runs in O(n log n) time in most cases, making it one of the most widely used sorting algorithms in practice.
Exercise: Try selecting the pivot using the median-of-three method for [3,1,4,1,5,9,2,6] and manually simulate the partitioning process!