AlgoVerse

Quick sort

Take the last item as the pivot, move smaller items to its left and larger ones to its right, then sort each side recursively.

Quick sort is also "divide and conquer", but it does the main work before recursing:

Read the full explanation ↓
Input:
n=8PDF export

Eight mixed numbers with 4 as the first pivot; 15 comparisons.

  1. def quick_sort(a):
  2. sort(a, 0, len(a) - 1)
  3. return a
  6. def sort(a, lo, hi):
  7. if lo >= hi:
  8. return
  9. p = partition(a, lo, hi)
  10. sort(a, lo, p - 1)
  11. sort(a, p + 1, hi)
  14. def partition(a, lo, hi):
  15. pivot = a[hi]
  16. i = lo - 1
  17. for j in range(lo, hi):
  18. if a[j] <= pivot:
  19. i = i + 1
  20. a[i], a[j] = a[j], a[i]
  21. a[i + 1], a[hi] = a[hi], a[i + 1]
  22. return i + 1

Invariant: In the partition loop: every item in a[lo..i] is ≤ pivot and every item in a[i+1..j−1] is > pivot.

Start

2081721334556647

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

Orange = changed in this step

a list

28713564

Call stack

  1. quick_sort()line 1
Step 1 of 124
Black = pivot · Orange = key stepcompare: 0/15 · swap: 0/9 · pivot: 0/5 · place: 0/5

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • swaps
    • place
    • current input (n=8)
    020406046810121416n = number of itemscomparisonsswapsplace
    Show as a table
    ncomparisonsswapsplace
    44.72.52.3
    69.84.43.6
    817.48.35.1
    1025.514.26.6
    1232.417.87.5
    1441.324.38.8
    1652.529.210.6
    Explanation

    The idea

    Quick sort is also "divide and conquer", but it does the main work before recursing:

    1. Pick a pivot; here it is the last item of the range, a[hi].
    2. Partition the range: items ≤ pivot go left, the rest go right, and the pivot lands between them in its final place.
    3. Sort both sides of the pivot recursively. No combining is needed, because the array is sorted in place.

    Partitioning (Lomuto's scheme)

    i marks the end of the "small" part. j walks from lo to hi − 1; whenever a[j] ≤ pivot, i moves up one and a[i] and a[j] are swapped. At the end, the pivot is swapped with a[i + 1].

    Cost

    • If each pivot splits its range roughly in half, the recursion is log n deep and the time is O(n log n). This is also the average case.
    • If the pivot is always the largest or smallest item (for example on a sorted array), one side stays empty and the time becomes O(n²).
    • Repeated items also give unbalanced splits with this scheme; see the "all equal" input.
    • A random pivot makes the bad case unlikely, but here the pivot is fixed (the last item) so every run is the same.

    What to watch in the trace

    • pivot is written above the array and the blue band is the range lo..hi. The i and j arrows are the borders of the partition.
    • In the "recursion tree", compare the shape for the best case and the worst case: one wide and short, the other a long chain.