Monday, June 28, 2010

Quicksort is O(n log n) in average. How about worst case?

Surprisingly enough, there are still people who are not aware that Quicksort is O(n log n ) in average. How can we make it O(n log n) in the worst case?

8 comments:

  1. Use IntroSort (http://en.wikipedia.org/wiki/Introsort)

    ReplyDelete
  2. Introsort - http://en.wikipedia.org/wiki/Introsort

    ReplyDelete
  3. and without going in that direction?

    ReplyDelete
  4. Does parallelizing the operations count as making it better ?

    ReplyDelete
  5. OK. Randomized Quick Sort provides you an expected case runtime of O(nlgn). The reason why this is expected as against worst case is that there is always a possibility of picking up a bad pivot regardless of how random your selection is.

    Thinking is if I can guarantee that my pivot selection will never be the bad one, I can guarantee worst case run time of O(nlgn) for Quick Sort. How can I guarantee that my pivot selection will never be a bad one? Thinking is using something like the "Median of Medians algorithm" to pick the pivot.

    Would the above be a valid answer?

    ReplyDelete