Re: Question involving scope/recursion/arguments
- To: mathgroup at smc.vnet.net
- Subject: [mg27755] Re: Question involving scope/recursion/arguments
- From: Jens-Peer Kuska <kuska at informatik.uni-leipzig.de>
- Date: Wed, 14 Mar 2001 04:06:53 -0500 (EST)
- Organization: Universitaet Leipzig
- References: <98kofv$pq3@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hi,
here is the QuickSort version from Roman Maeder
quickSort[list_] := Module[ {l = list}, qSort[l, 1, Length[l]]; l ]
(* auxiliary procedure *)
SetAttributes[qSort, HoldFirst]
qSort[l_, n0_, n1_] /; n0 >= n1 := l (* nothing to do *)
qSort[l_, n0_, n1_] :=
Module[{lm = l[[ Floor[(n0 + n1)/2] ]], i = n0, j = n1},
While[ True,
While[ l[[i]] < lm, i++ ];
While[ l[[j]] > lm, j-- ];
If[ i >= j, Break[] ]; (* l is partitioned *)
swap[l, i, j];
i++; j--
];
(* recursion, shorter piece first *)
If[ i-n0 <= n1-j,
qSort[ l, n0, i-1 ]; qSort[ l, j+1, n1 ]
, qSort[ l, j+1, n1 ]; qSort[ l, n0, i-1 ]
]
]
Regards
Jens
John Eric Hanson wrote:
>
> 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
> >
> >
> >
> >