quicksort probabilistic guarantee #13

Activity

1. AnupKumarPanwar commented on Aug 9, 2016

   

   AnupKumarPanwar

   on Aug 9, 2016

   Member

   More actions

   What does randomization of input means? We are taking data from user input and of course that will be random. Please elaborate your suggestion.
2. miczal commented on Aug 9, 2016

   

   miczal

   on Aug 9, 2016

   ContributorAuthor

   More actions

   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)
   
3. harshildarji commented on Aug 11, 2016

   

   harshildarji

   on Aug 11, 2016

   Member

   More actions

   @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.
4. AnupKumarPanwar commented on Aug 13, 2016

   

   AnupKumarPanwar

   on Aug 13, 2016

   Member

   More actions

   Thanks for appreciating the Organisation
5. AnupKumarPanwar

   closed this as completedon Aug 13, 2016
6. poyea

   added a commit that references this issue on Jul 8, 2019

   Project Euler Problem #13 Python Solution (#935)

   ...

   32d5c1a
7. stokhos

   added a commit that references this issue on Jan 3, 2021

   Project Euler Problem TheAlgorithms#13 Python Solution (TheAlgorithms…

   ...

   d1033a8