Randomised Quicksort and Expected Running Time · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Quicksort without the worst case

Computing · Algorithms & Data Structures · ages 19-20
Name ______________________   Date ____________

  1. What is the invariant of the classic partition loop?

    • Everything left of finger q is smaller than the pivot
    • Finger j never moves
    • The pivot stays at the first position

  2. What does the partition step do?

    • Sorts the whole array at once
    • Rearranges items so smaller ones sit left of the pivot and bigger ones right
    • Picks a random number and stops

  3. A sorted input makes fixed-pivot quicksort shrink the problem by only one item per round.

    Circle one:   True   False

  4. In the worst case, rounds cost 5, 4, 3, 2, then 1 comparisons. Type the total.

    Answer: ______________

  5. Why is that shrinking pattern quadratic?

    • Each round costs one step only
    • The work adds up like 1 plus 2 up to n
    • The pivot changes size

  6. What does picking the pivot at random change?

    • Bad cases become bad luck that no input can force
    • The algorithm becomes always faster than merge sort
    • Partitioning needs no comparisons

  7. Partitioning scans its section once, doing work proportional to its length.

    Circle one:   True   False

  8. Which claim about randomised quicksort is wrong?

    • Its expected time is n log n over the random picks
    • No input can force the worst case
    • Its quadratic worst case disappears entirely
LightMySky · lightmysky.comW1-mt_fcKF7zfzpX-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Quicksort without the worst case W1-mt_fcKF7zfzpX-s1

  1. Everything left of finger q is smaller than the pivot · Finger q always marks the end of the small region.
  2. Rearranges items so smaller ones sit left of the pivot and bigger ones right · Partition splits the array around the pivot for the recursive calls.
  3. True · Every pivot lands at an end, leaving one side empty.
  4. 15 · Five plus four plus three plus two plus one is 15.
  5. The work adds up like 1 plus 2 up to n · Round costs of n, n minus 1, and so on sum to order n squared.
  6. Bad cases become bad luck that no input can force · Randomness moves the worst case from the input to the dice.
  7. True · One pass with constant work per item is linear.
  8. Its quadratic worst case disappears entirely · Unlikely is not impossible: the worst case still exists.
Worksheet · LightMySky