home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / symbolic / 3079 < prev    next >
Encoding:
Internet Message Format  |  1992-11-23  |  2.8 KB
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!cs.utexas.edu!sun-barr!ames!agate!peoplesparc.Berkeley.EDU!fateman
  2. From: fateman@peoplesparc.Berkeley.EDU (Richard Fateman)
  3. Newsgroups: sci.math.symbolic
  4. Subject: Quicksort in Mathematica
  5. Date: 23 Nov 1992 18:44:44 GMT
  6. Organization: University of California, Berkeley
  7. Lines: 94
  8. Message-ID: <1er8qsINN7cj@agate.berkeley.edu>
  9. NNTP-Posting-Host: peoplesparc.berkeley.edu
  10.  
  11.  
  12. Someone asked me why I said  earlier in this thread why an O(n log n) 
  13. algorithm might be  O(n^3) in Mathematica.
  14.  
  15. (This would be particularly embarrassing if it were being
  16. used in a CS algorithms course, but similar concerns might
  17. surface if one were to compare various RK formulas in a
  18. computational physics class.)
  19.  
  20. I tried out this simple program, and it suggests that quicksort
  21. in Mathematica is not O(n^3).  But it is not O(n log n) either.
  22.  
  23. I've spent too much time on this example this morning already,
  24. I would be interested in seeing the results of a closer look, from
  25. someone who is considering using Mathematica for CS students.
  26.   RJF.
  27.  
  28.  
  29. (* Here's a quicksort written in mathematica *)
  30.  
  31. sort[l_Integer,r_Integer] := Block[{i,j,x,w},
  32.     i=l; j=r;
  33.     x= A[[Floor[(l+r)/2]]];
  34. For[, i<=j,,
  35.     While [A[[i]] < x, i++];
  36.     While [x < A[[j]], j--];
  37.     If [i<=j,
  38.         Block[{}, w=A[[i]];A[[i]]=A[[j]];A[[j]]=w; i++; j--]]];
  39. If [l<r,sort[l,j]];
  40. If [i<r,sort[i,r]]]
  41.  
  42. (*yes, that's all there is to quicksort if you wish to sort just one
  43.   array A of n numbers, and call the sort routine by sort[1,n]. *)
  44.  
  45. (*Here are some programs to test it *)
  46.  
  47. makeA[n_]:=  A=Table[Random[Integer,100],{i,1,n}]
  48.  
  49. testsort[n_]:=Block[{},makeA[n];sort[1,n]]
  50.  
  51. (* results on MIPS-120 with Mathematica 2.0 for Timing[Do[testsort[n],{2}]] *)
  52.  
  53. (*note.. the built-in fn takes 0.15 sec  for sorting 1000 numbers, 0.37 for
  54.  sorting 4000 elements.
  55. (* above 3000, we timed just 1 run, not averaged, times 2. *)
  56.  
  57. results={{25,0.452},  
  58.     {50,0.994},
  59.     {75, 1.61},    
  60.     {100,2.23},
  61.     {200,5.17},
  62.     {300,9.37},
  63.     {400,12.23},
  64.     {500,17.16},
  65.     {800,33.97},
  66.     {1000,47.51},
  67.     {2000,149.95},
  68.     {3000,326.28},
  69.     {4000,561.7}}
  70.  
  71. p1=ListPlot[results,PlotJoined->True, PlotRange->All]
  72. (* compare mathematica to n*log(n), match at n=300 *)
  73. p2=Plot[0.005476*n*Log[n],{n,1,4000}] 
  74. Show[{p1,p2}]
  75.  
  76. (* compare mathematica to n^2, match at n=1000 *)
  77. p3=Plot[0.00006864*n^2,{n,1,4000}]
  78. Show[{p1,p3}]
  79.  
  80. (* See all three -- *)
  81.  
  82. Show[{p1,p2,p3}]
  83.  
  84. (*Conclusions: The quicksort program above, as
  85. executed by Mathematica, does not run in time proportional
  86. to not n log n.  It is much slower.
  87.  
  88. It is not as slow as n^2, at least in the range 25 to 4000.
  89.  
  90. It is ridiculously slow compared to the built-in Sort, for any size.
  91.  
  92. On the positive side, Mathematica's graphing tools are handy to show
  93. how inefficient its programming language is. *)
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102. -- 
  103. Richard J. Fateman
  104. fateman@cs.berkeley.edu   510 642-1879
  105.