Sorting linked lists

[Joseph D. Shapiro]

In article <165 at ablnc.UUCP> rcpilz at ablnc.UUCP (Robert C. Pilz) writes:
>
> 
>I would like some advice on sorting linked lists. I
>am running SVR2 UNIX on a VAX 11/780 and 3B20S. I
>would like to know if there is a way to sort a linked list.
>I know that a table can be sorted via qsort(3c). But
>it assumes that every element is contiguous in memory.
>In a linked list this is not the case. Do I do a
>memory copy of some type to get the link list contiguous?
>I would like to know what works.
> 
>Send replies to:
>ihnp4!abfll!rcpilz
>Thanks

try the following:

	traverse your linked list, making an array of pointers to
	each node.

	write a comparison routine to compare two nodes, given two
	pointers to pointers to nodes.

	use qsort to sort your array of pointers to nodes.

	traverse the array of pointers to nodes, re-writing the links
	in the nodes as you go.

hope this helps

-- 
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_

Joseph D. Shapiro			"He who hesitates
Bunker Ramo Information Systems		 is lunch"

{bellcore, genrad, mcnc, sunybcs}\
{harpo, linus, decwrl, tektronix}->!decvax!ittvax!bunker!shap
{dartvax, ucbvax, wanginst, yale}/

sdcsvax!dcdwest!ittvax!bunker!shap