Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the worst case scenario for quicksort?

When does the quicksort algorithm take O(n^2) time?

like image 789
NoodleOfDeath Avatar asked Jan 29 '11 02:01

NoodleOfDeath


People also ask

What is the best and worst case for quicksort?

The best-case time complexity of quicksort is O(n*logn). Average Case Complexity - It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of quicksort is O(n*logn).

Which scenario quicksort gives best case complexity?

Quick Sort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array. If pivot element divides the array into two equal half in such a scenario, quick sort takes the least time sort, that is, best case time complexity.

Which of the following is the most suitable scenario for Quicksort?

A condition for the best case for Quicksort is that the pivot always goes right smack in the middle (except perhaps in the very last stages), so much is definitely correct.


1 Answers

Quicksort works by taking a pivot, then putting all the elements lower than that pivot on one side and all the higher elements on the other; it then recursively sorts the two sub groups in the same way (all the way down until everything is sorted.) Now if you pick the worst pivot each time (the highest or lowest element in the list) you'll only have one group to sort, with everything in that group other than the original pivot that you picked. This in essence gives you n groups that each need to be iterated through n times, hence the O(n^2) complexity.

The most common reason for this occurring is if the pivot is chosen to be the first or last element in the list in the quicksort implementation. For unsorted lists this is just as valid as any other, however for sorted or nearly sorted lists (which occur quite commonly in practice) this is very likely to give you the worst case scenario. This is why all half-decent implementations tend to take a pivot from the centre of the list.

There are modifications to the standard quicksort algorithm to avoid this edge case - one example is the dual-pivot quicksort that was integrated into Java 7.

like image 132
Michael Berry Avatar answered Oct 24 '22 06:10

Michael Berry