CODEWITHSUNDEEP
algorithmbig-oquicksort
John
John

Reputation: 531

Quick sort Worst case

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.

Upvotes: 34

Views: 86737

Answers (6)

Soner from The Ottoman Empire
Soner from The Ottoman Empire

Reputation: 20901

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]

Upvotes: 0

Chris K
Chris K

Reputation: 31

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²).

Upvotes: 3

theReverseFlick
theReverseFlick

Reputation: 6044

Worst Performance Condition:

When each time pivot chosen is 'greatest' or 'smallest' and this pattern repeats

So for 1 3 5 4 2

If pivots are chosen in order 1,2,3,4,5 Or 5,4,3,2,1

then the worst case running time is O(n*n)

How avoid the worst case:

(1)Divide the array into five sets.So if 1..100 the sets are (1..20) (21..40) (41..60) (61..80) (81..100)

(2)Choose median of first five elements in each of set so (3) (23) (43) (63) (83)

(3)Now choose the median among them as the pivot so here its (43)

Upvotes: 12

Niki Yoshiuchi
Niki Yoshiuchi

Reputation: 17551

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.

Upvotes: 38

Gabe Moothart
Gabe Moothart

Reputation: 32082

An easy modification is to choose the pivot randomly. This gives good results with high probability.

Upvotes: 6

Burton Samograd
Burton Samograd

Reputation: 3638

It's been a while, but I think the worst case for quicksort was when the data was already sorted. A quick check to see if the data is already sorted could help alleviate this problem.

Upvotes: 4

Related Questions