home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / symbolic / 3084 < prev    next >
Encoding:
Text File  |  1992-11-24  |  5.6 KB  |  154 lines
  1. Newsgroups: sci.math.symbolic
  2. Path: sparky!uunet!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watdragon.uwaterloo.ca!daisy.uwaterloo.ca!kogeddes
  3. From: kogeddes@daisy.uwaterloo.ca (Keith O. Geddes)
  4. Subject: Re: Quicksort in Mathematica
  5. Message-ID: <By7A3v.Kv2@watdragon.uwaterloo.ca>
  6. Sender: news@watdragon.uwaterloo.ca (USENET News System)
  7. Organization: University of Waterloo
  8. References: <1er8qsINN7cj@agate.berkeley.edu>
  9. Date: Tue, 24 Nov 1992 03:09:30 GMT
  10. Lines: 142
  11.  
  12. In article <1er8qsINN7cj@agate.berkeley.edu> fateman@peoplesparc.Berkeley.EDU (Richard Fateman) writes:
  13. >
  14. >Someone asked me why I said  earlier in this thread why an O(n log n) 
  15. >algorithm might be  O(n^3) in Mathematica.
  16.    . . .
  17.    . . .
  18. >
  19. >(* Here's a quicksort written in mathematica *)
  20. >
  21. >sort[l_Integer,r_Integer] := Block[{i,j,x,w},
  22. >    i=l; j=r;
  23. >    x= A[[Floor[(l+r)/2]]];
  24. >For[, i<=j,,
  25. >    While [A[[i]] < x, i++];
  26. >    While [x < A[[j]], j--];
  27. >    If [i<=j,
  28. >        Block[{}, w=A[[i]];A[[i]]=A[[j]];A[[j]]=w; i++; j--]]];
  29. >If [l<r,sort[l,j]];
  30. >If [i<r,sort[i,r]]]
  31. >
  32. >(*yes, that's all there is to quicksort if you wish to sort just one
  33. >  array A of n numbers, and call the sort routine by sort[1,n]. *)
  34. >
  35.  
  36. It is an interesting exercise to translate this into Maple.
  37. Here are the results.
  38.  
  39. ===========================================================================
  40.  
  41.     |\^/|     Maple V Release 2
  42. ._|\|   |/|_. Copyright (c) 1981-1992 by the University of Waterloo.
  43.  \  MAPLE  /  All rights reserved. MAPLE is a registered trademark of
  44.  <____ ____>  Waterloo Maple Software.
  45.       |       Type ? for help.
  46. #
  47. # Direct translation to Maple of Fateman's Mathematica programs.
  48. #
  49. > quicksort := proc(l:integer, r:integer)  local i,j,x,w;
  50. >     i := l;  j := r;
  51. >     x := A[floor((l+r)/2)];
  52. >     while i <= j do
  53. >         while A[i] < x do i := i+1 od;
  54. >         while x < A[j] do j := j-1 od;
  55. >         if i <= j then
  56. >             w := A[i];  A[i] := A[j];  A[j] := w;
  57. >             i := i+1;  j := j-1
  58. >         fi
  59. >     od;
  60. >     if l < r then quicksort(l,j) fi;
  61. >     if i < r then quicksort(i,r) fi
  62. > end:
  63. > 
  64. # Here are some programs to test it.
  65. > 
  66. > makeA := proc(n) local i;  A := table( [seq(rand(),i=1..n)] ) end:
  67. > 
  68. > testsort := proc(n) makeA(n); quicksort(1,n) end:
  69. > 
  70. > results := NULL:
  71. > for N in [25,50,75,100,200,300,400,500,800,1000,2000,3000,4000] do
  72. >     st := time();  testsort(N);  results := results, [N, time()-st]
  73. > od:
  74. > results := [results];
  75.   results := [[25, .200], [50, .350], [75, .550], [100, .716], [200, 1.750],
  76.  
  77.       [300, 2.200], [400, 3.550], [500, 4.367], [800, 7.733], [1000, 9.484],
  78.  
  79.       [2000, 20.100], [3000, 31.800], [4000, 45.866]]
  80.  
  81. > 
  82. > with(plots):
  83. > p1 := plot(results, color=red):
  84. #
  85. # Compare Maple to n*log(n), match at n=300.
  86. #
  87. > const := solve(c*300*ln(300) = results[6][2], c):
  88. > formula := const*n*ln(n);
  89.                         formula := .001285696529 n ln(n)
  90.  
  91. > p2 := plot(formula, n=1..4000, color=black):
  92. #
  93. # (Using dumb character plots for the purpose of this message.)
  94. #
  95. > display({p1,p2});
  96.  
  97.   |                                                                        BB 
  98.   |                                                                     BBB A 
  99.   |                                                                  BBB AAA  
  100. 40+                                                               BBBAAAA     
  101.   |                                                            BBBAAAA        
  102.   |                                                         BBBAAA            
  103.   |                                                       B*AAA               
  104. 30+                                                    ***A                   
  105.   |                                                B***A                      
  106.   |                                            B***A                          
  107.   |                                         B**A                              
  108.   |                                      ***A                                 
  109. 20+                                  ****A                                    
  110.   |                              B***A                                        
  111.   |                          B****A                                           
  112.   |                      B***AA                                               
  113. 10+                  BB**AA                                                   
  114.   |              B***AA                                                       
  115.   |           ***AA                                                           
  116.   |      B****A                                                               
  117.   |  B****A                                                                   
  118. 0 ****-----+--------+---------+--------+--------+---------+--------+--------+ 
  119.           500     1000      1500     2000     2500      3000     3500     4000
  120. #
  121. # The two graphs are very similar.
  122. #
  123. # Check at n = 2000, 3000, 4000 .
  124. #
  125. > `p1 at 2000` = results[11][2];
  126.                               p1 at 2000 = 20.100
  127.  
  128. > `p2 at 2000` = evalf(subs(n=2000, formula));
  129.                             p2 at 2000 = 19.54490782
  130.  
  131. > `p1 at 3000` = results[12][2];
  132.                               p1 at 3000 = 31.800
  133.  
  134. > `p2 at 3000` = evalf(subs(n=3000, formula));
  135.                             p2 at 3000 = 30.88127698
  136.  
  137. > `p1 at 4000` = results[13][2];
  138.                               p1 at 4000 = 45.866
  139.  
  140. > `p2 at 4000` = evalf(subs(n=4000, formula));
  141.                             p2 at 4000 = 42.65452333
  142.  
  143. > quit
  144.  
  145. ===========================================================================
  146.  
  147.  
  148. Professor Keith Geddes
  149. Director, Symbolic Computation Group
  150. Department of Computer Science
  151. University of Waterloo
  152. Waterloo, Ontario
  153. Canada N2L 3G1                     kogeddes@daisy.uwaterloo.ca
  154.