Quicksort, quickselect and pivot selection | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython example pack ↓

Partition rules and pivot choice are separate decisions. Random pivots reduce dependence on adversarial ordering but do not eliminate worst-case possibilities. Three-way partitioning separates less/equal/greater keys and handles duplicates effectively.

Quicksort explores both partitions; quickselect follows only the partition containing k, giving expected linear selection. Define zero- versus one-based rank. Median-of-medians provides worst-case linear selection when correctly implemented, at a substantial constant cost.

Introsort switches to heapsort at a depth limit to bound worst-case sorting. Timsort exploits existing runs; Python's built-in sort is not this quicksort. The readable three-list implementation below is not in-place, and allocation costs matter.

A worked trace

[3,1,3,2], pivot3 produces less=[1,2], equal=[3,3], greater=[]. Equal keys need no recursive sorting.

Cost and assumptions

Randomised quicksort expected O(n log n), worst O(n²); quickselect expected O(n). This example allocates O(n) per partition.

Executable example

Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.

Python 3

from random import choice

def quicksort(a):
    if len(a) < 2: return list(a)
    p = choice(a)
    return (quicksort([x for x in a if x < p]) +
            [x for x in a if x == p] +
            quicksort([x for x in a if x > p]))
assert quicksort([3,1,3,2]) == [1,2,3,3]

TEST YOUR UNDERSTANDING

Your turn

What recurrence results from always choosing the minimum pivot?

Reveal the reasoning

T(n)=T(n−1)+Θ(n), hence Θ(n²). Randomisation prevents this pattern in expectation, not as an impossibility.

Take it further

Write down the input contract and the invariant before changing the example.
Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
Derive the cost under the stated model; measure several input sizes and explain discrepancies.

Primary reading & lecture notes

Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.

MIT 6.046J · Design and Analysis ↗Princeton · Algorithms, Sedgewick & Wayne ↗

Solve the exercise before moving on.

RasimAtaberkŞahin