4

Can anyone explain why the worst-case runtime for quicksort is O(n^2) and why this is rare?

John Smith
  • 11,678
  • 17
  • 46
  • 51
  • IIRC, worst case for QS is an already ordered list. But, a search engine is your friend (wikipedia defines it nicely). – KevinDTimm Apr 12 '13 at 18:08
  • @KevinDTimm That depends on the pivot selection. The worst case is one which drives the pivot selection to *always* choose either the largest or smallest value in the list. Naive pivot selection can do that on a pre-sorted list. John, can you see why the pivot selection is so important? – dmckee --- ex-moderator kitten Apr 12 '13 at 18:10
  • @dmckee I don't really understand how the pivot matters because either way we're appending each element to either a Left list or a Right list and then recursing on both – John Smith Apr 12 '13 at 18:14
  • @John The critical question is "How long are the two lists?". To get O(N log N) performance you need to divide the work up between the two sides roughly evenly. With a bad choice of pivot you can end with one list that contains 1 item and the other that contains the remaining items. Then you need O(N) passes, and each one involves O(N) comparisons. Try working it by hand with 5 or 6 items to get a feel for it. – dmckee --- ex-moderator kitten Apr 12 '13 at 18:43
  • @dmckee Whether I split in the middle or split near an end, isn't that just compensating? Ultimately I have to "touch" all the elements and where I split the data won't change that – John Smith Apr 12 '13 at 18:51
  • Count the number of passes you make when splitting evenly or worst case. The thing that makes fast sorts is that they "divide and conquer". With a optimal pivot you can do 8 items in 3 passes. With a wort case pivot it takes 7 passes. With 32 items it's 4 and 15. 32 items means 5 or 31. And so on. – dmckee --- ex-moderator kitten Apr 12 '13 at 18:59
  • 8 items in three passes? Pivot=5, left=1234, right=678. pivot=3, left=12, right=4. pivot=2, left=1, right=empty. pivot=7, left=6, right=8. I count 4 here? – John Smith Apr 12 '13 at 19:02

1 Answers1

11

If the pivot is chosen in the worst way every time, rather than partitioning into two lists of size n/2, it will partition into one of size 1 and one of size n-1. This leads to a recursion depth of n and an n^2 total time.

This is rare because the pivot is normally chosen randomly, so the chances of picking the worst pivot every time are small, and on average the pivot will tend to split the list roughly in half.

If the pivot were chosen non-randomly, such as taking the first element, then certain inputs (pre-sorted or reverse-sorted lists) can force n^2 performance.

Ryan M
  • 2,072
  • 11
  • 14
  • So is the best pivot a random one (if you know nothing about the list's order going in?) – John Smith Apr 12 '13 at 18:15
  • @JohnSmith: The "best pivot" is more likely to be the median of 3 samples, rather than a random sample. This decreases the probability that you're randomly choosing the worst pivot... I hope you've moved on to other problems. :P – Eric McLachlan May 27 '21 at 08:29