Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!agate!linus!alliant!merk!uvmark!jim From: jim@uvmark.uucp (Jim Todhunter) Newsgroups: comp.lang.c Subject: Re: sorting doubly linked list Message-ID: <1991May14.122033.42672@uvmark.uucp> Date: 14 May 91 12:20:33 GMT References: Distribution: comp Organization: Vmark Software, Inc. Lines: 34 In article 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