Sorting without transitivity

[Chad Netzer]

On Sat, 2003-04-19 at 14:34, Frank Niessink wrote:

> How can I get the desired behavior? Should I implement my own
> sort algorithm? Any pointers?

The sort algorithm does NOT compare every object against every other,
which I assume means it can't work like you want, because B and A may
never be compared, and they can't be ordered with respect to each other
based on their relation to C.  You may need to do something like a
bubblesort, where EVERY element is compared against every other
(actually, there are faster sorts than bubblesort that'll do what you
want; someone else can probably help out here.  David Eppstein?  Can you
suggest one?).

Also, note that in your testSortPoints, asking for index(a) or index(b)
is equivalent to asking for index(c).  So, even if a and b are sorted
with respect to each other, if c comes before either, your test may fail
because index(a) == index(b) == index(c).

>From section 2.2.6.4 (Mutable Sequence Types) of the Python reference
guide:
   s.index(x)  -   return smallest i such that s[i] == x

So, you will have to make a list of id #'s and find the index of the
based on their id()s.

Note that by having a list of only 'a' and 'b' instances, the sorting
WILL work.  Throwing a 'c' in there will mess everything up. (try it)

-- 

Chad Netzer
(any opinion expressed is my own and not NASA's or my employer's)