Description

anay07

opened on Dec 7, 2017

Issue body actions

DESCRIPTION

Randomized version of quicksort is mostly implemented in real life and is missing in the repo as it is the randomized quicksort which gives it the worst case O(nlogn) complexity and not the naive implementation.

STEPS TO REPRODUCE

EXPECTED OUTCOME

Code of randomized quicksort will be added.

ACTUAL OUTCOME

Proposed Solution [optional]

I will like to add the randomized quicksort in the quicksort folder.

Activity

1. prateekiiest commented on Dec 7, 2017

   

   prateekiiest

   on Dec 7, 2017

   Member

   More actions

   @anay07 , it would be better if you can show me some graph of this randomized quick sort
2. prateekiiest

   added

   enhancement

   kwoc

   on Dec 7, 2017
3. anay07 commented on Dec 7, 2017

   

   anay07

   on Dec 7, 2017

   Author

   More actions

   @prateekiiest ,In randomized quicksort chooses the pivot at random (and also can shuffle the array at start) .

   Doing this can some significant change as shown in below graphs
   Here are some comparison graphs for different input cases :
   1)Sorted(Reverse)
   
   
   We can see there is significant difference in this case

   2)Sorted
   
   
   We can see the difference is not so significant in this case
4. prateekiiest commented on Dec 8, 2017

   

   prateekiiest

   on Dec 8, 2017

   Member

   More actions

   How about considering the distribution of the elements of the array?
   say quick sort on array of a normal distribution and on an array of uniform distribution ?

   Both cases let Pivot choice be random.
5. prateekiiest

   added

   maths

   on Dec 8, 2017
6. prateekiiest commented on Dec 29, 2017

   

   prateekiiest

   on Dec 29, 2017

   Member

   More actions

   @anay07 did you send a PR for this ?
7. anay07 commented on Dec 30, 2017

   

   anay07

   on Dec 30, 2017

   Author

   More actions

   Not till now as I was not assigned the same .
   Also I found that quicksort will not be affected by the distribution ( unless there are many duplicated values or if we know the range of distribution of number (as we can use bucket sort in this case which is faster than quicksort) )
8. vasugr commented on Dec 5, 2018

   

   vasugr

   on Dec 5, 2018

   More actions

   I would like to contribute to this.

Issue actions