Sorting linked lists

[Gregory Smith]

In article <337 at umcp-cs.UUCP> chris at umcp-cs.UUCP (Chris Torek) writes:
>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
[ 300+ lines of code deleted ]

You can use qsort. Just malloc up an array of pointers ( assume the linked list
is made of struct foo's:)

	struct foo **Index;		/* pointer to the array */
	Index = ( struct foo **) malloc( list_size * sizeof( struct foo *));

Then fill in this array with pointers to each element in the linked list.

	struct foo * Head;		/* head of list */

	register struct foo *rp, **bp;

	rp = Head; bp = Index;
	while( rp ){
		*bp++ = rp;
		rp = rp->link;
	}


Then:

	qsort( Index, list_size, sizeof( struct foo*), comp );

Note that we are sorting the pointer array, not the actual list.
This means that 'comp(a,b)' is handed two pointers to pointers to struct
foo:
	comp(a,b) struct foo **a,**b;
	{	return strcmp( (*a)->name, (*b)->name));
	}
( The above will sort on a 'name' element within foo which is of type
char * or char [] )

After that, you have an array of pointers to the list which is ordered the
way you want it. You can use this to traverse the list, or you can use it
to re-link the list in the correct order:

	for(i=0; i<list_size-1; ++i){
		Index[i]->link = Index[i+1];
			/* indexing used instead of pointers for clarity*/
	}
	Index[ list_size-1] = 0;		/* end of list */
	Head = Index[0];			/* new list head */
	free( Index );			/* done! */

Of course, the actual foo records themselves have not moved.
This is _the_ way to go if the list is long and the records are too large
to copy. The heap sort given by Chris Torek may be slightly faster, but I
don't like writing or debugging big sort routines so I like
to use qsort whenever possible.

-- 
"No eternal reward will forgive us now for wasting the dawn" -J. Morrison
----------------------------------------------------------------------
Greg Smith     University of Toronto       ..!decvax!utzoo!utcsri!greg