quicksort probabilistic guarantee

[miczal]

Hi,
I think your implementation of quicksort lacks randomizing of the input. If you shuffle it, you are almost guaranteed to not have O(n^2) time scenario.

[AnupKumarPanwar]

What does randomization of input means? We are taking data from user input and of course that will be random. Please elaborate your suggestion.

[miczal]

Before quicksort you should just shuffle the input array, so that you avoid worst-case scenario.
Consider this - If you have already sorted input, then you encounter O(n^2) scenario, but if you shuffle the array before passing it to the sorting algorithm, then it is MUCH more likely to be O(n log n).

I think that this should be fine.

from random import shuffle
def quick_sort(collection):
    shuffle(collection)
    quick_sort_impl(collection)

[harshildarji]

@miczal
Hi, This is an open-source repository and anyone can make a pull request with the changes that can improve the performance of the algorithm. If you find a way to improve the performance, we request you to make a pull request.

[AnupKumarPanwar]

Thanks for appreciating the Organisation