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.

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.

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)