Quick Sort
Pick a pivot, partition so smaller items go left and bigger items go right, then sort each side recursively. Average O(n log n), worst O(n²).
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
A teacher wants to sort exam papers. She picks one paper, say score 70, as the pivot. Everyone below 70 goes on the left pile, everyone above on the right pile, and 70 sits in the middle, already in its final place. Then she does the same with each pile. Piles of one paper are done.
That is divide and conquer: split the problem, solve the parts, and (here) there is nothing to combine.
Partition (Lomuto)
Use the last item as the pivot. Keep i as the end of the “smaller than pivot” zone.
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) swap(a[++i], a[j]);
swap(a[i + 1], a[hi]); // pivot into place
return i + 1;Then sort lo .. p − 1 and p + 1 .. hi.
Best vs worst
- Good pivot (near the median): each level halves the array, so log n levels of O(n) work gives O(n log n).
- Bad pivot (the smallest or largest every time, e.g. sorted input with a last-item pivot): each level removes one item, so n levels gives O(n²).
A random pivot makes the bad case very unlikely.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Watch the "small" zone grow as items smaller than the pivot are swapped in. Then try a sorted array for the worst case.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
int partition(int a[], int lo, int hi) { // Lomuto: last item is the pivot
int pivot = a[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (a[j] < pivot) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[hi]);
return i + 1;
}
void print(int a[], int n) { for (int k = 0; k < n; k++) cout << a[k] << " "; cout << "\n"; }
void quickSort(int a[], int lo, int hi, int n) {
if (lo < hi) {
int p = partition(a, lo, hi);
cout << "pivot " << a[p] << " -> index " << p << ": ";
print(a, n);
quickSort(a, lo, p - 1, n);
quickSort(a, p + 1, hi, n);
}
}
int main() {
int a[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(a) / sizeof(a[0]);
quickSort(a, 0, n - 1, n);
cout << "sorted: "; print(a, n);
}pivot 70 -> index 4: 10 30 40 50 70 90 80 pivot 50 -> index 3: 10 30 40 50 70 90 80 pivot 40 -> index 2: 10 30 40 50 70 90 80 pivot 30 -> index 1: 10 30 40 50 70 90 80 pivot 80 -> index 5: 10 30 40 50 70 80 90 sorted: 10 30 40 50 70 80 90
05Complexity
| Best case (pivot splits in half) | O(n log n) |
|---|---|
| Average case | O(n log n) |
| Worst case (sorted input, last-item pivot) | O(n²) |
| Extra space | O(log n) recursion on average, O(n) worst |
| Stable? | No |
| In-place? | Yes |
Picking a random or median-of-three pivot makes the worst case very unlikely. In practice quick sort is often the fastest comparison sort.
06Watch
QuickSort Algorithm
Why this one: Abdul Bari's classic. Partition traced by hand with i and j.
Quick sort in 4 minutes
Why this one: A 4-minute visual recap.
07Exam lens
Likely questions
- Explain divide and conquer using quick sort.
- Partition
10, 80, 30, 90, 40, 50, 70around the last item. Show i, j and every swap. - What is the worst case of quick sort? Which input causes it with a last-item pivot?
- Write partition() and quickSort() in C++.
Common mistakes
- Recursing on
(lo, p)instead of(lo, p − 1). The pivot is already in place. - Forgetting the final
swap(a[i + 1], a[hi])that puts the pivot in place. - Saying quick sort is always O(n log n).
- Calling it stable.
08Quick check
09Practice
🟢 Trace by hand
Run quick sort (Lomuto, last-item pivot) on 10, 80, 30, 90, 40, 50, 70. Write the array after each partition and the pivot's final index.
Show answer
- pivot 70 → index 4:
10 30 40 50 70 90 80 - pivot 50 → index 3:
10 30 40 50 70 90 80 - pivot 40 → index 2 (left side
10 30 40) - pivot 30 → index 1
- pivot 80 → index 5:
10 30 40 50 70 80 90
🟡 Implement it
Make quick sort pick a random pivot (swap a random item in [lo, hi] with a[hi] before partitioning). Compare comparison counts on a sorted array of 1,000.
Hint
int r = lo + rand() % (hi - lo + 1); swap(a[r], a[hi]); at the start of partition.
🔴 Solve problems
Hint
A plain last-item pivot can time out on sorted tests. Use a random pivot.
Hint
Quickselect. Partition once and recurse into only the side that holds index n − k.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.