# 8.2 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²).

Chapter: Advanced Sorting & Searching · ~55 min · hard
URL: https://dsa.fetehadin.com/learn/quick-sort

## Mental 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.

```cpp
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.

## C++ code: quick-sort.cpp

```cpp
#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);
}
```

Expected output:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| 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²) |

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.

## Videos

- [QuickSort Algorithm](https://youtu.be/7h1s2SojIRw) (Abdul Bari): Abdul Bari's classic. Partition traced by hand with i and j.
- [Quick sort in 4 minutes](https://youtu.be/Hoixgm4-P4M) (Michael Sambol): A 4-minute visual recap.

## Exam lens

Likely questions:

- Explain divide and conquer using quick sort.
- Partition `10, 80, 30, 90, 40, 50, 70` around 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.

## Quick check

1. After one partition, the pivot is…
   A. at index 0
   B. in its final sorted position
   C. at the end
   D. removed
   Answer: B. Everything left is smaller and everything right is bigger, so it never moves again.

2. Last-item pivot on an already sorted array gives…
   A. O(n)
   B. O(n log n)
   C. O(n²)
   D. O(log n)
   Answer: C. Every partition peels off just one item, so n levels of O(n) work.

3. Partition `3, 8, 2, 5, 4` around pivot 4 (Lomuto). Result?
   A. `3 2 4 5 8`
   B. `2 3 4 8 5`
   C. `3 2 4 8 5`
   D. `4 3 8 2 5`
   Answer: A. 3 stays (i=0), 8 skipped, 2 swaps with 8 → `3 2 8 5 4`, 5 skipped. Then the pivot swaps with a[2] → `3 2 4 5 8`.

4. Quick sort is…
   A. stable, not in-place
   B. in-place, not stable
   C. stable and in-place
   D. neither
   Answer: B. It only uses the recursion stack, but long-distance swaps break stability.

## Practice

**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.

Solution:

- 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.

**Problems:**

- [Sort an Array](https://leetcode.com/problems/sort-an-array/) (medium). Hint: A plain last-item pivot can time out on sorted tests. Use a random pivot.
- [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) (medium). Hint: Quickselect. Partition once and recurse into only the side that holds index n − k.

## Mastery checklist

- [ ] I can partition an array around a pivot by hand.
- [ ] I can write partition and quickSort from memory.
- [ ] I can explain best, average and worst case.
- [ ] I know quick sort is in-place and not stable.