can u give me an example array of the best case of quick sort?
I do understand that the best case of quick sort is when the elements are already in the pivot place., and that the complexity is O(n logn), but i m just not able to come up with a large array, that fits this condition perfectly.

3
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by firstPerson

The best cast for quicksort is an already sorted array when the implementation checks for an already sorted subset. In such a case, no partitioning takes place and no recursive calls are made, which results in linear complexity:

``````function quicksort(a, first, last)
if is_sorted(a, first, last) then
return
end if

pivot := partition(a, first, last)

quicksort(a, first, pivot - 1)
quicksort(a, pivot + 1, last)
end function``````

Assuming the original quicksort algorithm with no improvements, the best case is an even partitioning in all steps, which is O(N log N).

i m just not able to come up with a large array, that fits this condition perfectly

The dependency is your partitioning scheme, so to create an array that fits the best case, you need both a deterministic partitioning scheme (ie. random pivots will need to be mocked) and an array that gets partitioned perfectly each time. Without knowing your partitioning algorithm, I can't really offer much more advice than that.

Votes + Comments
And that about covers it...

Hint: Use your pivot algorithm to work from the bottom up instead of top down

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.