Sorting linked lists

[Chris Torek]

In article <165 at ablnc.UUCP> rcpilz at ablnc.UUCP writes:
 
>I would like to know if there is a way to sort a linked list.

You get to roll your own.  I started to think about this, and blew
a couple of hours writing the code below.  This will work on a
doubly linked list if you turn it into a tree first.  (You can turn
it back into a list when you are done.)  These routines assume that
copying nodes is expensive: instead of swapping values, they move
nodes about in the tree.  If all you have are values, this is
inefficient, but usually each node in the tree has much more data
than that.  Besides, using this method, the code need not know the
size of the nodes, so an abstracted C++ version should be easy to
write.

[hsort.c]

#define STANDALONE
/* #define VERBOSE */

/*
 * hsort - heap sort.
 *
 * Builds a linked list using the `left' pointers.
 *
 * Call hsort only on heaps; use tree = heapify(tree) if tree needs
 * to be formed into a heap first.
 *
 * For convenience, hsort() returns its argument.  I.e., it is legal
 * to say, e.g., `printlist(hsort(heapify(tree)))'.
 */

#include <stdio.h>

/* replace this node structure with your own */
struct node {
	struct node *left, *right;
	int value;
};

/*
 * Build the heap (smallest at the top).
 *
 * This algorithm assumes that copying nodes is expensive.
 *
 * See comments at hsort() for generalisation directions.
 */
struct node *
heapify(root)
	register struct node *root;
{
	register struct node *cand;
	struct node *t;

	if (root == NULL)
		return (NULL);

	/*
	 * Handle no-children case early (simplifies following code).
	 */
	if (root->left == NULL && root->right == NULL)
		return (root);	/* nothing to do */

	/*
	 * Form the left and right sub-heaps.
	 */
	root->left = heapify(root->left);
	root->right = heapify(root->right);

	/*
	 * Put the smallest node at the top of the tree.
	 * If there is a left node, and:
	 *	there is no right node, or
	 *	the left node's value is less than the right node's value,
	 * then the right is not the smallest, so it is either the left
	 * or the root.  Otherwise, it is either the right or the root.
	 * (We have guaranteed that either left or right is non nil.)
	 */
	if ((cand = root->left) != NULL &&
	    (root->right == NULL || cand->value < root->right->value)) {
		if (cand->value < root->value) {
			/*
			 * Swap the root's left node (cand) and the
			 * root itself.  Re-form the left subheap.
			 */
			t = root->right;
			root->right = cand->right;
			cand->right = t;
			root->left = cand->left;
			cand->left = heapify(root);
			return (cand);
		}
	} else {
		cand = root->right;
		if (cand->value < root->value) {
			/*
			 * Swap the root's right node (cand) and the
			 * root itself.
			 */
			t = root->left;
			root->left = cand->left;
			cand->left = t;
			root->right = cand->right;
			cand->right = heapify(root);
			return (cand);
		}
	}

	return (root);
}

/*
 * Do the heap sort (smallest values first).
 *
 * This algorithm assumes that copying nodes is expensive.
 *
 * This would be better written using classes; that and a
 * comparison function would generalise the routine.  (Of
 * course, the heapify() routine would also need the same
 * comparison function.)
 */
struct node *
hsort(root)
	struct node *root;
{
	register struct node *l, *r, *p;
	register struct node **arrow;
	struct node **listp, *top;
	struct node temp;

	top = root;		/* grab the top of the tree */
	root = NULL;		/* in case there is no tree */
	listp = &root;		/* build return list through *listp */
	while ((p = top) != NULL) {
		/*
		 * `top' (and now p) is the current top of the tree, and
		 * thus by the heap property is also the smallest node.
		 * Append it to the list, but first set up the temporary
		 * node to hold on to the rest of the tree.
		 */
		temp.left = p->left;
		temp.right = p->right;
		*listp = p;
		p->left = NULL;
		p->right = NULL;
		listp = &p->left;

		/*
		 * Form a new top at the temporary node, and set the arrow
		 * to point at whatever points at the temporary node (in
		 * this case `top').
		 */
		top = &temp;
		arrow = ⊤

		/*
		 * Now bubble the temporary node down to the bottom of
		 * the tree, re-forming the heap in the process (the
		 * temporary node is the `least value' node).  `arrow'
		 * always points at that which points at the temporary node.
		 */
		for (;;) {
			l = temp.left;
			r = temp.right;

			/*
			 * We are done iff there is no left and no right.
			 */
			if (l == NULL && r == NULL) {
				/*
				 * Remove the temporary node from the tree.
				 */
				*arrow = NULL;
				break;
			}

			/*
			 * We know that it goes somewhere.
			 * It goes on the left if there is a left and:
			 *	there is no right, or
			 *	left's value < right's value
			 * Otherwise it goes on the right.
			 */
			if (l != NULL && (r == NULL || l->value < r->value)) {
				/*
				 * Move the temporary node down to the left.
				 */
				temp.left = l->left;
				l->left = &temp;
				temp.right = l->right;
				l->right = r;
				*arrow = l;
				arrow = &l->left;
			} else {
				/*
				 * Move the temporary node down to the right.
				 * We know r != NULL.
				 */
				temp.right = r->right;
				r->right = &temp;
				temp.left = r->left;
				r->left = l;
				*arrow = r;
				arrow = &r->right;
			}
		}
	}
	return (root);
}

#ifdef STANDALONE
/* these routines need not be (and indeed, are not) efficient */

/*
 * Print a list chained via lefts.
 */
printlist(p)
	register struct node *p;
{

	while (p) {
		printf("%d%c", p->value, p->left ? ' ' : '\n');
		p = p->left;
	}
}

#ifdef VERBOSE
/*
 * Print a tree.  If you stand on your left ear it will look a proper tree.
 */
printtree(p)
	struct node *p;
{

	doprinttree(p, 0, (struct node *) NULL);
}

/*
 * Helper function: print node p at depth depth; if p==nil && force!=nil,
 * force a `nil'.  This makes the tree `spread' properly.
 */
doprinttree(p, depth, force)
	register struct node *p;
	int depth;
	struct node *force;
{
	register int i = depth;

	if (p == NULL) {
		if (force != NULL) {
			while (--i >= 0)
				printf("   ");
			printf("nil\n");
		}
		return;
	}
	doprinttree(p->right, depth + 1, p->left);
	while (--i >= 0)
		printf("   ");
	printf("%d\n", p->value);
	doprinttree(p->left, depth + 1, p->right);
}
#endif /* VERBOSE */

char *malloc();

/*
 * Create a node with the given value.
 */
struct node *
make(v)
	int v;
{
	register struct node *p = (struct node *) malloc(sizeof (*p));

	if (p == NULL) {
		fprintf(stderr, "out of memory");
		exit(1);
	}
	p->left = NULL;
	p->right = NULL;
	p->value = v;
	return (p);
}

/*
 * Return the depth of the tree t.
 */
int
depth(t)
	register struct node *t;
{

	return (t == NULL ? 0 : depth(t->left) + depth(t->right) + 1);
}

/*
 * Insert a node into a tree, keeping the left and right weights balanced.
 * Return the new tree.
 */
struct node *
insert(t, p)
	register struct node *t;
	struct node *p;
{

	if (t == NULL)
		return (p);
	if (depth(t->left) <= depth(t->right))
		t->left = insert(t->left, p);
	else
		t->right = insert(t->right, p);
	return (t);
}

struct node *
readtree()
{
	register struct node *tree = NULL;
	int v;

	while ((fputs("> ", stdout), scanf("%d", &v)) == 1)
		tree = insert(tree, make(v));
	printf("\n\n");
	return (tree);
}

/*ARGSUSED*/
main(argc, argv)
	int argc;
	char **argv;
{
#ifdef VERBOSE
	struct node *root;
#endif

	printf("enter tree values\n");
#ifdef VERBOSE
	root = readtree();
	printf("original tree:\n");
	printtree(root);

	root = heapify(root);
	printf("after heapify:\n");
	printtree(root);

	(void) hsort(root);
	printf("after hsort:\n");
	printlist(root);
#else
	printlist(hsort(heapify(readtree())));
#endif
	exit(0);
}
#endif /* STANDALONE */
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1415)
UUCP:	seismo!umcp-cs!chris
CSNet:	chris at umcp-cs		ARPA:	chris at mimsy.umd.edu