Summary - Quick sort

Implement quick sort and print the result.

Summary - Quick sort

Quick sort: pick a pivot, partition, recursively sort. In-place, O(log n) extra memory (stack). Good pivot gives average O(n log n), bad pivot gives O(n^2).

Not stable. Very fast in practice; on small subarrays a hybrid with insertion sort is common.

Pivot choice is the key to performance: random or median-of-three are safe picks.

Exercise Summary: quick sort

Write quick_sort(arr, lo, hi). Print [1, 1, 2, 3, 4, 5, 9] with arr=[3,1,4,1,5,9,2]; quick_sort(arr,0,6); print(arr).

Show example solution

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1
def quick_sort(arr, lo, hi):
    # Partition and recurse
    if lo >= hi:
        return
    p = partition(arr, lo, hi)
    quick_sort(arr, lo, p - 1)
    quick_sort(arr, p + 1, hi)
arr = [3, 1, 4, 1, 5, 9, 2]
quick_sort(arr, 0, 6)
print(arr)

Test yourself

Summary - Quick sort: match the terms

Pivot

Partition axis
Partition

O(n)
Average

O(n log n)
Worst case

O(n^2)

Memory cost

Extra memory: O(____)

Show answer

Extra memory: O(log n)

Is quick sort stable?
- No
- Only on small arrays
- Only with a good pivot
- Yes, always
Show answer

No — No

Next lesson: What is a heap?

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies