Thank you for your comments.
Yes, the camel book states that some implementations of qsort
do crash when fed inconsistent comparision results; that is a valid
point.
Also, your version feels more perl-like. But I actually choose the
constants 100 and 50 in 'int(rand(100)-50)' to have only 2% chance on
an equality result (i.e. 0); my intuition tells me that thus the
result will be more random (this will depend on the implementation of
qsort; but qsort will typically take the same decission when faced with
equality between the elements).
Greetz -- Mave
| [reply] |
Hi mave,
The text-book way of doing qsort 'properly' (already I'm on flame-war ground :) ), is use the median-three variant (median-three vairant means pick the first, middle and last item and choose the median of these for the partition point)with three speed enhancements: first use the two remaining items from the median-three step as sentinels (instead of having a second conditional in the innerloop), next at n=20-60ish (hardware dependent constant) switch to insertion sort, and lastly when deciding wether to swap or keep in place an equal item, choose to swap it.
Of course, all this is meaningless babble. The best thing to do is go in and test it. Hmm, unfortunately my boss got back from out of town work and is on the rampage this morning handing out more work for us all :) . I suggest a randomness test on output (chi-squared) and/or running sample data and counting the number of swaps. I also suggest using this when testing:
my @list = map $_->[1], sort {$a->[0]<=>$b->[0]} map [rand,$_], (0..99);
Which should be much faster on larger sets, and you can change the rand part to int rand $n, which can have $n be the (inverse of the) chance that two items will be equal.
Good Luck,
Gryn
| [reply]
[d/l] |
| [reply] |
If you want it to be either -1 or 1, but never 0, you could use
sort { int(rand 2)*2-1 } @list
| [reply]
[d/l] |
