[PD] Shuffling arrays

[Mathieu Bouchard]

On Tue, 5 Oct 2010, Claude Heiland-Allen wrote:

> The same way that it's a really bad way to sort - maybe it could be classed 
> as a bogobubblesort.

That sort is still just O(n²) in time, isn't it ? And it can finish 
faster than the bubble sort. Does it often do ?

If you want a really slow sort, the bumblesort is rated O(n²*2^n)...

> This might be relevant if you value correctness:
> http://okmij.org/ftp/Haskell/perfect-shuffle.txt

It makes a strawman example about sorting with a random key bit being 
attached to each element. No-one would use a random key. The rest of the 
argument is good, but the reader should consider what happens with 32-bit 
ints, and if that's not enough, 64-bit ints... In any case, if I were to 
code something in C++ for shuffling, I wouldn't pick this and would pick a 
fair shuffling instead, but it might be more because this is O(n*log(n)) 
and fair shufflings are doable in O(n).

Btw, when you use [random n], did you wonder about the fairness of the 
result ? note that n is usually not a divisor of 2^32. I think that the 
fairness-error it introduces is bigger than the one in sorting on random 
32-bit keys (but it shows more when n is high).

>> A better way is to start at the beginning of the array, swap the first 
>> item with one of the remaining items, then swap the second item, up to 
>> the end.

Yes, that's O(n), and that's what I'd use for a C++ version.

  _______________________________________________________________________
| Mathieu Bouchard ------------------------------ Villeray, Montréal, QC