develooper Front page | perl.perl5.porters | Postings from September 2006

sort and 0 returns from comparison routines

Thread Next
From:
Allen Smith
Date:
September 22, 2006 06:40
Subject:
sort and 0 returns from comparison routines
Message ID:
mid+200609221345.k8MDjvBH1238267@dogberry.rutgers.edu

It is possible for there to be two different meanings for a 0 return from a
comparison routine for sort, but sort assumes (as far as I can tell) that
the first is correct:
    A. $a and $b are equal;
    B. The ordering of $a and $b cannot be determined from $a and $b alone.
The latter situation can come up in, for instance, phylogenetics and
taxonomy, which is what I have been working on. It may be possible for a
comparison routine to return that X is greater than Y (e.g., X is the parent
of Y), and that Y is greater than Z, but it may not be (conveniently)
possible for the comparison routine to determine that X is greater than Z
(e.g., because it would have to check all the descendents of X). Two
questions:
	A. Does anyone know of a sort algorithm (preferably conveniently
	   implementable in Perl or puttable in as an alternative to the
	   current mergesort/quicksort choice) that would be able to
	   recognize the above (perhaps with a return from the comparison
	   routine of undef instead of 0, if such a distinction was
	   necessary?)?
        B. With regard to perl's currently available mergesort/quicksort
           choice, which is more likely to handle this sort of situation (in
           which one may get seemingly inconsistent results from a
           comparison routine - of X vs Y being 1 and Y vs Z being 1 but X
           vs Z being 0) as desired? If this can be determined, it would be
           helpful to have this in the manpage for the sort
           pragma. Likewise, documentation of what happens (for each of
           mergesort and quicksort) if a comparison routine is _actually_
           inconsistent would be helpful.

	   Thanks,

	   -Allen

-- 
Allen Smith			         http://cesario.rutgers.edu/easmith/
There is only one sound argument for democracy, and that is the argument
that it is a crime for any man to hold himself out as better than other men,
and, above all, a most heinous offense for him to prove it. - H. L. Mencken

Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About