home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / sys / mac / programm / 20050 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  1.5 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!dewey.soe.berkeley.edu!werner
  2. From: werner@dewey.soe.berkeley.edu (John Werner)
  3. Newsgroups: comp.sys.mac.programmer
  4. Subject: Re: initing Linked Lists and then Sorting them...
  5. Date: 18 Dec 1992 20:10:44 GMT
  6. Organization: School of Education, U.C. Berkeley
  7. Lines: 16
  8. Distribution: usa
  9. Message-ID: <1gtb84INN829@agate.berkeley.edu>
  10. References: <1992Dec18.190934.7747@midway.uchicago.edu>
  11. NNTP-Posting-Host: dewey.soe.berkeley.edu
  12.  
  13. In article <1992Dec18.190934.7747@midway.uchicago.edu> phoenix@uhuru.uchicago.edu (Lord Phoenix) writes:
  14. >Ok, I have been spinning in circles for the past two months and I am about 
  15. >ready to quit...  I have tried to initialize a doubly linked list and i think
  16. >it works, but when I try to sort it doesn't...
  17. >I know people must have been able to do this but I just can't figure it out...
  18.  
  19. Get any good algorithms book (like Sedgwick's "Algorithms") and look
  20. at the section on the "merge sort".  It's handy for sorting linked
  21. lists, and has good performance (N log N, I think).  The trick when
  22. sorting a doubly-linked list is to treat it like a singly-linked one,
  23. then go back and reconstruct the back-pointers when you're done.  If
  24. you're worried about sorting records with huge data objects in them,
  25. maybe you should have pointers or handles to the data instead.
  26. -- 
  27. John Werner                        werner@soe.berkeley.edu
  28. UC Berkeley School of Education    510-642-9651
  29.