CODEWITHSUNDEEP
algorithmsortingquicksort
RIchard Williams
RIchard Williams

Reputation: 557

A basic confusion on quicksort

Suppose we choose a pivot as the first element of an array in case of a quicksort. Now the best/worst case complexity is O(n^2) whereas in average case it is O(nlogn). Is not it weird (best case complexity is greater than worst case complexity)?

Upvotes: 0

Views: 242

Answers (2)

ultddave
ultddave

Reputation: 198

The best-case of quicksort 0(nlogn) is when the chosen pivot splits the subarray in two +- equally sized parts in every iteration.

Worst-case of quicksort is when the chosen pivot is the smallest element in the subarray, so that the array is split in two parts where one part consists of one element (the pivot) and the other part of all the other elements of the subarray.

So choosing the first element as the pivot in an already sorted array, will get you 0(n^2). ;)

Therefore it is important to choose a good pivot. For example by using the median of the first, middle and last element of the subarray, as the pivot.

Upvotes: 0

manub
manub

Reputation: 4100

The best case complexity is O(nlogn), as the average case. The worst case is O(n^2). Check http://en.wikipedia.org/wiki/Quick_sort.

While other algorithms like Merge Sort and Heap Sort have a better worst case complexity (O(nlogn)), usually Quick Sort is faster - this is why it's the most common used sorting algorithm. An interesting answer about this can be found at Why is quicksort better than mergesort?.

Upvotes: 3

Related Questions