Quick sort Worst case

Question

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.

Interplanetary

Also, you should watch out for repeated elements. For instance, if all of the elements are equal in the array being sorted, it can cause worst-case behavior depending on the quicksort. – Norvall

is this homework? no problem if it is, but you might want to tag it as such. – Gittel

Answer 1

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.

Inbred

Answer 2

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)

Waler

Answer 3

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

Messuage

Answer 4

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.

Lyceum

No, not really. For already sorted data it'll work just fine. – Bank

@Nikita: in the simplest, most basic naive quicksort, the pivot is the first element. Already-sorted data is the worst case number of comparisons for that version (or reverse-sorted data). – Garner

The worst case is an already sorted array but I think even if you check whether it is already sorted or not, there will be some "almost sorted" arrays and they will be "almost worst cases". – Mcminn

Answer 5

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

Semiprofessional

Answer 6

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]

Pitfall