olson@aaet.csc.ti.com (Doug Olson) (05/14/91)
I have a number of doubly linked lists of the type s_double_list,
which is defined as:
typedef struct double_list
{
void *next;
void *prev;
char *key;
} s_double_list;
I need an efficient method of sorting these lists based on the key
field. Any help would be greatly appreciated.
Thanks in advance,
--
===========================================================
Doug Olson | Austin, Texas, 78714-9149
Texas Instruments | olson@aaet.csc.ti.com
12501 Research Blvd | MSGID = OLSN
P.O. Box 149149, M/S 2227 |
===========================================================wirzeniu@kruuna.Helsinki.FI (Lars Wirzenius) (05/14/91)
In article <OLSON.91May13142102@sol.aaet.csc.ti.com> olson@aaet.csc.ti.com (Doug Olson) writes: >I need an efficient method of sorting these lists based on the key >field. Any help would be greatly appreciated. How about using a quicksort, ie. (in pseudocode): list quicsort(list) { if (list is not empty) { divide list into three sublists (less, equal, and greater than first element); quicksort(less); quicksort(greater); list = less + equal + greater; fix_the_other_links; } return list; } While sorting, you should ignore the other link, and fix it afterwards (left as an exercise :-). I don't know if this is efficient enough, but it might very well be. -- Lars Wirzenius wirzenius@cc.helsinki.fi
jim@uvmark.uucp (Jim Todhunter) (05/14/91)
In article <OLSON.91May13142102@sol.aaet.csc.ti.com> olson@aaet.csc.ti.com (Doug Olson) writes: >I have a number of doubly linked lists of the type s_double_list, >which is defined as: > >typedef struct double_list >{ > void *next; > void *prev; > char *key; >} s_double_list; > > >I need an efficient method of sorting these lists based on the key >field. Any help would be greatly appreciated. Not to sound trite, but building your list in sorted order in the first place would allow you disperse the cost ( O(n2) ) of sorting over the run cycle of your program. However, if you must sort this pre-built structure: For small lists (less than 100-200 elements), simply pulling each node off the list and inserting into a new list should be fast enough ( O(n2) with a small overhead cost). For larger lists, you might try pulling each node off the list, and building a binary tree using next and prev as child pointers. After the tree has been built, you can generate the newly sorted linked list by traversing the tree. This technique will provide O(n log n) performance at a modest overhead cost. The implementation of either of the above methods is fairly simple. -- James W. Todhunter | ..uunet!merk!uvmark!jim Vmark Software, Inc. | Phone: 508-655-3700 5 Strathmore Road | Fax: 508-655-8395 Natick, MA 01760 | Telex: 5101011619 VMARKUNIVERS
shu@acsu.buffalo.edu (Wennie Shu) (05/14/91)
This message is empty.
gwyn@smoke.brl.mil (Doug Gwyn) (05/15/91)
In article <OLSON.91May13142102@sol.aaet.csc.ti.com> olson@aaet.csc.ti.com (Doug Olson) writes: >I need an efficient method of sorting these lists based on the key >field. Any help would be greatly appreciated. Convert the doubly-linked list to a binary search tree (you already have the link fields needed for that), then (if there is any need to do so) traverse the tree in inorder, moving the nodes as they are processed onto the tail of a doubly-linked list.
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (05/15/91)
In article <1991May14.112315.496@klaava.Helsinki.FI>, wirzeniu@kruuna.Helsinki.FI (Lars Wirzenius) writes: > In article <OLSON.91May13142102@sol.aaet.csc.ti.com> olson@aaet.csc.ti.com (Doug Olson) writes: > >I need an efficient method of sorting these lists based on the key > >field. Any help would be greatly appreciated. > > How about using a quicksort, ie. (in pseudocode): There are several ways of approaching this problem. The one which will get you off the ground fastest is -- determine the length of the list -- allocate a scratch array holding that many pointers -- for (i = 0, p = list; p != NULL; i++, p = p->next) a[i] = p; /* i.e. copy the list pointers into the array */ -- USE THE STANDARD LIBRARY FUNCTION qsort to sort the array -- rebuild the list from the array. -- release the scratch array All of this is trivial. If for some reason you do not want to allocate a scratch array, or if you need a really efficient sorting algorithm, USE MERGE SORT. Do *not* use quicksort. The only advantage of quicksort is that it doesn't need additional workspace, and when you _have_ a linked list you already have all the workspace you need. What is more, quicksort pays for its space saving by being quite noticably *SLOWER* than merge sort. Look in any respected algorithms text (Sedgewick, Rivest et al, ...) to find out how merge sort works. Merge sort on one way linked lists is very very simple and rather fast. To merge sort two way linked lists, ignore the back links, then rebuild them after you have finished sorting. Doubly linked lists are seldom needed; what is the task the original poster is _really_ interested in? -- There is no such thing as a balanced ecology; ecosystems are chaotic.
boyd@prl.dec.com (Boyd Roberts) (05/15/91)
Just add an extra pointer and turn the list into a binary tree and do an `infix' traversal. This is the Doug Gwyn prefered method posted some months ago to a similar request. Boyd Roberts boyd@prl.dec.com ``When the going gets wierd, the weird turn pro...''