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
_______________________________________________
Pd-list@iem.at mailing list
UNSUBSCRIBE and account-management ->
http://lists.puredata.info/listinfo/pd-list
