I am 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 miggate 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.
Thanks
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.
An easy modification is to choose the pivot randomly. This gives good results with high probability.
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.