[Haskell-beginners] Re: randomize the order of a list

John Dorsey haskell at colquitt.org
Wed Sep 1 17:59:57 EDT 2010

Gabriel Scherer wrote:

>> Thanks for the link apfelmus, it's fairly interesting. The key to
>> making it work is the weighting of lists during merging based on their
>> lengths. I wonder if other sort algorithm can be adapted in such a
>> way, while preserving uniformity. Quicksort for example : is it enough
>> to choose the result position of the pivot randomly, and then placing
>> elements on either side with a probability of 1/2 ?

to which Heinrich Apfelmus answered:

> Interesting question! Adapting quick sort is not that easy, though.
> First, you can skip choosing the pivot position because it is already  
> entailed by the choices of elements left and right to it.

I don't think this is true...

> Second, probability 1/2 won't work, it doesn't give a uniform  
> distribution.

... because of this.

In fact, it appears to me that the proposed modification to quicksort is
uniform and simple.  Why do you think otherwise?


More information about the Beginners mailing list