Quick Sort, Partitioning and Quickselect
32 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Quick sort wins in practice by sorting in place with one simple step: partition around a pivot. The same step gives quickselect, which finds the k-th value without sorting everything.
Pick a pivot, split around it
Quick sort is a divide and conquer sort that picks a pivot, partitions the list so smaller values come before it and larger values after it, then sorts the two sides the same way.
Choose one value, the pivot. Put smaller values on its left and larger values on its right. The pivot is then in its final place, and each side is sorted the same way.
def quick_sort(items): if len(items) <= 1: return items pivot = items[len(items) // 2] smaller = [x for x in items if x < pivot] equal = [x for x in items if x == pivot] larger = [x for x in items if x > pivot] return quick_sort(smaller) + equal + quick_sort(larger)Example 1 · Quick sort with a trace
def quick_sort(items): if len(items) <= 1: return items pivot = items[len(items) // 2] smaller = [x for x in items if x < pivot] equal = [x for x in items if x == pivot] larger = [x for x in items if x > pivot] print("pivot", pivot, smaller, equal, larger) return quick_sort(smaller) + equal + quick_sort(larger)
print(quick_sort([7, 2, 9, 4, 3, 8, 5]))pivot 4 [2, 3] [4] [7, 9, 8, 5] pivot 3 [2] [3] [] pivot 8 [7, 5] [8] [9] pivot 5 [] [5] [7] [2, 3, 4, 5, 7, 8, 9]
What this code does
- Each line shows one split: the values below the pivot, equal to it, and above it.
- The equal group is never split again, so repeated values make the sort faster.
This version is the easiest to read in Python, but it builds new lists. Values equal to the pivot stay together, so many duplicates cause no trouble.
Partitioning in place
Partition is the step that rearranges part of a list around a pivot so that every value before the pivot is not larger and every value after it is larger, and returns where the pivot ends.
To save memory, rearrange the list itself. Scan with j; every value not larger than the pivot is swapped into the growing small zone that ends at i. Finally the pivot swaps into place.
def partition(a, lo, hi): pivot = a[hi] i = lo for j in range(lo, hi): if a[j] <= pivot: a[i], a[j] = a[j], a[i] i += 1 a[i], a[hi] = a[hi], a[i] return iExample 2 · One partition
def partition(a, lo, hi): pivot = a[hi] i = lo for j in range(lo, hi): if a[j] <= pivot: a[i], a[j] = a[j], a[i] i += 1 a[i], a[hi] = a[hi], a[i] return i
marks = [7, 2, 9, 4, 3, 8, 5]p = partition(marks, 0, len(marks) - 1)print(p, marks)3 [2, 4, 3, 5, 9, 8, 7]
What this code does
- The pivot 5 ends at index 3. Everything on its left is at most 5 and everything on its right is larger.
- The two sides are not sorted yet, only separated.
Example 3 · Quick sort in place
def partition(a, lo, hi): pivot = a[hi] i = lo for j in range(lo, hi): if a[j] <= pivot: a[i], a[j] = a[j], a[i] i += 1 a[i], a[hi] = a[hi], a[i] return i
def quick_sort(a, lo, hi): if lo < hi: p = partition(a, lo, hi) quick_sort(a, lo, p - 1) quick_sort(a, p + 1, hi)
prices = [29, 10, 14, 37, 13, 5, 41]quick_sort(prices, 0, len(prices) - 1)print(prices)[5, 10, 13, 14, 29, 37, 41]
What this code does
- The list is sorted by swaps only, so no new lists are made.
- The bounds
loandhiare inclusive, which is why the recursive calls usep - 1andp + 1.
It returns the pivot position. One scan, O(n) time, O(1) extra space. This is the Lomuto scheme; it is the shortest to write in an interview.
Worst case and the pivot choice
If the pivot is always the smallest or largest value, one side is empty and the work is O(n squared). That happens with the last item as pivot on a sorted list. A random or middle pivot makes it rare.
import random
def quick_sort(a, lo=0, hi=None): if hi is None: hi = len(a) - 1 if lo < hi: r = random.randint(lo, hi) a[r], a[hi] = a[hi], a[r] p = partition(a, lo, hi) quick_sort(a, lo, p - 1) quick_sort(a, p + 1, hi)Example 4 · Bad pivot against good pivot
work = 0
def quick_sort(items, pick): global work if len(items) <= 1: return items work += len(items) pivot = items[pick(items)] smaller = [x for x in items if x < pivot] larger = [x for x in items if x > pivot] return quick_sort(smaller, pick) + [pivot] + quick_sort(larger, pick)
data = list(range(200))quick_sort(data, lambda items: len(items) - 1)print("last item as pivot:", work)work = 0quick_sort(data, lambda items: len(items) // 2)print("middle item as pivot:", work)last item as pivot: 20099 middle item as pivot: 1280
What this code does
- On a sorted list, the last item is the largest, so every split leaves one side empty and the work is about n squared / 2.
- The middle item halves the list each time, so the work is near n log n. Random pivots avoid the trap on any input.
Swapping a random item to the end first makes bad splits unlikely. The average time is O(n log n); the stack is O(log n) on average. Quick sort is not stable.
Quickselect: the k-th smallest
Quickselect is a way to find the k-th smallest value by partitioning around a pivot and continuing in only the one side that holds position k, which gives O(n) time on average.
To find the k-th smallest you need not sort everything. After partitioning, the pivot is in its final place, so keep only the side that contains position k. Average time is O(n).
import random
def quickselect(items, k): pivot = random.choice(items) smaller = [x for x in items if x < pivot] equal = [x for x in items if x == pivot] if k < len(smaller): return quickselect(smaller, k) if k < len(smaller) + len(equal): return pivot larger = [x for x in items if x > pivot] return quickselect(larger, k - len(smaller) - len(equal))Example 5 · Quickselect: smallest, third smallest and median
import random
def quickselect(items, k): pivot = random.choice(items) smaller = [x for x in items if x < pivot] equal = [x for x in items if x == pivot] if k < len(smaller): return quickselect(smaller, k) if k < len(smaller) + len(equal): return pivot larger = [x for x in items if x > pivot] return quickselect(larger, k - len(smaller) - len(equal))
marks = [64, 34, 25, 12, 22, 11, 90]print(quickselect(marks, 0))print(quickselect(marks, 2))print(quickselect(marks, len(marks) // 2))11 22 25
What this code does
- Index 0 is the smallest and index 3 is the median of 7 values.
- On average each round keeps about half the list, so the work is n + n/2 + n/4 + ... which is O(n).
Example 6 · Python tools for the k-th value
import heapq
scores = [72, 95, 64, 88, 91, 55, 79]print(sorted(scores)[2])print(heapq.nsmallest(3, scores)[-1])print(heapq.nlargest(2, scores)[-1])72 72 91
What this code does
- All three give an answer without writing quickselect. Sorting is O(n log n); the heap functions are O(n log k).
- Hand-written quickselect is what an interview asks for when it wants O(n) on average.
Here k counts from 0, so k = 0 is the smallest. The answer never depends on which pivot is picked, only the speed does.
Next step
Check your understanding
11 quick questions