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);
}
#endifmikey@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