On 27 Jul 01, at 2:36, Bart Lateur wrote:
> On Thu, 26 Jul 2001 18:58:21 -0400, Bernie Cosell wrote:
>
> >> ...If you
> >> would then swap pairs, Perl will think the entire array is already
> >> monotonic - and you will have a sort that runs in linear time!
> >
> >And what's wrong with that?
>
> The fact that it would be a lie? A distant cousin of the perpetuum
> mobile, perhaps?
>
> I'm not really sure if you are serious, or just jesting.
Just jesting... I need to put in more smileys...
> Perl's sort is based upon the idea that $a and $b are fixed, thereby
> allowing skipping some unnecessary comparisons, because the outcome can
> already be known. For example, when comparing "A", "B" and "C", it's
> enough to compare "A" with "B", and "B" with "C", to know the result of
> comparing "A" with "C". Thus, you can skip that comparison.
>
> When you start swapping items, you invalidate this supposition. The
> items become moving targets. It's just like trying to count ants in a
> whirling nest.
Actually, it is stronger than that. You can *prove* that a sort
that only ever compares two elements at a time cannot have a worst-
case performance any better than requiring at least O(nlogn)
comparisons (that is, there is at least one data set that will
require at least O(nlogn) comparisons). You can get better _average_
performance, depending on the data and whether there are
distributions/coincidences that you can take advantage of, but for
worst case analysis the nlogn limit is tough to evade.
A tricky design decision is whether to go with a sort with better
average performance in exchange for worse worst-case performance
[e.g., quick sort and quickersort, that are O(N^2) worst case, if I
remember long-ago comp science classes right, but are *usually*
better than nlogn]. Another situation like this is a list-merge sort
which is *fantastic* if the data is nearly sorted...
/Bernie\
--
Bernie Cosell Fantasy Farm Fibers
mailto:[EMAIL PROTECTED] Pearisburg, VA
--> Too many people, too few sheep <--
