random shuffles

[Boris Borcic]

I wrote :
> 
> ...in this sense, it is clear that quicksort for instance is optimal*
> 
> It is easy to see, when you detail this algorithm, that never during its 
> run is the result of a comparison it makes, preordained by comparisons 
> already made; iow : it doesn't make superfluous or redundant comparisons.

The above is true, but...

While an algorithm may never call for a comparison that has a result 
predetermined by previous comparisons, it doesn't follow that the property would 
hold true for the exact same comparisons done in a different order.

In particular, any sort algorithm must have compared successive items to be able 
to conclude to their order, so that any system of comparisons that allows to 
sort a dataset of n items, must contain the strictly minimal system of n-1 
comparisons of successive items.

This doesn't change the conclusion that an algorithm that never does a 
comparison with a result that could be deduced from previous comparisons, will 
only sample a random comparison function up to a system of comparisons that's 
consistent with an order relation between the items.