home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1711 < prev    next >
Internet Message Format  |  1990-12-28  |  2KB
  1. From: daveg@near.cs.caltech.edu (Dave Gillespie)
  2. Newsgroups: alt.sources
  3. Subject: Re: Sorting Algorithm
  4. Message-ID: <DAVEG.90Aug24175726@near.cs.caltech.edu>
  5. Date: 25 Aug 90 00:57:26 GMT
  6.     <wayned.0928@wddami.spoami.com>
  7. Sender: news@laguna.ccsf.caltech.edu
  8. Followup-To: alt.sources.d
  9. Organization: California Institute of Technology
  10. Lines: 36
  11.  
  12. The binary-searching insertion sort is one of those things that seem like
  13. they ought to work, but somehow the data structures invoke Murphy's Law no
  14. matter which way you turn.  Knuth discusses it in the case of sorting arrays
  15. (_Art_of_Computer_Programming_, Volume III, section 5.2.1) and notes that
  16. even though the search time is reduced to O(N log N), the time to shift
  17. around the array elements still dominates at O(N^2).  Your suggestion of
  18. using linked lists eliminates the time to shift the array, but now the search
  19. is at least O(N^2) due to the list traversals.  Both the array shifting and
  20. the pointer traversal overheads are likely to be either negliglble or
  21. (more likely) not negligible in the same situations.
  22.  
  23. My guess is that Victor Kan's fix will indeed turn out to require shuffling
  24. O(log N) pointers at each step, but at enough cost per pointer that the
  25. overall method is again O(N^2).  The problem is that, if the input is
  26. randomly distributed, each binary-search path may be wildly different
  27. from the previous one, so the list must still be traversed a significant
  28. distance most of the time.  I hope you can prove me wrong, Victor!
  29.  
  30. I remember seeing a clever technique in the June 1990 issue of
  31. "Communications of the ACM" for doing binary-search-like things with
  32. linked lists.  They augmented the linked list structure with
  33. long-distance links.  So every element points to the next element,
  34. some also point to the second element after them, fewer still also
  35. point to the fourth following element, and so on.  They showed that if
  36. you build this structure probabilistically, it's still relatively
  37. efficient in both time and space (which can easily be traded against
  38. each other) and also easy to manipulate.  Pretty cool stuff.
  39.  
  40. Anyhow, I've addressed followups to alt.sources.d because that seemed
  41. a more appropriate place for the discussion.
  42.  
  43.                                 -- Dave
  44. --
  45. Dave Gillespie
  46.   256-80 Caltech Pasadena CA USA 91125
  47.   daveg@csvax.cs.caltech.edu, ...!cit-vax!daveg
  48.