home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / sources / d / 1237 < prev    next >
Encoding:
Text File  |  1992-09-02  |  1.9 KB  |  39 lines
  1. Newsgroups: comp.sources.d
  2. Path: sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!zaphod.mps.ohio-state.edu!wupost!usc!venice!reuter
  3. From: reuter@venice.sedd.trw.com (Joseph Reuter)
  4. Subject: Re: Sorting in Virtual Memory
  5. Message-ID: <1992Sep2.152451.19509@venice.sedd.trw.com>
  6. Summary: Try Quicksort anyway
  7. Organization: TRW Systems Engineering & Development Division, Carson, CA
  8. References: <1992Aug27.093506.11349@sniap.mchp.sni.de> <7290002@hpfcso.FC.HP.COM>
  9. Date: Wed, 2 Sep 1992 15:24:51 GMT
  10. Lines: 27
  11.  
  12. In article <7290002@hpfcso.FC.HP.COM> ericw@hpfcso.FC.HP.COM (Eric Widhalm) writes:
  13. >/ hpfcso:comp.sources.d / frank@D012S436.sniap.mchp.sni.de () /  3:35 am  Aug 27, 1992 /
  14. >I'm writing a program which needs to sort a large array 
  15. >parts of which are swapped in and out of memory (my own
  16. >...
  17. >of swapping.  Traditional sort alrgorithms optimise on
  18. >comparisons - what I want is also to optimise the *order*
  19. >of comparison, I think.  Any ideas?
  20.  
  21. Quicksort isn't as bad as you think.  In one pass of Quicksort, the algorithm
  22. scans the array *sequentially* from both ends, occasionally swapping elements.
  23. Thus, in one pass of Quicksort, each page of the array is swapped in once.
  24. Furthermore, once the component elements get smaller than 8K, quicksort needs
  25. no swaps at all.  Thus, the swapping complexity of quicksort should be the
  26. same as its comparison complexity, n**2 in the worst case, but n*log(n)
  27. on the average.
  28.  
  29. If you really want to sort first and them merge, try one of the merge 
  30. algorithms that we used to use for tape-based sorting (see Knuth for details).
  31. Since rewinding a tape was *slow*, these algorithms tried to minimize the 
  32. passes through the tapes, which might translate into minimizing the accesses
  33. to the pages.
  34. -- 
  35. Joseph A. Reuter, Wizard-in-Training
  36. Speaking for myself from reuter@venice.sedd.trw.com
  37. "Olorin I was in the West that is forgotten." -- J.R.R. Tolkien
  38. "You can't win, you can't break even, and you can't quit the game."
  39.