home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / cplus / 15943 < prev    next >
Encoding:
Text File  |  1992-11-08  |  2.2 KB  |  44 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!Sirius.dfn.de!Urmel.Informatik.RWTH-Aachen.DE!messua!dak
  3. From: dak@messua.informatik.rwth-aachen.de (David Kastrup)
  4. Subject: Re: Making qsort type-safe
  5. Message-ID: <dak.721261218@messua>
  6. Sender: news@Urmel.Informatik.RWTH-Aachen.DE (Newsfiles Owner)
  7. Nntp-Posting-Host: messua
  8. Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
  9. References: <1992Nov4.162131.10289@cs.brown.edu> <1992Nov5.125947.1@vax1.bham.ac.uk> <1992Nov5.160048.15113@bcrka451.bnr.ca> <1992Nov6.202732.27007@mprgate.mpr.ca>
  10. Date:  8 Nov 92 22:20:18 GMT
  11. Lines: 31
  12.  
  13. walduck@mpr.ca (Andrew Walduck) writes:
  14.  
  15.  
  16. >It is precisely due to this behaviour that I prefer heapsort to quicksort...
  17. >Quicksort performance can rapidly approach O(N^2) as the list becomes closer
  18. >to being sorted!! (It depends how the pivot is chosen...)
  19.  
  20. >Many people think of qsort as an O(nlogn) sort...it isn't. Its average
  21. >case is O(nlogn)...but its worst case is O(n^2) (the same as a bubble
  22. >sort!!) This behaviour, when combined with its stack requirements, is
  23. >why I prefer heap sort. In all cases, it performs as an O(nlogn) sort...
  24. >and it can be implemented in 2 success loops...(about 30 lines of code
  25. >or so...)
  26.  
  27. Quicksort needs some tuning to get really good. Fisrt, you should use
  28. the median 3 algorithm for choosing your pivot, and take the median of
  29. first, middle, and last element. That way, presorted data will partition
  30. perfectly. In addition, the O(n^2) worst case becomes REALLY improbable.
  31.  
  32. Secondly, you should look which of the two partitions you get has less
  33. elements and sort that partition first in recursion. THEN sort the second,
  34. larger size partition by a tail recursion. That way, your stack space
  35. will be strictly O(lg n) even in worst case.
  36.  
  37. If you are sorting linked lists, however, use a mergesort, which combines
  38. sorting a sublist with scanning to the head of the next sublist.
  39.  
  40. Short code, guaranteed LESS than n lg n comparisons, guaranteed at most
  41. lg n recursion depth, no data copying, etc. And you need no tricks (as
  42. opposed to quicksort) to let it work well behavedly. Beats average quicksorts
  43. by a factor of more than 2 (at least in Turbo C it does.)
  44.