From: kogeddes@daisy.uwaterloo.ca (Keith O. Geddes)
Subject: Re: Quicksort in Mathematica
Organization: University of Waterloo
Date: Tue, 24 Nov 1992 03:09:30 GMT

In article <1er8qsINN7cj@agate.berkeley.edu> fateman@peoplesparc.Berkeley.EDU (Richard Fateman) writes:
>
>Someone asked me why I said  earlier in this thread why an O(n log n) 
>algorithm might be  O(n^3) in Mathematica.
   . . .
   . . .
>
>(* Here's a quicksort written in mathematica *)
>
>sort[l_Integer,r_Integer] := Block[{i,j,x,w},
>	i=l; j=r;
>	x= A[[Floor[(l+r)/2]]];
>For[, i<=j,,
>	While [A[[i]] < x, i++];
>	While [x < A[[j]], j--];
>	If [i<=j,
>		Block[{}, w=A[[i]];A[[i]]=A[[j]];A[[j]]=w; i++; j--]]];
>If [l<r,sort[l,j]];
>If [i<r,sort[i,r]]]
>
>(*yes, that's all there is to quicksort if you wish to sort just one
>  array A of n numbers, and call the sort routine by sort[1,n]. *)
>

It is an interesting exercise to translate this into Maple.
Here are the results.

===========================================================================

    |\^/|     Maple V Release 2
._|\|   |/|_. Copyright (c) 1981-1992 by the University of Waterloo.
 \  MAPLE  /  All rights reserved. MAPLE is a registered trademark of
 <____ ____>  Waterloo Maple Software.
      |       Type ? for help.
#
# Direct translation to Maple of Fateman's Mathematica programs.
#
> quicksort := proc(l:integer, r:integer)  local i,j,x,w;
> 	i := l;  j := r;
> 	x := A[floor((l+r)/2)];
> 	while i <= j do
> 		while A[i] < x do i := i+1 od;
> 		while x < A[j] do j := j-1 od;
> 		if i <= j then
> 			w := A[i];  A[i] := A[j];  A[j] := w;
> 			i := i+1;  j := j-1
> 		fi
> 	od;
> 	if l < r then quicksort(l,j) fi;
> 	if i < r then quicksort(i,r) fi
> end:
> 
# Here are some programs to test it.
> 
> makeA := proc(n) local i;  A := table( [seq(rand(),i=1..n)] ) end:
> 
> testsort := proc(n) makeA(n); quicksort(1,n) end:
> 
> results := NULL:
> for N in [25,50,75,100,200,300,400,500,800,1000,2000,3000,4000] do
>     st := time();  testsort(N);  results := results, [N, time()-st]
> od:
> results := [results];
  results := [[25, .200], [50, .350], [75, .550], [100, .716], [200, 1.750],

      [300, 2.200], [400, 3.550], [500, 4.367], [800, 7.733], [1000, 9.484],

      [2000, 20.100], [3000, 31.800], [4000, 45.866]]

> 
> with(plots):
> p1 := plot(results, color=red):
#
# Compare Maple to n*log(n), match at n=300.
#
> const := solve(c*300*ln(300) = results[6][2], c):
> formula := const*n*ln(n);
                        formula := .001285696529 n ln(n)

> p2 := plot(formula, n=1..4000, color=black):
#
# (Using dumb character plots for the purpose of this message.)
#
> display({p1,p2});

  |                                                                        BB 
  |                                                                     BBB A 
  |                                                                  BBB AAA  
40+                                                               BBBAAAA     
  |                                                            BBBAAAA        
  |                                                         BBBAAA            
  |                                                       B*AAA               
30+                                                    ***A                   
  |                                                B***A                      
  |                                            B***A                          
  |                                         B**A                              
  |                                      ***A                                 
20+                                  ****A                                    
  |                              B***A                                        
  |                          B****A                                           
  |                      B***AA                                               
10+                  BB**AA                                                   
  |              B***AA                                                       
  |           ***AA                                                           
  |      B****A                                                               
  |  B****A                                                                   
0 ****-----+--------+---------+--------+--------+---------+--------+--------+ 
          500     1000      1500     2000     2500      3000     3500     4000
#
# The two graphs are very similar.
#
# Check at n = 2000, 3000, 4000 .
#
> `p1 at 2000` = results[11][2];
                              p1 at 2000 = 20.100

> `p2 at 2000` = evalf(subs(n=2000, formula));
                            p2 at 2000 = 19.54490782

> `p1 at 3000` = results[12][2];
                              p1 at 3000 = 31.800

> `p2 at 3000` = evalf(subs(n=3000, formula));
                            p2 at 3000 = 30.88127698

> `p1 at 4000` = results[13][2];
                              p1 at 4000 = 45.866

> `p2 at 4000` = evalf(subs(n=4000, formula));
                            p2 at 4000 = 42.65452333

> quit

===========================================================================


Professor Keith Geddes
Director, Symbolic Computation Group
Department of Computer Science
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1                     kogeddes@daisy.uwaterloo.ca
Newsgroups: sci.math.symbolic