random shuffles

[Boris Borcic]

Paul Rubin wrote:
> Boris Borcic <bborcic at gmail.com> writes:
>> To be more convincing... assume the algorithm is optimal and calls
> 
> That assumption is not even slightly realistic.  Real-world sorting
> algorithms almost never do a precisely minimal amount of comparison.

'optimal' or 'minimal amount of comparisons' does not mean here to make just the 
right n-1 comparisons between successive items to verify the order of n items, 
but rather that no strict subset of the comparisons made to sort some data is 
sufficient to sort that data.

IOW "minimal" in "minimal amount of comparisons" refers not to the total 
ordering by size of the sets of comparisons made, but to the partial ordering by 
set inclusion of these sets.

And 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.

Do you mean quicksort-like algorithms aren't real-world ?

Best, BB
--

*assuming a variant, like the following for illustration, that doesn't waste 
info on equal items.

def qsort(items,cmp) :
     if len(items)<2 : return items
     pivot = items[0]
     divide = [[pivot],[],[]]
     for item in items[1:] :
         divide[cmp(item,pivot)].append(item)
     return qsort(divide[-1],cmp)+divide[0]+qsort(divide[1],cmp)