Quick sort Worst case

user_487026 0
Viewed 85009

I'm working on the program just needed in the following to understand it better.

What is the worst case running time for Quicksort and what may cause this worse case performance? How can we modify quicksort program to mitigate this problem?

I know that it has worst case O(n^2) and I know it occurs when the pivot unique minimum or maximum element. My question is how can I modify the program to mitigate this problem.

A good algorithm will be good.

quicksort big-o algorithm
6 Answers

The worst case running time depends on the partition method within quick-sort. That has two aspects:

  • selecting the pivot
  • how to partition around the pivot

Good strategies to select the pivot have been outlinied in previous posts (median of medians, or median of three or randomization). But even if the pivot is wisely selected, in the extreme, if an array has all equal elements it will lead to worst case runtime if only two partitions are built, because one will carry the equal elements, that is all elements:

  • this causes partion to be called n times, each of it taking n/2 in average leading to O(n²)
  • this is not good, because it's not a theoretical worst case scenario but a quite common one
  • note that it is not solved by detecting the empty partition, because the pivot could have the highest or lowest element value (e.g. median is 5 which is as well the highest element value, but there might still be a few misplaced < 5 values)

A way around this problem is to partition into three partitions, a lower (elements < pivot), an equal (elements = pivot) and an upper partition. The "=pivot elements" are in their final position. Lower and upper partition needs still to be sorted if not empty.

Together with randomization, median of medians or some combination to select a pivot a worst case scenario is quite rare but not impossible, which leaves the algorithm with a worst case upper bound of O(n²).

user_69263200

The question I wonder is frequently asked. AFAI research there are 2 keys of its worstness.

  • If array is already sorted no matter ascending or descending in addition to selecting pivot as minimum(smallest) or maximum(greatest) element of the list. [2,3,4] or [4,3,2]
  • If all elements are same. [2,2,2]
user_49906420
Related