C++UCS301
Sorting AlgorithmsC++17

Quick Sort

Quick sort partitions values around a pivot and recursively sorts the two resulting regions.

What to understand

  • Partition invariant
  • Pivot choice
  • Lomuto and Hoare schemes
  • Recursion depth

Remember this

  1. 1Average O(n log n)
  2. 2Worst O(n²) with poor pivots
  3. 3Usually fast in practice
  4. 4Randomisation reduces adversarial behaviour

Detailed notes

Quick sort partitions a range so values on one side satisfy the pivot relation and values on the other side do not. Recursion then operates on smaller independent partitions.

Balanced partitions produce logarithmic depth and Θ(n log n) work. Repeated extreme pivots produce quadratic work and linear stack depth, so randomisation or median-style selection is important.

How it works

  1. 1Choose a pivot independently of the partition scan.
  2. 2Maintain the partition scheme's boundary invariant.
  3. 3Place or identify the pivot split.
  4. 4Recurse only on ranges that exclude the final pivot region.

Worked trace

Lomuto partition

[7,2,9,4,5], pivot=5
  1. 17 is not below pivot; boundary remains 0.
  2. 22 < 5; swap it to boundary → [2,7,9,4,5].
  3. 39 is not below pivot; 4 < 5, so move 4 to boundary 1.
  4. 4Swap pivot into boundary 2.
Result: [2,4,5,7,9] with pivot 5 final at index 2

Where it is used

  • Fast general in-memory sorting
  • Partition-based selection
  • Systems where locality matters more than stability

Common mistakes

  • Recursing on a range that still contains the same pivot
  • Using deterministic end pivots on already sorted input
  • Claiming standard quick sort is stable

Complexity analysis

OperationBestAverageWorstExtra space
SortO(n log n)O(n log n)O(n²)O(log n)

C++ implementation

C++17 reference
main.cpp

Randomised quick sort

Random pivot selection makes consistently unbalanced partitions unlikely for ordinary input.

int partition(vector<int>& a, int low, int high) {
    int pivot = a[high], boundary = low;
    for (int i = low; i < high; ++i)
        if (a[i] < pivot) swap(a[i], a[boundary++]);
    swap(a[boundary], a[high]);
    return boundary;
}

void quickSort(vector<int>& a, int low, int high) {
    if (low >= high) return;
    int pivotIndex = low + rand() % (high - low + 1);
    swap(a[pivotIndex], a[high]);
    int pivot = partition(a, low, high);
    quickSort(a, low, pivot - 1);
    quickSort(a, pivot + 1, high);
}
16 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.