rcpilz@ablnc.UUCP (Robert C. Pilz) (03/13/86)
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
chris@umcp-cs.UUCP (Chris Torek) (03/16/86)
In article <165@ablnc.UUCP> rcpilz@ablnc.UUCP writes: >I would like to know if there is a way to sort a linked list. You get to roll your own. I started to think about this, and blew a couple of hours writing the code below. This will work on a doubly linked list if you turn it into a tree first. (You can turn it back into a list when you are done.) These routines assume that copying nodes is expensive: instead of swapping values, they move nodes about in the tree. If all you have are values, this is inefficient, but usually each node in the tree has much more data than that. Besides, using this method, the code need not know the size of the nodes, so an abstracted C++ version should be easy to write. [hsort.c] #define STANDALONE /* #define VERBOSE */ /* * hsort - heap sort. * * Builds a linked list using the `left' pointers. * * Call hsort only on heaps; use tree = heapify(tree) if tree needs * to be formed into a heap first. * * For convenience, hsort() returns its argument. I.e., it is legal * to say, e.g., `printlist(hsort(heapify(tree)))'. */ #include <stdio.h> /* replace this node structure with your own */ struct node { struct node *left, *right; int value; }; /* * Build the heap (smallest at the top). * * This algorithm assumes that copying nodes is expensive. * * See comments at hsort() for generalisation directions. */ struct node * heapify(root) register struct node *root; { register struct node *cand; struct node *t; if (root == NULL) return (NULL); /* * Handle no-children case early (simplifies following code). */ if (root->left == NULL && root->right == NULL) return (root); /* nothing to do */ /* * Form the left and right sub-heaps. */ root->left = heapify(root->left); root->right = heapify(root->right); /* * Put the smallest node at the top of the tree. * If there is a left node, and: * there is no right node, or * the left node's value is less than the right node's value, * then the right is not the smallest, so it is either the left * or the root. Otherwise, it is either the right or the root. * (We have guaranteed that either left or right is non nil.) */ if ((cand = root->left) != NULL && (root->right == NULL || cand->value < root->right->value)) { if (cand->value < root->value) { /* * Swap the root's left node (cand) and the * root itself. Re-form the left subheap. */ t = root->right; root->right = cand->right; cand->right = t; root->left = cand->left; cand->left = heapify(root); return (cand); } } else { cand = root->right; if (cand->value < root->value) { /* * Swap the root's right node (cand) and the * root itself. */ t = root->left; root->left = cand->left; cand->left = t; root->right = cand->right; cand->right = heapify(root); return (cand); } } return (root); } /* * Do the heap sort (smallest values first). * * This algorithm assumes that copying nodes is expensive. * * This would be better written using classes; that and a * comparison function would generalise the routine. (Of * course, the heapify() routine would also need the same * comparison function.) */ struct node * hsort(root) struct node *root; { register struct node *l, *r, *p; register struct node **arrow; struct node **listp, *top; struct node temp; top = root; /* grab the top of the tree */ root = NULL; /* in case there is no tree */ listp = &root; /* build return list through *listp */ while ((p = top) != NULL) { /* * `top' (and now p) is the current top of the tree, and * thus by the heap property is also the smallest node. * Append it to the list, but first set up the temporary * node to hold on to the rest of the tree. */ temp.left = p->left; temp.right = p->right; *listp = p; p->left = NULL; p->right = NULL; listp = &p->left; /* * Form a new top at the temporary node, and set the arrow * to point at whatever points at the temporary node (in * this case `top'). */ top = &temp; arrow = ⊤ /* * Now bubble the temporary node down to the bottom of * the tree, re-forming the heap in the process (the * temporary node is the `least value' node). `arrow' * always points at that which points at the temporary node. */ for (;;) { l = temp.left; r = temp.right; /* * We are done iff there is no left and no right. */ if (l == NULL && r == NULL) { /* * Remove the temporary node from the tree. */ *arrow = NULL; break; } /* * We know that it goes somewhere. * It goes on the left if there is a left and: * there is no right, or * left's value < right's value * Otherwise it goes on the right. */ if (l != NULL && (r == NULL || l->value < r->value)) { /* * Move the temporary node down to the left. */ temp.left = l->left; l->left = &temp; temp.right = l->right; l->right = r; *arrow = l; arrow = &l->left; } else { /* * Move the temporary node down to the right. * We know r != NULL. */ temp.right = r->right; r->right = &temp; temp.left = r->left; r->left = l; *arrow = r; arrow = &r->right; } } } return (root); } #ifdef STANDALONE /* these routines need not be (and indeed, are not) efficient */ /* * Print a list chained via lefts. */ printlist(p) register struct node *p; { while (p) { printf("%d%c", p->value, p->left ? ' ' : '\n'); p = p->left; } } #ifdef VERBOSE /* * Print a tree. If you stand on your left ear it will look a proper tree. */ printtree(p) struct node *p; { doprinttree(p, 0, (struct node *) NULL); } /* * Helper function: print node p at depth depth; if p==nil && force!=nil, * force a `nil'. This makes the tree `spread' properly. */ doprinttree(p, depth, force) register struct node *p; int depth; struct node *force; { register int i = depth; if (p == NULL) { if (force != NULL) { while (--i >= 0) printf(" "); printf("nil\n"); } return; } doprinttree(p->right, depth + 1, p->left); while (--i >= 0) printf(" "); printf("%d\n", p->value); doprinttree(p->left, depth + 1, p->right); } #endif /* VERBOSE */ char *malloc(); /* * Create a node with the given value. */ struct node * make(v) int v; { register struct node *p = (struct node *) malloc(sizeof (*p)); if (p == NULL) { fprintf(stderr, "out of memory"); exit(1); } p->left = NULL; p->right = NULL; p->value = v; return (p); } /* * Return the depth of the tree t. */ int depth(t) register struct node *t; { return (t == NULL ? 0 : depth(t->left) + depth(t->right) + 1); } /* * Insert a node into a tree, keeping the left and right weights balanced. * Return the new tree. */ struct node * insert(t, p) register struct node *t; struct node *p; { if (t == NULL) return (p); if (depth(t->left) <= depth(t->right)) t->left = insert(t->left, p); else t->right = insert(t->right, p); return (t); } struct node * readtree() { register struct node *tree = NULL; int v; while ((fputs("> ", stdout), scanf("%d", &v)) == 1) tree = insert(tree, make(v)); printf("\n\n"); return (tree); } /*ARGSUSED*/ main(argc, argv) int argc; char **argv; { #ifdef VERBOSE struct node *root; #endif printf("enter tree values\n"); #ifdef VERBOSE root = readtree(); printf("original tree:\n"); printtree(root); root = heapify(root); printf("after heapify:\n"); printtree(root); (void) hsort(root); printf("after hsort:\n"); printlist(root); #else printlist(hsort(heapify(readtree()))); #endif exit(0); } #endif /* STANDALONE */ -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1415) UUCP: seismo!umcp-cs!chris CSNet: chris@umcp-cs ARPA: chris@mimsy.umd.edu
shap@bunker.UUCP (Joseph D. Shapiro) (03/18/86)
In article <165@ablnc.UUCP> rcpilz@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
g-rh@cca.UUCP (Richard Harter) (03/18/86)
In article <> chris@umcp-cs.UUCP (Chris Torek) writes: >In article <165@ablnc.UUCP> rcpilz@ablnc.UUCP writes: > >>I would like to know if there is a way to sort a linked list. > >You get to roll your own. I started to think about this, and blew >a couple of hours writing the code below...... A simpler method, given qsort with a compare function as an argument, is to create an array of pointers to the nodes and write the appropriate compare routine to compare the keys being pointed at. Qsort then shuffles the pointers around to produce the sorted list. You can then relink the list in sorted order using the array of pointers. Richard Harter, SMDS Inc.
greg@utcsri.UUCP (Gregory Smith) (03/18/86)
In article <337@umcp-cs.UUCP> chris@umcp-cs.UUCP (Chris Torek) writes: >In article <165@ablnc.UUCP> rcpilz@ablnc.UUCP writes: >>I would like to know if there is a way to sort a linked list. >You get to roll your own. I started to think about this, and blew >a couple of hours writing the code below. This will work on a >doubly linked list if you turn it into a tree first. (You can turn [ 300+ lines of code deleted ] You can use qsort. Just malloc up an array of pointers ( assume the linked list is made of struct foo's:) struct foo **Index; /* pointer to the array */ Index = ( struct foo **) malloc( list_size * sizeof( struct foo *)); Then fill in this array with pointers to each element in the linked list. struct foo * Head; /* head of list */ register struct foo *rp, **bp; rp = Head; bp = Index; while( rp ){ *bp++ = rp; rp = rp->link; } Then: qsort( Index, list_size, sizeof( struct foo*), comp ); Note that we are sorting the pointer array, not the actual list. This means that 'comp(a,b)' is handed two pointers to pointers to struct foo: comp(a,b) struct foo **a,**b; { return strcmp( (*a)->name, (*b)->name)); } ( The above will sort on a 'name' element within foo which is of type char * or char [] ) After that, you have an array of pointers to the list which is ordered the way you want it. You can use this to traverse the list, or you can use it to re-link the list in the correct order: for(i=0; i<list_size-1; ++i){ Index[i]->link = Index[i+1]; /* indexing used instead of pointers for clarity*/ } Index[ list_size-1] = 0; /* end of list */ Head = Index[0]; /* new list head */ free( Index ); /* done! */ Of course, the actual foo records themselves have not moved. This is _the_ way to go if the list is long and the records are too large to copy. The heap sort given by Chris Torek may be slightly faster, but I don't like writing or debugging big sort routines so I like to use qsort whenever possible. -- "No eternal reward will forgive us now for wasting the dawn" -J. Morrison ---------------------------------------------------------------------- Greg Smith University of Toronto ..!decvax!utzoo!utcsri!greg
gwyn@brl-smoke.ARPA (Doug Gwyn ) (03/20/86)
In article <165@ablnc.UUCP> rcpilz@ablnc.UUCP (Robert C. Pilz) writes: >I would like some advice on sorting linked lists. I believe the "list merge" sorting algorithm described in Knuth Vol. 3 can be adapted to this case. Since it works by changing link fields, rather than by actually moving records, it would not break other pointers in the records. List merge sorting is one of my favorite in-memory methods, primarily for its stability (see Knuth for definition). It was at the heart of an interactive traffic analysis system I whipped up on a 24Kb paper-tape based CDC 1700. (Oh, how I miss the good old days!)
chris@umcp-cs.UUCP (Chris Torek) (03/20/86)
In article <6721@cca.UUCP> g-rh@cca.UUCP (Richard Harter) writes: [in response to my heap sort] >A simpler method, given qsort with a compare function as an >argument, is to create an array of pointers to the nodes [and sort through the pointers]. Indeed you can; I was simply trying to avoid using extra space. (And I had a lot of fun writing my first ever heap sort.) Personally, I like the merge sort in article <402@mips.UUCP> by hansen@mips. Maybe I will convert that one next. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1415) UUCP: seismo!umcp-cs!chris CSNet: chris@umcp-cs ARPA: chris@mimsy.umd.edu
oster@ucblapis.berkeley.edu (David Phillip Oster) (03/28/86)
In article <402@mips.UUCP> hansen@mips.UUCP (Craig Hansen) writes: >There's a simpler way, using a merge sort instead of a heap sort. >The code below is O(n log n), and relies only on singly linked >be fairly simple to translate. The basic idea is to take the >list as pairs, sorting each pair, then take pairs of sorted >pairs and merge them together, so so on, taking geometrically >increasing-sized lists, until you have a single sorted list. >Craig Hansen >MIPS Computer Systems >...decwrl!glacier!mips!hansen > for ... > while ... > i := i - 1; > trailer := point; > point := point^.next; > end {while}; > if sublist[j] <> nil then trailer^.next := nil; > end {for}; Sorry guys, this is a stupid way to sort a list. Although your comaprison function is called O(n log n), the above code is executed n^2 times. It just blows the time codt to hell. I sort my lists by copying them into an array, sorting the array using qsort, then copying back to a list. --- David Phillip Oster ----------------------- ``What do you look like when you aren't visualizing?'' Arpa: oster@lapis.berkeley.edu Uucp: ucbvax!ucblapis!oster
hansen@mips.UUCP (Craig Hansen) (03/31/86)
> In article <402@mips.UUCP> hansen@mips.UUCP (Craig Hansen) writes: > >There's a simpler way, using a merge sort instead of a heap sort. > >The code below is O(n log n), and relies only on singly linked > >be fairly simple to translate. The basic idea is to take the > >list as pairs, sorting each pair, then take pairs of sorted > >pairs and merge them together, so so on, taking geometrically > >increasing-sized lists, until you have a single sorted list. > >Craig Hansen > >MIPS Computer Systems > >...decwrl!glacier!mips!hansen > > for ... > > while ... > > i := i - 1; > > trailer := point; > > point := point^.next; > > end {while}; > > if sublist[j] <> nil then trailer^.next := nil; > > end {for}; > > Sorry guys, this is a stupid way to sort a list. Although your comaprison > function is called O(n log n), the above code is executed n^2 times. It > just blows the time codt to hell. I sort my lists by copying them into an > array, sorting the array using qsort, then copying back to a list. > > --- David Phillip Oster > ----------------------- ``What do you look like when you aren't visualizing?'' > Arpa: oster@lapis.berkeley.edu > Uucp: ucbvax!ucblapis!oster David, you can sort your lists anyway stupid way you god-damn please. ~==~ The code you excerpt above is NOT executed n^2 times, it's executed O(n log n) times. Try profiling it if you can't reason it out. To explain further, the outer-most loop is executed O(log n) times: MergeLength := 1; while MergeLength < SymbolCount do begin ... MergeLength := MergeLength * 2; end {while}; The inner loop is order n; even though it is composed of nested loops: point := table; while point <> nil do begin ... end {while}; executes n/MergeLength times, and the loop: i := MergeLength; while (point <> nil) and (i > 0) do begin i := i - 1; ... end {while}; executes MergeLength times; the end result is O(n). Another way of seeing this is by noting that the inner loop moves "point" through the list exactly once. Did I lose anybody? -- Craig Hansen | "Evahthun' tastes MIPS Computer Systems | bettah when it ...decwrl!mips!hansen | sits on a RISC"
throopw@dg_rtp.UUCP (Wayne Throop) (04/04/86)
I've posted a "C" version of Craig Hansen's NlogN singly-linked list
sort to net.sources. It is titled "singly-linked list sort in C". It
is organized as a general-purpose routine, usable to sort lists of any
node type. It assumes that your C compiler does reasonable things with
structure layout, but this can be made compiler specific fairly easily
if your compiler is peculiar.
The main differences of this routine relative to Craig Hansen's offering
are these:
- I've heavily commented it to make clear what is going on.
(I did this because I didn't follow in detail what Craig's did until
I had translated it to C and tinkered with it a little. Craig's
was *clear* enough, I was just a little slow...)
- I've generalized it as mentioned above.
- I've traded time spent moving a bookeeping pointer through the list
against keeping a little more bookeeping information around. (The
bookeeping space is still constant in N, however.)
- I've included a small testing routine, so you can see if it works
for you.
Have fun, sorting freeks, and my apologies if zillions of list sorting
routines have already been posted to net.sources.
--
Wayne Throop at Data General, RTP, NC
<the-known-world>!mcnc!rti-sel!dg_rtp!throopw