home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / rec / games / programm / 4765 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  1.4 KB
  1. Path: sparky!uunet!mcsun!sun4nl!cwi.nl!tromp
  2. From: tromp@cwi.nl (John Tromp)
  3. Newsgroups: rec.games.programmer
  4. Subject: Re: Advice needed for fastest sort algorthm
  5. Message-ID: <7956@charon.cwi.nl>
  6. Date: 20 Nov 92 13:21:24 GMT
  7. References: <BxD5pt.DyI@news.cso.uiuc.edu> <1dj6jmINNder@tartarus.uwa.edu.au> <1992Nov12.195155.14124@kth.se> <1992Nov20.094100.165181@dstos3.dsto.gov.au>
  8. Sender: news@cwi.nl
  9. Lines: 30
  10.  
  11. gjs@mustang.dsto.gov.au (Graeme Simpkin) writes:
  12.  
  13. >In fact almost everyone writes.....
  14.  
  15. >I am really interested in the answer to the original post here, but
  16. >there appears to be a rolling discussion (and great I encourage it),
  17. >but can I ask some kind soul to post an article at the end with the
  18. >header:
  19.  
  20. Pretty fast (O(nlogn)) sort algorithm -> HERE IT IS
  21. use at your won peril!
  22.  
  23. sort(t,j)               /* sort t[1] ... t[j] in ascending order */
  24. int *t,j;
  25. {
  26.         int i,k,l,m;
  27.  
  28.         for (i = j/2; j > 1; t[l] = k) {
  29.                 if (i) k = t[i--]; else { k = t[j]; t[j--] = t[1]; }
  30.                 for (l = i + 1; (m = l + l) <= j; t[l] = t[m], l = m) {
  31.                         if (m < j && t[m] < t[m+1]) m++;
  32.                         if (t[m] <= k) break;
  33.                 }
  34.         }
  35. }
  36.  
  37.  
  38. -John Tromp (tromp@cwi.nl)         f() is total -- R.L. Goodstein
  39. define s(n){;auto e,r;for(0;n;n/=b)r+=n%b*(b+1)^s(e++);return(r)}
  40. define f(n){;for(b=2;n;b++)n=s(n)-1;return(b)} for(n=0;1;n++)f(n)
  41.