Pivot selection
- Algorithms course
- Intermediate
- Lesson 5/80
- 4 min
Pick a pivot and partition the array in quick sort.
Pivot selection
Quick sort picks a pivot element and partitions the array into elements smaller and larger than the pivot. Pivot choice drives performance.
First, last or middle element are common choices. A bad pivot (smallest or largest) separates only one element each step; then the cost is O(n^2).
Random pivot or median-of-three reduces the worst-case risk. With a good pivot, average O(n log n).
Pivot strategies
Picking the first element is disastrous on a sorted array: only one element is separated per step. The last element carries the same risk.
Median-of-three: take the median of the first, middle and last elements. Improves sorted and reverse-sorted cases.
Random: uniform random selection lowers the worst-case probability. Very effective in practice.
Practice Pick pivot and print
Write pick_pivot(arr). Pick the last element as pivot and return it. Print 9 with print(pick_pivot([3, 1, 4, 1, 5, 9])).
Starter code
def pick_pivot(arr):
# Take the last element as pivotSample solution
def pick_pivot(arr):
# Take the last element as pivot
return arr[-1]
print(pick_pivot([3, 1, 4, 1, 5, 9]))Expected output
9
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What cost does a bad pivot give?
- O(1)
- O(n^2) Correct answer
- O(log n)
- O(n)
Explanation: O(n^2)
2 Pivot selection
pivot = arr[____]pivot = arr[-1]Explanation: -1 is right.
3 Pivot selection: match the terms
| Term | Meaning |
|---|---|
First pivot |
Risky |
Random |
Safe |
Median-of-three |
Balanced |
Worst case |
O(n^2) |