[PD] Shuffling arrays
Mathieu Bouchard
matju at artengine.ca
Tue Oct 5 15:55:21 CEST 2010
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
More information about the Pd-list
mailing list