DailyRNG
Login
Advanced

Quicksort

Quicksort picks a pivot, puts smaller items left and bigger right, then sorts each side. It is usually the fastest in practice, though its worst case is n squared.

What you will see

3

About 3 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Run quicksort and probe the pivot.

1

Sort with quicksort.

def qsort(a): if len(a) <= 1: return a p = a[0] lo = qsort([x for x in a[1:] if x < p]) hi = qsort([x for x in a[1:] if x >= p]) return lo + [p] + hi print(qsort([5, 2, 8, 1]))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
[1, 2, 5, 8]
2

Split around a pivot.

nums = [5, 2, 8, 1] pivot = nums[0] smaller = [x for x in nums[1:] if x < pivot] bigger = [x for x in nums[1:] if x >= pivot] print(smaller, bigger)

Before you run it, say out loud what it will print. Then open the answer.

What it prints
[2, 1] [8]
3

Pick a random pivot.

import random nums = [5, 2, 8, 1] print(random.choice(nums))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
one of 5, 2, 8, 1
4

Show the log depth of eight.

import math print(round(math.log2(8)))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
3

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Quicksort splits items around a pivot and sorts each side, averaging n log n but hitting n squared on a bad pivot.
1 pick a pivot
↓
2 smaller left bigger right
↓
3 sort each side
↓
4 bad pivot gives n squared
Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

def qsort(a): sets nothing on screen
if len(a) <= 1: sets nothing on screen
return a sets nothing on screen
p = a[0] sets nothing on screen
lo = qsort([x for x in a[1:] if x < p]) sets nothing on screen
hi = qsort([x for x in a[1:] if x >= p]) sets nothing on screen
return lo + [p] + hi sets nothing on screen
print(qsort([5, 2, 8, 1])) [1, 2, 5, 8]
Why this works
Why it wins in practice

Quicksort sorts in place with good cache behavior, so it beats merge sort on ordinary data despite the same average cost. The worst case is rare and avoidable.

Pivot is the whole trick

A balanced pivot keeps the depth small. A bad pivot makes it degenerate. Choosing the pivot well is the difference between n log n and n squared.

Examples

Pick a pivot

nums = [5, 2, 8, 1]
pivot = nums[0]
smaller = [x for x in nums[1:] if x < pivot]
bigger = [x for x in nums[1:] if x >= pivot]
print(smaller, bigger)

Everything smaller than the pivot goes left, the rest right. The pivot sits between them.

Sort both sides

def qsort(a):
    if len(a) <= 1:
        return a
    p = a[0]
    lo = qsort([x for x in a[1:] if x < p])
    hi = qsort([x for x in a[1:] if x >= p])
    return lo + [p] + hi
print(qsort([5, 2, 8, 1]))

Sort each side the same way. The pivot lands in its final place each round.

Pivot choice matters

nums = [1, 2, 3, 4, 5]
print(nums[0])

If the pivot is always the smallest, one side is empty and the split is lopsided. That is the n squared worst case.

Random pivot

import random
nums = [5, 2, 8, 1]
print(random.choice(nums))

A random pivot avoids the lopsided split on sorted input. That is why quicksort often picks randomly.

In-place partition

nums = [5, 2, 8, 1]
pivot = nums[-1]
lo = [x for x in nums[:-1] if x < pivot]
hi = [x for x in nums[:-1] if x >= pivot]
print(lo + [pivot] + hi)

Split around the pivot in one scan. Real quicksort does this by swapping in place.

Average is n log n

import math
print(round(math.log2(8)))

A balanced split gives log levels. Each level scans n, so the average is n log n.

Fast in practice

print(sorted([9, 3, 7]))

Built-in sorts beat a hand-written quicksort. Quicksort is the idea; the library is the tuned version.

Worst case is real

nums = [1, 2, 3, 4]
print(nums[0])

Sorted input with a first-element pivot is the worst case. A random or middle pivot avoids it.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Merge sort
Previous Lesson
Merge sort
Next Lesson
Binary search
Binary search →