Dominance Tree Sorts

"Dominance tree sorts" is a neologism.  If anyone recognizes this 
class of sorts I would take it kindly if they would point to the 
literature (web preferred) where this class of sorts is described 
and named.  The idea doesn't seem to be explored in Knuth, though 
something may be hidden in the exercises.  Dominance tree sorts 
aare selection sorts but not tournament sorts.

Suppose we have a set S of elements and an ordering relationship 
R defined over S.  For example, S might be an array of integers, 
and R might be >, the greater than relationship.  Let x and y be 
two elements of S.  Element x is said to dominate y if (x R y).  
Again from the example, let x be 8 and y be 5.  Then x dominates 
y.

A dominance tree T over S is a tree such that (a) every element 
of S appears exactly once in T, and (b) for every element (except 
the root) the element's parent dominates it.  Here are some 
examples of dominance trees over the set {1,2,3,4,5}

          A          B        C

          5          5        5
          |          |        |
       -------     -----      4
       | | | |     |   |      |
       1 2 3 4     4   2      3
                   |          |
                  ---         2
                  | |         |
                  1 3         1
                  
Heaps are dominance trees, but not all dominance trees are heaps.  
Example B is a heap, example C is a sorted list, and in example A 
all we know is that '5' is maximal.  

A set K of comparisons (xRy) is a minimum comparison set for 
a dominance tree T if it consists exclusively of the comparisons
in the child/parent linkages.  Thus, in our example, the minimum 
comparison sets are:

K(A):  5>1, 5>2, 5>3, 5>4
K(B):  5>4, 5>2, 4>1, 4>3
K(C):  5>4, 4>3, 3>2, 2>1

Note that a minimum comparison set always has n-1 members where n 
is the cardinality of S.

An algorithm is an efficient dominance tree construction (EDTC) 
algorithm if it specifies a minimum comparison sequence that in 
turn specifies a dominance tree.

One of the important features of EDTC algorithms is that if an 
element 'loses' in a comparison it cannot appear in a later 
comparison in the comparison's sequence.  Another is that there 
is no EDTC algorithm that can guarantee that the root element has 
less than log2(n) children.  In particular there are no 
EDTC algorithms for creating heaps.

The general plan for dominance tree sorts runs as follows:  For a 
given set S we first construct a dominance tree T.  We then emit 
the root of the tree.  The children of the root are compared 
until a new root is established. In each comparison the 'loser' 
becomes a new child of the 'winner'.  EDTC algorithms are used in 
both the initial construction phase and in each emission step.  
There are quite a number of variations depending on which EDTC 
algorithms are used.

There are two major EDTC algorithms that occur to me.  The first 
is tournament pairing, also used in the tournament sort and in 
heapsort.  In the tournament pairing algorithm the set is divided
into pairs that are compared.  The winners go on to the second 
round where they are again divided into pairs that are compared.  
This is continued until a final winner is determined.  This 
requires n-1 comparisons, log2(n) rounds, and the winner, the 
root of the tree, will have log2(n) children.

The second is sequential comparison.  The first element in a 
list is compared with the second.  The winner is compared with 
the third, and so on.  This also requires n-1 comparisons.  The 
number of children of the root depends on the location of the 
root element in the list.  If the ordering of the list elements 
is random, the average number of children will n/2.  On the other 
hand, the number of children will be 1 if the list is ordered.

It turns out that we get a very efficient (as measured by the 
number of comparisons used) sort if we use tournament 
pairing to construct the initial dominance tree and sequential 
comparison in the update after emission of the root.  Each 
element has a list associated with it of elements that it 
dominates.  During construction when one element dominates 
another the losing element is appended to the winning elements 
list.  Here is a very simple example.  Let the set to be sorted 
be {2,4,3,1}.  The actions are: 

    Construction Phase
        compare (2,4); append 4 to 2's list
        compare (3,1); append 3 to 1's list
        compare (2,1); append 2 to 1's list; 1 is the root
    Emission Phase
        emit (1); compare (3,2); append 3 to 2's list; 2 is root
        emit (2); compare (3,4); append 4 to 3's list; 3 is root
        emit (3); 4 is root
        emit (4); done 

How efficient is this sort?  The tests that I ran showed it to 
about equivalent to merge-insert (see Knuth, Vol 3, 5.3.1).  For 
example, sorting 32 items requires a minimum of 118 comparisons 
on average (log2(32!)).  Merge-insert needs 121.  The number 
needed by the above algorithm depends on the precise permutation.  
The average number needed is about 121.5.  For large n the number 
of comparisons required was ~ n*(log2(n) - 1.27) in the tests I 
performed; this is not far off from the best possible of whic is
~ n*(log2(n) - log2(e)) = n*(log2(n) - 1.44).

Why is this sort efficient?  It has to do with an order 
preservation property in the construction and updating of the 
dominance lists.  In the construction phase a dominance list has 
two special properties: (a) its length is longer than the lengths 
of the lists of the elements in its list, and (b) the elements in 
the list are in order of the length of their lists.  These 
properties are almost always preserved by the above algorithm.  
In turn this implies that the lengths of the dominance lists are 
slightly less than O(log2(n)) on average.

Can this be improved upon?  Possibly.  The only 
reference I can find to dominance tree sorts is a web article by 
someone called Supercat.  In the web article he in effect forces 
property (b) to hold.  (He calls it a tournament sort which is a 
bit of a misnomer.)  He gives the following results for a test 
case sorting one million items.

Number of comparisons by a perfect sort (lg(n!)) : 18,488,865
Avg # of comparisons for Tournament Sort: 18,646,425 
   (100.85% of perfect)
Avg # of comparisons for Borland C's qsort: 22,439,507 
   (121.37% of perfect)

This gives (n = 1000000) n*(log2(n) - 1.284) which is tad better 
than the simpler algorithm given here.  On the other hand 
Supercat's version requires addition comparisons of the element 
weights (integers rather than keys).

Is this a practical sort?  Possibly not.  It requires extra space 
O(n) for the lists and O(n) for the list headers.  Each 
comparison involves adding an item to a linked list, so the 
cost of the inner loop operations will be higher than it is in 
simpler sorts.  On the other hand memory is often plentiful and 
the inner loop costs should be no worse than those for an 
ordinary tree sort.


References:
   URL:   http://www.halfbakery.com/idea/Tournament_20Sort
   Title: Tournament sort
   
   Knuth, The Art of Computer Programming, Vol 3, Searching
   and Sorting.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.

On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:

>
>Dominance Tree Sorts
Oops, should have been comp.theory.  Mea Culpa.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.

On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:


[snip original]

In the original text it is stated that a dominance tree is not a heap,
even though a heap is a dominance tree.  There are a couple of
corrections to make here.  The first is that 'heap' should have been
'binary heap'.  The second is that dominance trees have the heap
property and accordingly are heaps in the most general sense of
'heap'.

No mention is made in the original of fibonacci heaps and fibonacci
heap sorts.  There is an intimate relationship betweem fibonacci heap
sorts and the dominance tree sorts mentioned in my article.  However
they are different animals.

"Dominance tree sorts" may not be entirely appropriate since a
dominance tree is a heap.  However the appropriate names have all been
appropriated.

It should be possible to create a heap type that corresponds to the
heap structure used in dominance tree sorts.  I will look into this
and report my findings.




Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.

In article <41227327.365327442@news.sbtc.net>, cri@tiac.net (Richard Harter) writes:
> 
> Each 
> comparison involves adding an item to a linked list, so the 
> cost of the inner loop operations will be higher than it is in 
> simpler sorts.  On the other hand memory is often plentiful and 
> the inner loop costs should be no worse than those for an 
> ordinary tree sort.

On the other other hand, all that linked-list traversal likely means
poor locality of reference, which means bad cache effects.  Which,
come to think of it, is generally true of heap sorts.  If you keep
the children as an array rather than a linked list (overflows can be
handled in various ways) that should help.

Interesting idea and nice writeup, though.  I'm still thinking about
it.  On casual inspection it does look like it might be quite
amenable to being parallelized, and with SMP systems becoming ever
more common that's certainly useful.  (Of course, mergesorts are
inherently parallel and very easy to code.)

-- 
Michael Wojcik                  michael.wojcik@microfocus.com

Auden often writes like Disney.  Like Disney, he knows the shape of beasts --
(& incidently he, too, might have a company of artists producing his lines) --
unlike Lawrence, he does not know what shapes or motivates these beasts.
   -- Dylan Thomas

mwojcik@newsguy.com (Michael Wojcik) wrote in message news:<cglfau0kjv@news1.newsguy.com>...
> In article <41227327.365327442@news.sbtc.net>, cri@tiac.net (Richard Harter) writes:
> > 
> > Each 
> > comparison involves adding an item to a linked list, so the 
> > cost of the inner loop operations will be higher than it is in 
> > simpler sorts.  On the other hand memory is often plentiful and 
> > the inner loop costs should be no worse than those for an 
> > ordinary tree sort.
> 
> On the other other hand, all that linked-list traversal likely means
> poor locality of reference, which means bad cache effects.  Which,
> come to think of it, is generally true of heap sorts.  If you keep
> the children as an array rather than a linked list (overflows can be
> handled in various ways) that should help.

Performance problems with heapsort are often blamed on cache effects.
No doubt this is true; however the standard heapsort has further problems
that degrade perfomance.  An obvious one is the complexity of the inner
loops.  

A more subtle issue is that the heapify process throws information
away. For example suppose we have three elements x,y,z at locations
a[n], a[2*n], a[2*n+1] and we heapify them.  We first compare y and z
and pick the dominant one, z for the sake of argument.  We then compare 
z with x, the top point in our little heap; if it dominates x we swap, 
moving z up and x down.  We now have a[n] > {a[2*n],a[2*n+1]} and that is
all we have.  However if x was the dominant one we lose the information that
a[2*n+1] > a[2*n].  That is, the data structure doesn't distinguish between
x>z>y and z>x,z>y; in the former case it records x>z (true by transitivity)
and x>y, but not z>y.  In effect 1/3 of a decision is lost.  This information
loss occurs at several points in the standard heap sort.  For this reason
the required number of comparisons for heapsort is n*[a*log2(n)+b] where a>1.

This kind of information loss does not occur either quicksort or mergesort.
Using a simplified analysis of the mergesort cost function we get 
n*(log2(n)-1.0), which is pretty close to the optimal n*(log2(n)-log2(e)).
Although quicksort doesn't throw information away, it doesn't use it
quite as efficiently (partitions are equisized) so its 'a' is greater than 1.
As noted the dominance tree sort (my version anyway) has a comparison cost
function of ~ n*(log2(n)-1.27) or better (on random data), which is better 
than mergesort but not by much.  

I'm not sure that putting the linked lists in arrays helps particularly with
the cache problem although it is easy enough to put them in arrays.  The
catch is that the references in the linked lists are scattered.  There may
be something clever that one can do with moving the data so that cache misses
are reduced but I haven't thought it out though.


> Interesting idea and nice writeup, though.  

Thanks.

>I'm still thinking about
> it.  On casual inspection it does look like it might be quite
> amenable to being parallelized, and with SMP systems becoming ever
> more common that's certainly useful.  (Of course, mergesorts are
> inherently parallel and very easy to code.)

Offhand it seems quite straightforward to parallelize it.

As a final note both mergesort and quicksort are intrinsically cache
friendly as long as there are at least two caches.

On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:

>
>Dominance Tree Sorts
>


[snip original article]

I have looked into this matter in some detail.  In particular I have
gone through the relevant sections of Knuth, vol 3, Sorting and
Searching.  One problem here is that my copy is the 1973 edition (I
don't know what changes, if any, are in later editions.)  In
consequence there is a lot of more modern material, e.g., fibonacci
heaps, that is not included.  That said:

(1) A dominance tree is a heap (using the most general definition of
heap) with the additional requirement that each element loses in a
comparison no more than once.  There doesn't seem to be any need for
"dominance trees" as a description of a data structure.  On the other
hand the the term "dominance tree sorts" is useful since the term
"heap sorts", which ought to refer the class of sorts based on heaps
has instead been preempted as the label for a particular kind of
binary heap sort. 

(2) The category of dominance tree sorts is broader than that of
tournament sorts; however the standard tournament sort is isomorphic
to a dominance tree sort in which the tree is constructed using
tournament pairing and then in the selection phase the child lists of
each selection is processed sequentially.

(3) Tournament sorts (and the equivalent dominance tree sorts) are
highly efficient in terms of the average number of comparions and the
minimax number of comparisons required.  Both quicksort and heapsort
require substantially more; mergesort is comparable but is slightly
more costly.  Merge-Insert (Johnson-Trotter) sorts are slightly more
efficient but the gain is minimal.  

(4) Tournament sorts have the same comparison cost function as binary
insertion sorts.  However binary insertion sorts are expensive in
terms of data move costs.  Tournament sorts are better in terms of
data move costs but have (IMHO) messy data structures.  The equivalent
dominance tree sorts have "nicer" data structures.



 
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.