/*
* Copyright (c) 2004 by Richard Harter.
* This software may be freely used and modified without
* restriction provided that this notice is preserved unaltered.
*
*/
/*
* PURPOSE:
* This is an implementation of a dominance tree sort. See
* http://richardhartersworld/cri/domsort.html for a description
* dominance tree sorts. It sorts the data in place. It uses
* the minimum number of data moves and is nearly optimal for
* minimizing the number of comparisons used.
*/
#include <stdlib.h>
#define ENDLIST -1
#define PROCESSED -1
#define NODE struct domsortnode
#define DATATYPE int
#define MAXC 64
#define COMPARE_LT(x,y) (x < y)
struct domsortnode {
int child;
int sibling;
};
int
domsort(DATATYPE * data, int n)
{
NODE *node; /* Data structure for sort lists */
int u_head; /* Head of unbeaten list */
int u_tail; /* Tail of unbeaten list */
int first; /* First of a comparison pair */
int second; /* Second of a comparison pair */
int root; /* Tree root element */
int i; /* Loop index through array */
int j; /* Index of current perm. index */
int k; /* Index of next perm. index */
int pos_counter; /* Position in sorted file of tree root */
int children[MAXC]; /* Children list in array form */
int sib; /* Sibling from a sibling list */
int count; /* Size and index of sibling list */
int compares = 0; /* No. compares counter */
DATATYPE save; /* Save element for swapping */
node = malloc(n*sizeof (NODE));
if ((!node)) return 0;
for (i=0; i<n; i++)
{
node[i].child = ENDLIST;
node[i].sibling = i+1;
}
node[n-1].sibling = 0;
u_head = 0;
u_tail = n-1;
/*
* Knockout pairing section. All of the initially unbeaten elements
* are linked together in a sibling (circular linked) list. Elements
* are removed two at a time from the list and compared. The winner
* is appended to the tail of the unbeaten list. The loser is added
* to the sibling list for the winner's children.
*
*/
for (count = n-1; --count>=0;) {
first = u_head;
second = node[first].sibling;
u_head = node[second].sibling;
compares++;
if (COMPARE_LT(data[first], data[second]))
{
node[u_tail].sibling = first;
u_tail = first;
node[second].sibling = node[first].child;
node[first].child = second;
} else {
node[u_tail].sibling = second;
u_tail = second;
node[first].sibling = node[second].child;
node[second].child = first;
}
}
/*
* The data now forms a dominance tree (heap) with a single root.
* We now have a loop; in each iteration the root is removed from
* from the tree and the children of the root are compared sequentially
* to find the new root.
*
* The sibling field of the removed root holds the final position of
* the corresponding data element.
*/
root = u_tail;
pos_counter = 0;
for(;;) {
node[root].sibling = pos_counter++;
for(sib=node[root].child, count=0;
sib != ENDLIST;
sib=node[sib].sibling)
{ children[count++] = sib;}
if (count == 0) break;
if (count == 1) {
root = children[0];
continue;
}
first = children[--count];
while (count >0) {
second = children[--count];
compares++;
if (COMPARE_LT(data[first], data[second])) {
node[second].sibling = node[first].child;
node[first].child = second;
} else {
node[first].sibling = node[second].child;
node[second].child = first;
first = second;
}
}
root = first;
}
/*
* Each node sibling field now contains the position index of
* the corresponding element of the data array. In effect it
* is a permutation specifying the index to which each element
* is to be moved. We first invert the permutation, using the
* the child node to hold it. The inverse is a permutation
* the index of where each elment is to be moved from. Using
* the 'come from' permutation minimizes the number of required
* data moves for a reordering of the data in place.
*
*/
for (i=n; --i >= 0;) node[node[i].sibling].child = i;
for (i=0;i<n;i++) {
if (node[i].child <= i) continue;
for (j=i, save=data[i];;) {
k = node[j].child;
node[j].child = PROCESSED;
if (k == i) {
data[j] = save;
break;
}
data[j] = data[k];
j = k;
}
}
free (node);
return compares;
}