home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / cplus / 15880 < prev    next >
Encoding:
Text File  |  1992-11-08  |  1.8 KB  |  38 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!destroyer!cs.ubc.ca!mprgate.mpr.ca!walduck
  3. From: walduck@mpr.ca (Andrew Walduck)
  4. Subject: Re: Making qsort type-safe
  5. Message-ID: <1992Nov6.202732.27007@mprgate.mpr.ca>
  6. Sender: news@mprgate.mpr.ca
  7. Organization: MPR Teltech Ltd., Burnaby, B.C., Canada
  8. References: <1992Nov4.162131.10289@cs.brown.edu> <1992Nov5.125947.1@vax1.bham.ac.uk> <1992Nov5.160048.15113@bcrka451.bnr.ca>
  9. Date: Fri, 6 Nov 92 20:27:32 GMT
  10. Lines: 26
  11.  
  12. In article <1992Nov5.160048.15113@bcrka451.bnr.ca> sjm@bcrki65.bnr.ca (Stuart MacMartin) writes:
  13. >The library version of qsort on some machines behaves abysmally if many
  14. >objects compare equal.  On more than one UNIX workstation I have seen qsort
  15. >take more than 3/4 of an *hour* to sort a large list into two buckets,
  16. >whereas an appropriately adjusted qsort takes 1/4 *second*.  (Yes I know 
  17. >that qsort seems like a silly way to do what could be a single pass
  18. >operation, but why should "sort" be applicable to only some kinds of sorts?)
  19.  
  20. It is precisely due to this behaviour that I prefer heapsort to quicksort...
  21. Quicksort performance can rapidly approach O(N^2) as the list becomes closer
  22. to being sorted!! (It depends how the pivot is chosen...)
  23.  
  24. Many people think of qsort as an O(nlogn) sort...it isn't. Its average
  25. case is O(nlogn)...but its worst case is O(n^2) (the same as a bubble
  26. sort!!) This behaviour, when combined with its stack requirements, is
  27. why I prefer heap sort. In all cases, it performs as an O(nlogn) sort...
  28. and it can be implemented in 2 success loops...(about 30 lines of code
  29. or so...)
  30.  
  31. Andrew Walduck
  32.  
  33. -- 
  34. Andrew Walduck, MPR Canada, walduck@mprgate.mpr.ca
  35. -------------------------------------------------------------------------------
  36. (I hope someone will flatter me by using this as a .sig quote...)
  37.  -- Reid Kneeland
  38.