RE: Re: Question involving scope/recursion/arguments
- To: mathgroup at smc.vnet.net
- Subject: [mg27776] RE: [mg27731] Re: Question involving scope/recursion/arguments
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.de>
- Date: Wed, 14 Mar 2001 04:07:34 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Eric,
you can transpose the recursive procedure Quicksort to Mathematica. However
you must be careful with passing of the array to be sorted. In a common
procedural language this is done either by reference or by value of a
pointer. The substitute for that within Mathematica is to pass an
unevaluated symbol. This is best done, by giving the function an appropriate
Hold-Attribute. Here is a direct (and unpolished) transposition of Quicksort
as given by Robert Sedgewick "Algorithms in C++" p.118:
In[1]:= Attributes[qsort] = HoldFirst
In[2]:=
qsort[a_Symbol, l_Integer, r_Integer] :=
If[r > l, Block[{v = a[[r]], i = l - 1, j = r},
While[True,
While[a[[++i]] < v,];
While[a[[--j]] > v,];
If[i >= j, Break[]];
a[[{i, j}]] = a[[{j, i}]];];
a[[{i, r}]] = a[[{r, i}]];
qsort[a, l, i - 1];
qsort[a, i + 1, r];]]
As you see, all manipulation is done within the array a, no copy is being
made.
In[5]:= l = Table[Random[Integer, {1, 10}], {10}]
Out[5]=
{2, 1, 7, 6, 8, 1, 10, 7, 7, 7}
In[6]:= qsort[l, 1, 10]
In[7]:= l
Out[7]=
{1, 1, 2, 6, 7, 7, 7, 7, 8, 10}
So l has been sorted ("in place").
Now we test for n log n - behaviour:
In[8]:= SeedRandom[99999999]
In[9]:=
Table[l = Table[Random[Integer, {1, 2^#}], {2^#}];
Timing[qsort[l, 1, 2^#]][[1]]] & /@ Range[8, 16]
Out[9]=
{0.13 Second, 0.271 Second, 0.621 Second, 1.342 Second, 2.884 Second,
6.119 Second, 14.1 Second, 27.53 Second, 57.833 Second}
Generally in Mathematica we like to look out for a functional alternative.
Here is one for quicksort:
In[2]:= qs[{p_, r__}, s_] :=
With[{low = Cases[{r}, x_ /; x < p], upp = Cases[{r}, x_ /; x >= p]},
qs[low, {p, qs[upp, s]}]]
In[3]:= qs[a_, b_] := {a, b}
In[4]:= qsort2[l_] := Flatten[qs[l, {}]]
You see that for each recursion step new Lists ("arrays") are generated (by
Cases), but this is not a slow operation of Order n for each step, and we
have only log n recursions. The trick to separate Quicksort into the
recursive function qs, and then flattening once at the single, final step is
decisive here. If flattening is done within the recursion the algorithm
becomes very bad ~ O[n^2].
Again we test for n log n - behaviour
In[7]:= SeedRandom[99999999]
In[8]:=
ll = Table[Random[Integer, {1, 2^#}], {2^#}] & /@ Range[8, 16];
In[9]:=
Timing[qsort2[#]][[1, 1]] & /@ ll
Out[9]=
{0.12, 0.23, 0.521, 1.152, 2.303, 5.128, 10.905, 22.683, 49.371}
We see that this slightly better than the procedural approach!
However this all cannot cope with Mathematica's built-in Sort, which is
faster by two orders of magnitude, but there programming is done at machine
level.
It may be interesting to look at the result of qs, when it terminates:
In[16]:= l = Table[Random[Integer, {1, 10}], {10}]
Out[16]=
{6, 4, 9, 1, 3, 6, 1, 6, 7, 2}
In[17]:= qs[l, {}]
Out[17]=
{{}, {1, {{}, {1, {{2}, {3, {{}, {4, {{}, {6, {{}, {6, {{}, {6, {{7}, {9, \
{{}, {}}}}}}}}}}}}}}}}}}
In[18]:= qsort2[l]
Out[18]= {1, 1, 2, 3, 4, 6, 6, 6, 7, 9}
-- Hartmut
> -----Original Message-----
> From: John Eric Hanson [mailto:jhanson1 at stny.rr.com]
To: mathgroup at smc.vnet.net
> Sent: Tuesday, March 13, 2001 9:53 AM
> To: mathgroup at smc.vnet.net
> Subject: [mg27776] [mg27731] Re: Question involving scope/recursion/arguments
>
>
> Paul-
>
> One common example of what I'm trying to do is the quicksort
> algorithm -
> where a list or an array is sorted in place recursively. I
> am finding greta
> frustration trying to find the Mathematica technique which
> would result in
> behavior similar to passing an argument by reference or a
> pointer to an
> argument.
>
> I can do this with a global variable, but then, as far as I
> can see, I'm
> bound to passing in an argument with the same name as the
> global variable
> I'm using (else I have to make a copy of the variable unless
> Mathematica
> will allow two variables to reference the same data in memory - I'm
> obviously reasonably new to Mathematica).
>
> Thanks again,
>
> Eric
>
>
> > Well, you don't specify what you want to do, so I can only
> offer this
> > generic advice:
> >
> > f[list_,a_,b_] := (g[list], If[r, list = f[list_,c,d], STOP])
> >
> > Or you can make the list global, not a passed argument.
> >
> > --
> > Paul Lutus
> > www.arachnoid.com
> >
> >
> >
> >
>
>