home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 17325 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.4 KB
  1. Path: news.urz.uni-heidelberg.de!usenet
  2. From: pstarzet@ix.urz.uni-heidelberg.de (Paul Starzetz)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: 15 Apr 1996 09:48:50 GMT
  6. Organization: University of Heidelberg, Germany
  7. Distribution: world
  8. Message-ID: <4kt622$ree@sun0.urz.uni-heidelberg.de>
  9. References: <4kpfnd$3ed@vixen.cso.uiuc.edu>
  10. Reply-To: pstarzet@ix.urz.uni-heidelberg.de
  11. NNTP-Posting-Host: aixterm2.urz.uni-heidelberg.de
  12.  
  13. In article 3ed@vixen.cso.uiuc.edu,  wemccaug@prairienet.org (Wendy E. McCaughrin) writes:
  14. >
  15. >>
  16. >>Is it really 2logn?  My understanding was that a sort couldn't be
  17. >>less than nlogn...  More info, please.
  18. >>
  19. > You are correct: Quicksort performance is O(n*log(n)), usually
  20.  
  21. ...but this is only the best - and average-case!
  22. In the worst case Quicksort needs also O(N^2) steps (comparements) like the Insertion Sort.
  23.  
  24. The exact recursive formula for the average-case performance is
  25.  
  26. T(N) = c*(N + (1/N)*Sum(  T(n) + T(n-k) , k=1..N) )  (it's really the upper bound, so you can replace = by <, and c is a machine-dependent constant, can be set to 1)
  27.  
  28. and for the best case:
  29.  
  30. T(N) = c*(N + 2*T(N/2 ) ) (which can be easily resolved as c*N*log(N)  )
  31.  
  32. while the worst case formula sounds:
  33.  
  34. T(N) = c*(N + T(N-1) ) ( because sequences of single element are ignored,)
  35. which is simply T(N) = c*T(N-1) + c*N = c*T(N-2) + c*(N-1) + c*N = ... =
  36.                                  = c*T(0) + c + 2*c + ... + (N-1)*c + N*c = c*N*(n-1)/2
  37.  
  38.  
  39.  
  40.  
  41.