Pivot selection

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.

Exercise 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])).

Show example solution

def pick_pivot(arr):
    # Take the last element as pivot
    return arr[-1]
print(pick_pivot([3, 1, 4, 1, 5, 9]))

Test yourself

What cost does a bad pivot give?
- O(1)
- O(n^2)
- O(log n)
- O(n)
Show answer

O(n^2) — O(n^2)
Pivot selection
```
pivot = arr[____]
```
Show answer
```
pivot = arr[-1]
```
Pivot selection: match the terms

First pivot

Risky
Random

Safe
Median-of-three

Balanced
Worst case

O(n^2)

Next lesson: Partitioning

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies