From: Jorrit DOT Tyberghein AT uz DOT kuleuven DOT ac DOT be (Jorrit Tyberghein)
Subject: Sorting with partial ordering
To: DJGPP AT sun DOT soe DOT clarkson DOT edu
Date: Wed, 20 Dec 1995 10:46:52 +0100 (MET)

Hello, I know this isn't exactly the right place to ask this question
but I have no access to usenet so I can't ask it there and I don't know
of any other mailing list discussing specific algorithms.

I need an algorithm to sort an array of elements with partial ordering.
What I mean is that the compare function will return any of the following
values:

compare (A, Z)
  -1: A is smaller than Z.
   2: A is greater than Z.
   0: the ordering is unknown. There is some ordering but it can not
      be known with only A and Z as information.

If compare (A, Z) returns 0 the only way to know the real order of
A and Z is to find a series B, C, D, ... with
   compare (A, B) = compare (B, C) = compare ... = compare (Y, Z)

If compare (A, Z) returns 0 and there is no series B, C, D, ... with
   compare (A, B) = compare (B, C) = compare ... = compare (Y, Z)
A and Z are independent and the ordering of these may be choosen
at random (all objects have indeces so you could use these to order
independent objects if needed).

Greetings and thanks in advance,

==============================================================================
Jorrit DOT Tyberghein AT uz DOT kuleuven DOT ac DOT be, University Hospitals KU Leuven BELGIUM

"I mean are we talking Thicko City here or what?"
        -- Gaspode the wonder dog 
           (Terry Pratchett, Moving Pictures)
==============================================================================