[comp.lang.c] Sorting Double Linked List in place

anton@bkj386.uucp (Anton Aylward) (11/08/90)

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).

I've seen single link sorts that use auxillary 'bins" (kind of like 
merge tape sort), but I'm convinced ther is something more efficient 
for the DLL, since there is the extra link.  

Knuth doesn't seem to help on this one>

References or sample algorithm anyone ?

/anton aylward			anton@analsyn.UUCP

boyd@necisa.ho.necisa.oz (Boyd Roberts) (11/09/90)

In article <1990Nov7.160701.5838@bkj386.uucp> anton@analsyn.UUCP (PUT YOUR NAME HERE) 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).
>

What about a bubble sort?


Boyd Roberts			boyd@necisa.ho.necisa.oz.au

``When the going gets wierd, the weird turn pro...''

hilfingr@rama.cs.cornell.edu (Paul N. Hilfinger) (11/09/90)

In article <1990Nov7.160701.5838@bkj386.uucp> anton@analsyn.UUCP 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).
>
>I've seen single link sorts that use auxillary 'bins" (kind of like 
>merge tape sort), but I'm convinced ther is something more efficient 
>for the DLL, since there is the extra link.  
>

Please forgive a slight engineering quibble here: Given a list of N
elements, you need only lg(N) list heads for those bins, which means
that if you can spare an extra 32 pointer-sized words of storage, you
can sort up to 4,000,000,000 elements.  Of course, if you have room
for that many elements, the reasonable reader might ask why you
quibble about 128 bytes more!

I advise you to use one of those single-link sorts you mentioned.
Assuming it is a form of merge sort, you might just as well ignore the
second links altogether until the very end; they'll just slow you
down.  On the other hand, if you have only a few 10's of elements to
sort, it doesn't matter what you do.

Paul Hilfinger

gwyn@smoke.brl.mil (Doug Gwyn) (11/09/90)

In article <1990Nov7.160701.5838@bkj386.uucp> anton@analsyn.UUCP (PUT YOUR NAME HERE) 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).
>I've seen single link sorts that use auxillary 'bins" (kind of like 
>merge tape sort), but I'm convinced ther is something more efficient 
>for the DLL, since there is the extra link.  

Heck, that's easy.  You need one extra dummy "header" node.
Walk the original list, unlinking each node and inserting it into a
binary search tree rooted at the auxiliary header node.
Then traverse the binary search tree, rotating nodes to unbalance it,
eventually putting every node in a single path.
Finally, walk the (now singly-linked) list, recreating the reverse links.

drh@duke.cs.duke.edu (D. Richard Hipp) (11/09/90)

Efficient code for in-place sorting a doubly linked list is attached.
------------------------------ cut here -------------------------------------

/*
** An entry in a doubly linked list
*/
typedef struct s_dbllink {
  int key;
  struct s_dbllink *prev, *next;
} dblink;

/*
** Merge sort on a linked list.  Only the "next" links are used -- the
** list is treated as if it were singly linked.
*/
void mergesort(dblink **topptr){
  dblink *left, *right, *top;

  top = *topptr;

  /* Only do the sort if there are 2 or more elements in the list. */
  if( top && top->next ){

    /* Step 1: Break the list into two roughly-equal sized parts. "right"
    ** and "left" will point to the head of each part */
    left = right = 0;
    while( top ){
      dblink *next;
      next = top->next;
      top->next = left;
      left = top;
      top = next;
      if( top ){
        next = top->next;
        top->next = right;
        right = top;
        top = next;
      }
    }
  
    /* Step 2: Recursively call mergesort to sort each half of the list */
    mergesort(&left);
    mergesort(&right);

    /* Step 3: Merge the two halves of the list back together */
    if( left->key<right->key ){  
      *topptr = top = left;
      left = left->next;
    }else{
      *topptr = top = right;
      right = right->next;
    }
    while( left && right ){
      if( left->key<right->key ){
        top->next = left;
        left = left->next;
      }else{
        top->next = right;
        right = right->next;
      }
      top = top->next;
    }
    top->next = left ? left : right;
  }
}

/*
** Sort a doubly linked list
*/
void dblsort(dblink **topptr){
  dblink *p, *x;

  /* Call mergesort to sort the list.  The "prev" links are ignored */
  mergesort(topptr);

  /* Reconnect the "prev" links */
  for(x=*topptr, p=0; x; x=x->next){
    x->prev = p;
    p = x;
  }
}

#ifdef TEST
#include <stdio.h>
#include <stdlib.h>

void main(void){
  char line[1000];
  dblink *x, *y;

  x = 0;
  printf("Enter numbers.  ^D to stop input.\n");
  while( fgets(line,1000,stdin) ){
    y = malloc( sizeof(dblink) );
    if( !y ) break;
    y->next = x;
    y->prev = 0;
    y->key = atoi(line);
    if( x ) x->prev = y;
    x = y;
  }
  dblsort(&x);
  printf("---------- forward -------------\n");
  for(y=x; y; y=y->next) printf("%d\n",y->key);
  printf("---------- backward ------------\n");
  for(y=x; y->next; y=y->next);
  for(; y; y=y->prev) printf("%d\n",y->key);
}
#endif

mikey@ontek.com (michelle (krill of yore) lee) (11/10/90)

In comp.lang.c, anton@analsyn.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).
| 
| I've seen single link sorts that use auxillary 'bins" (kind of like 
| merge tape sort), but I'm convinced ther is something more efficient 
| for the DLL, since there is the extra link.  
| 
| References or sample algorithm anyone ?

  What I always do is count how big the list is, malloc an array
  of pointers, initialize the array to point to each thing on the
  list, call qsort on the array, relink the list based on what
  comes back from qsort, and then free the array.  This consists of
  two passes + whatever length of time qsort takes.  Now you have
  a sorted, doubly linked list.

	the krill, or was that obvious?

hilfingr@rama.cs.cornell.edu (Paul N. Hilfinger) (11/10/90)

I found that the following code (which uses O(lg(N)) extra space, but
so what) works pretty well.  On my DECSTATION 3100 using gcc -O, it
runs about 2.5 times faster than another posted mergesort on one set
of 24000 integers, but what's a constant factor among colleagues?

The algorithm uses a binomial comb to collect merged sublists.

Paul Hilfinger

------------------------cut here----------------------------------------------

#include <stdlib.h>
#include <stdio.h>

/*
** An entry in a doubly linked list (from D. Richard Hipp)
*/
typedef struct s_dbllink {
  int key;
  struct s_dbllink *prev, *next;
} dblink;

#define NEXT(L) ((L) -> next)
#define PREV(L) ((L) -> prev)
#define KEY(L)  ((L) -> key)


#define LG_MAX_LIST 48

static dblink *merge(dblink *L0, dblink *L1);

void dblSort1(dblink **LP)
    /* Assumptions:							*/
    /*     The list *LP has no more than 2**LG_MAX_LIST elements.	*/
    /* Effect:								*/
    /*     Destructively sorts the list pointed to by *LP in		*/
    /*     increasing lexicographic order by key, setting *LP to point 	*/
    /*     to the head of the resulting list.  			        */
{
    dblink *BIN[LG_MAX_LIST]; /* List headers */
    dblink *L;
    int i;

    for (i = 0; i < LG_MAX_LIST; i += 1)
	BIN[i] = NULL;

    L = *LP;
    while (L != NULL) {
	dblink *M = L;

	L = NEXT(L);
	NEXT(M) = NULL;
	
	for (i = 0; BIN[i] != NULL; i += 1) {
	    M = merge(BIN[i], M);
	    BIN[i] = NULL;
	}
	BIN[i] = M;
    }

    for (L = BIN[0], i = 1; i < LG_MAX_LIST; i += 1)
	L = merge(BIN[i], L);

	/* Re-establish back links. */
    if (L != NULL) {
	dblink *P;

	L -> prev = NULL;
	for (P = L; NEXT(P) != NULL; P = NEXT(P))
	    PREV(NEXT(P)) = P;
    }

    *LP = L;
}

static dblink *merge(dblink *L0, dblink *L1)
    /* Assumptions:							*/
    /*     L0, L1 are sorted in increasing order by key.		*/
    /* Effects:								*/
    /*     Destructively merges L0 and L1 into increasing order.	*/
    /*     Equal elements in L0 are placed before ones in L1.		*/
    /*     Returns a pointer to the header of the list.			*/
    /*     PREV values are unreferenced (and hence, invalid).           */
{
    dblink **last;
    dblink *head;

    last = &head;

    while (L0 != NULL && L1 != NULL) {
	if (KEY(L0) <= KEY(L1)) {
	    *last = L0;
	    L0 = NEXT(L0);
	}
	else {
	    *last = L1;
	    L1 = NEXT(L1);
	}

	last = &NEXT(*last);
    }

    if (L0 == NULL)
	*last = L1;
    else
	*last = L0;

    return head;
}

rh@smds.UUCP (Richard Harter) (11/10/90)

In article <1930@necisa.ho.necisa.oz>, boyd@necisa.ho.necisa.oz (Boyd Roberts) writes:
> In article <1990Nov7.160701.5838@bkj386.uucp> anton@analsyn.UUCP (PUT YOUR NAME HERE) 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).

> What about a bubble sort?

Masochistic, aren't we. :-)

If the man wants qsort, use it.  (Complaints about the inferiority of
qsort to mergesort may be filed with the Ministry of Love, room 101.)
If one has a qsort routine the modifications to use doubly linked lists
instead of array indices are pretty simple.

-- 
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398 
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb.  This sentence short.  This signature done.

brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/10/90)

In article <1990Nov7.160701.5838@bkj386.uucp> anton@analsyn.UUCP (PUT YOUR NAME HERE) 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).
  [ .. ]
> Knuth doesn't seem to help on this one>

Everything that Knuth says about tape sorting is directly applicable
here. You have a bit more freedom in memory use, but you won't find a
noticeably more efficient algorithm.

---Dan

csgr@quagga.uucp (Geoff Rehmet) (11/10/90)

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

c164-bd@cordelia.uucp (John D. Mitchell) (11/14/90)

In article <1930@necisa.ho.necisa.oz> boyd@necisa.ho.necisa.oz (Boyd Roberts) writes:
>In article <1990Nov7.160701.5838@bkj386.uucp> anton@analsyn.UUCP (PUT YOUR NAME HERE) 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).
>
>What about a bubble sort?
>
Call this whatever you want:

Assumptions:
	Linked list

typedef struct LList_
  {
  struct LList_ *prev;
  struct LList_ *next;
  void *data;			/* Whatever...	*/
  }  LList;

LList LLSort (LList *head)
  {
  LList *lessList,		/* List containing all those < pivot.	*/
	*morequalList;		/*  "     "         "   "   >=   "  .	*/
  LList *tmpList;

  /* Stopping case checks....	*/
  ....

  /* Partition the list.	*/
  /* Basically the trick is to find a good pivot.  Just run down the
   * current list placing any node < pivot into one list and everthing
   * else into the other list.
   */
  partitionList (&lessList, &morequalList);

  /* Sort each sub-list.	*/
  LLSort (lessList);
  LLSort (morequalList);

  /* Hook the sorted sub-lists together.	*/
  tmpList = lessList;
  while (tmpList->next)
    tmpList = tmpList->next;
  tmpList->next = morequalList;

  return (lessList);
  }


PLEASE note that the above is just for illustrative puposes.  I have
actual working code that does this somewhere :-).  There are all sorts
of things that you can "optimize" for many typical cases.  Pivot
selection is the toughest (personally I use circular doubly-linked
lists, so I use the mean of the first and last elements).  If you
might have many duplicates then adding an equal list can save
re-processing all of them needlessly. ....  This should get you
started :-)...

Good luck,
	John Mitchell
	johnm@cory.Berkeley.EDU