top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

When can worst case scenario of Quicksort can occur?

+2 votes
414 views
When can worst case scenario of Quicksort can occur?
posted Nov 30, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases.

1) Array is already sorted in same order.
2) Array is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2)

Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.

Source: http://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/

answer Dec 1, 2013 by Salil Agrawal
Similar Questions
+1 vote

I want to know the usage of QuickSort and randomized QuickSort.
Please help me when to use what?

+2 votes

Say we only know the worst case and best case complexity of an algo (Algo is not known). Is it possible to get the average case complexity?

...