Quick sort Worst case

by

Quicksort’s performance is dependent on your pivot selection algorithm. The most naive pivot selection algorithm is to just choose the first element as your pivot. It’s easy to see that this results in worst case behavior if your data is already sorted (the first element will always be the min).

There are two common algorithms to solve this problem: randomly choose a pivot, or choose the median of three. Random is obvious so I won’t go into detail. Median of three involves selecting three elements (usually the first, middle and last) and choosing the median of those as the pivot.

Since random number generators are typically pseudo-random (therefore deterministic) and a non-random median of three algorithm is deterministic, it’s possible to construct data that results in worst case behavior, however it’s rare for it to come up in normal usage.

You also need to consider the performance impact. The running time of your random number generator will affect the running time of your quicksort. With median of three, you are increasing the number of comparisons.

More Related Contents:

  1. Quicksort superiority over Heap Sort
  2. complexity in terms of big O
  3. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  4. time complexity of recursion function
  5. Big O, how do you calculate/approximate it?
  6. What does O(log n) mean exactly?
  7. Constant Amortized Time
  8. What exactly does big Ө notation represent?
  9. Can hash tables really be O(1)?
  10. Why is the constant always dropped from big O analysis?
  11. Is log(n!) = Θ(n·log(n))?
  12. How can building a heap be O(n) time complexity?
  13. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  14. Big-O for Eight Year Olds? [duplicate]
  15. Which algorithm is faster O(N) or O(2N)?
  16. Why is quicksort better than mergesort?
  17. Quicksort: Choosing the pivot
  18. Time complexity of Euclid’s Algorithm
  19. What is pseudopolynomial time? How does it differ from polynomial time?
  20. Computing set intersection in linear time?
  21. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  22. Worst case for QuickSort – when can it occur?
  23. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  24. Why do we ignore co-efficients in Big O notation?
  25. Big O when adding together different routines
  26. Time Complexity of two for loops [duplicate]
  27. Print the biggest K elements in a given heap in O(K*log(K))?
  28. Difference between Big-Theta and Big O notation in simple language
  29. Why is bubble sort O(n^2)?
  30. Why is Insertion sort better than Quick sort for small list of elements?

Leave a Comment