1. Concept library
  2. Data Structures & Algorithms
  3. Module 7: Sorting

Concept

Quicksort

Quicksort picks a pivot, partitions the array into smaller and larger elements around it, and sorts each side. It is O(n log n) on average and sorts in place, but a bad pivot makes it O(n^2).

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain partitioning around a pivot and why the average is O(n log n)
  2. Write a partition step and trace it on a short array
  3. Spot the pivot choice that degrades sorted input to O(n^2)

In practice

A few lines that show Quicksort doing its job.

Python
import random

def quicksort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return
    pivot = a[random.randint(lo, hi)]
    i, j = lo, hi
    while i <= j:
        while a[i] < pivot: i += 1
        while a[j] > pivot: j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]; i += 1; j -= 1
    quicksort(a, lo, j); quicksort(a, i, hi)

The common mistake

Watch for

Always choosing the first or last element as the pivot. On already sorted input every partition is lopsided and the sort degrades to O(n^2) with recursion as deep as the array.

What to know first

Your roadmap puts these before Quicksort, unless you already know them.

How it stays learned

Once a session shows you understand Quicksort, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Merge sort