Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!dali.cs.montana.edu!milton!uw-beaver!zephyr.ens.tek.com!tektronix!nosun!qiclab!m2xenix!quagga!csgr
From: csgr@quagga.uucp (Geoff Rehmet)
Newsgroups: comp.lang.c
Subject: Re: Sorting Double Linked List in place
Message-ID: <1990Nov10.100117.18743@quagga.uucp>
Date: 10 Nov 90 10:01:17 GMT
References: <1990Nov7.160701.5838@bkj386.uucp>
Organization: Rhodes University, Grahamstown RSA
Lines: 30

In <1990Nov7.160701.5838@bkj386.uucp> anton@bkj386.uucp (Anton Aylward) writes:

>I'm looking for a routine to sort a double linked list in place, 
>given the head of the list and a compare function for the elements 
>(sort of like qsort).

You can use a quicksort on a linked list (doubly or singly linked). 
All you need to do use the head element as the comparator.  This isn't
necessarily the best choice of comparator - especially if your list is
already sorted, or in inverse order!

What you need to do (I'm too lazy to write out a proper algorithm) is
split the list into 2 sublists, one of which contains only elements
greater than the comparator, and the other containing elements less than
or equal to the comparator.
Then recursively sort the 2 sublists and join the lot together with the
comparator in the middle.

You can fix up the backward links of the DLL afterwards - keeping them
consistent during the sort is more work than it's worth.

I hope this helps.

Cheers, Geoff.

-- 
Geoff Rehmet       |      Internet: csgr.quagga@f4.n494.z5.fidonet.org          
Rhodes University  |                csgr@quagga.ru.ac.za (soon - I hope)     
Grahamstown        |      UUCP    : ..uunet!m2xenix!quagga!csgr
-------------------+      Uninet  : csgr@quagga