Paul Rubin wrote:
> Boris Borcic <[EMAIL PROTECTED]> 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)
--
http://mail.python.org/mailman/listinfo/python-list
