SUNY Geneseo Department of Computer Science

Performance of Quicksort

Return to List of Lectures

Questions?

Finding most and least swaps in lab?

• Check text animation prints to see if pivot might swap with itself - look for "exchange," "pivot moves..."

Quicksort's Performance

Section 10.3

• Best and worst cases, finding closed forms
• Best case: Θ(n logn) when low and high halves equal in size
• Worst case = Θ(n²) when the two halves are radically unequal
• Finding closed form for best case
  • Restrict domain of recurrence - usually OK
    • n = 2ⁱ - 1

• Substitution - solve recurrence in terms of i
  • Rewrite solution in terms of i in terms of n

Is there an easier way to deduce any of the closed forms?

• Master Theorem!
• Best case recurrence
  • C(n) = (n-1) + 2C( (n-1)/2 )
  • a = b = 2
  • g(n) = n-1
  • n^log_ba = n¹ = n = Θ(n)
  • Second case applies
  • f(n) = Θ( n^log_ba logn )
    • = Θ( n logn )
• Worst case?
  • Trick question! Master Theorem doesn't apply unless b > 1

Can Quicksort's worst case be avoided/improved?

• When does worst case happen?
  • First element (pivot) is largest or smallest
  • Generally, if array is already sorted or exactly out of order
• Fixes
  • Scan for sortedness?
  • Scan elements and pick "middle" as pivot
    • "Median of three"
  • Pick random element as pivot

Next

A sorting algorithm with a fast worst case

Read sections 10.4.1 and 10.4.2