home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / cplus / 15974 < prev    next >
Encoding:
Text File  |  1992-11-09  |  1.3 KB  |  31 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!secapl!Cookie!frank
  3. From: frank@Cookie.secapl.com (Frank Adams)
  4. Subject: Re: Making qsort type-safe
  5. Message-ID: <1992Nov09.155723.112061@Cookie.secapl.com>
  6. Date: Mon, 09 Nov 1992 15:57:23 GMT
  7. References: <1992Nov5.160048.15113@bcrka451.bnr.ca> <1992Nov6.202732.27007@mprgate.mpr.ca> <dak.721261218@messua>
  8. Organization: Security APL, Inc.
  9. Lines: 20
  10.  
  11. In article <dak.721261218@messua> dak@messua.informatik.rwth-aachen.de (David Kastrup) writes:
  12. >walduck@mpr.ca (Andrew Walduck) writes:
  13. >Quicksort needs some tuning to get really good. Fisrt, you should use
  14. >the median 3 algorithm for choosing your pivot, and take the median of
  15. >first, middle, and last element. That way, presorted data will partition
  16. >perfectly. In addition, the O(n^2) worst case becomes REALLY improbable.
  17.  
  18. An interesting fact: if the array is sorted exactly backwards, this method
  19. is still O(n^2).  If you use median of 2nd, middle, and next to last, you
  20. avoid this problem.  (You should be reverting to insertion sort for small
  21. sub-arrays, anyhow.  This makes a significant difference, whatever the size
  22. of the initial array.)
  23.  
  24. Also, when the object in the array is equal to the pivot, move it.
  25. Otherwise, you will get O(n^2) behavior when the data to be sorted is all
  26. the same.
  27.  
  28. >If you are sorting linked lists, however, use a mergesort
  29.  
  30. Absolutely.
  31.