0

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
6 Years
Discussion Span
Last Post by firstPerson
1

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...
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.