Worst case for QuickSort – when can it occur?

by

I think people are confusing Quicksort the partition-based sorting algorithm, and “qsort” the various library implementations.

I prefer to see Quicksort the algorithm as having a pluggable pivot selection algorithm, which is quite essential in analyzing its behavior.

If the first element is always chosen as the pivot, then an already sorted list is the worst-case. Often there’s a high probability that the array is already/nearly sorted, so this implementation is rather poor.

Analogously, selecting the last element as the pivot is bad for the same reason.

Some implementations tries to avoid this problem by choosing the middle element as the pivot. This would not perform as badly on already/nearly sorted arrays, but one could still construct an input that would exploit this predictable pivot selection and make it run in quadratic time.

Thus, you get randomized pivot selection algorithms, but even this doesn’t guarantee O(N log N).

So other algorithms were developed that would use some information from the sequence before picking a pivot. You can of course scan the whole sequence and find the median, and use that as the pivot. This guarantees O(N log N), but of course slower in practice.

So some corners are cut, and people devised the median-of-3 algorithm. Of course, later even this was exploitable by the so-called median-of-3 “killer”.

So more attempts are made at coming up with more “intelligent” pivot selection algorithms that guarantees O(N log N) asymptotic behavior that is still fast enough to be practical, with varying degree of success.

So really, unless one specifies a particular implementation of Quicksort, the question of when the worst case scenario occurs is ill-defined. If you use the so-called median-of-medians pivot selection algorithm, there is no quadratic worst-case scenario.

Most library implementations, however, are likely to forfeit O(N log N) guarantee for much faster sorting in the average case. Some of the really old implementations use the first element as the pivot, which is now well-understood as poor and is no longer a practice widely followed.

More Related Contents:

  1. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  2. Why is quicksort better than mergesort?
  3. Quicksort: Choosing the pivot
  4. Quick sort Worst case
  5. Quicksort: Iterative or Recursive
  6. median of three values strategy
  7. Quicksort vs heapsort
  8. Quicksort superiority over Heap Sort
  9. Why is Insertion sort better than Quick sort for small list of elements?
  10. Algorithm to find Largest prime factor of a number
  11. Roulette wheel selection algorithm [duplicate]
  12. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  13. Calculating mid in binary search
  14. Geo Fencing – point inside/outside polygon
  15. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  16. Box stacking problem
  17. How to design an algorithm to calculate countdown style maths number puzzle
  18. What are good examples of genetic algorithms/genetic programming solutions? [closed]
  19. How can I programmatically determine how to fit smaller boxes into a larger package? [closed]
  20. How do I find a factorial? [closed]
  21. Creating a random number generator from a coin toss
  22. What is a loop invariant?
  23. How to express tetration function, for complex numbers
  24. Why does the greedy coin change algorithm not work for some coin sets?
  25. Why DFS and not BFS for finding cycle in graphs
  26. Algorithm to simplify a weighted directed graph of debts
  27. Compute the area of intersection between a circle and a triangle?
  28. Unbiased random number generator using a biased one
  29. maximum subarray of an array with integers [duplicate]
  30. CUDA stream compaction algorithm

Leave a Comment