home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12352 < prev    next >
Encoding:
Internet Message Format  |  1992-08-14  |  1.5 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!ames!pasteur!dv349-5a.berkeley.edu!c152-cs
  2. From: c152-cs@dv349-5a.berkeley.edu (John W. Horigan)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Sort help needed
  5. Message-ID: <1992Aug14.224950.13669@pasteur.Berkeley.EDU>
  6. Date: 14 Aug 92 22:49:50 GMT
  7. References: <3223@dozo.and.nl> <2125@ontek.com> <3225@dozo.and.nl>
  8. Sender: nntp@pasteur.Berkeley.EDU (NNTP Poster)
  9. Organization: University of California, Berkeley
  10. Lines: 27
  11. Nntp-Posting-Host: dv349-5a.berkeley.edu
  12.  
  13. In article <3225@dozo.and.nl> jos@and.nl (Jos Horsmeier) writes:
  14.  
  15. [ stuff about the meaning of sort stability deleted. HS means Heap sort
  16.   and QS means Quick sort. ]
  17.  
  18. > I just
  19. >had to say that the _worst case_ behavior of HS is better than the
  20. >_worst case_ behaviour of QS, i.e. the big Oh still is O(n*log(n))
  21. >I should have avoided the use of the word `stable'. sorry ...
  22. >
  23. >(because of this O(n*log(n)) behavior, even in the worst case,
  24. > I prefer HS... no religious wars please ;-)
  25. >
  26. >kind regards,
  27. >
  28. >Jos aka jos@and.nl
  29.  
  30. But any reasonable implementation of Quick sort will use randomly
  31. chosen pivots or some other simple, easy to implement pivot selection
  32. algorithm.  With these types of Quick sort algorithms the worst case
  33. behavior is so _fantastically_ unlikely that with any reasonably
  34. sized data set you wouldn't see O(n^2) behavior within the lifetime
  35. of the universe.  But heaps are kinda neat... :)
  36.  
  37. John Horigan
  38. jhorigan@cook.berkeley.edu
  39. UC Berkeley, Dept. of Materials Science & Mineral Engineering
  40.