Sorting Double Linked List in place 
Author Message
 Sorting Double Linked List in place

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 ?




Mon, 26 Apr 1993 00:07:01 GMT  
 Sorting Double Linked List in place

Quote:
>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?


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



Tue, 27 Apr 1993 08:28:29 GMT  
 Sorting Double Linked List in place

Quote:

>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



Tue, 27 Apr 1993 13:42:44 GMT  
 Sorting Double Linked List in place

Quote:
>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.


Tue, 27 Apr 1993 15:26:39 GMT  
 Sorting Double Linked List in place
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;

Quote:
} 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;
  }

Quote:
}

/*
** 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;
  }

Quote:
}

#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);

Quote:
}

#endif


Tue, 27 Apr 1993 21:42:11 GMT  
 Sorting Double Linked List in place

| 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?



Wed, 28 Apr 1993 02:17:19 GMT  
 Sorting Double Linked List in place
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;

Quote:
} 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;

Quote:
}

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;

Quote:
}



Wed, 28 Apr 1993 15:33:30 GMT  
 Sorting Double Linked List in place

Quote:


> >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?

{*filter*}ic, 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.



Wed, 28 Apr 1993 15:46:22 GMT  
 Sorting Double Linked List in place

Quote:
> 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



Wed, 28 Apr 1993 17:20:56 GMT  
 Sorting Double Linked List in place

Quote:
>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.

--


Grahamstown        |      UUCP    : ..uunet!m2xenix!quagga!csgr



Wed, 28 Apr 1993 18:01:17 GMT  
 Sorting Double Linked List in place
Quote:


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



Sun, 02 May 1993 09:30:13 GMT  
 
 [ 11 post ] 

 Relevant Pages 

1. Sorting a double linked list

2. sorting a double link list

3. HELP: how to place in sorted list.......

4. link list of a linked list (chained links?)

5. Link-list sort algorithm question

6. basic sort for singly linked list...

7. deleting and sorting items in a linked list

8. sorting of a linked list

9. Linked List Sort/Search/delete code ??Help????

10. Linked list sorting...

11. quick-sorting a linked list?

12. Please Help: Sorting a linked list

 

 
Powered by phpBB® Forum Software