Re: whats wrong with this code ?!
- To: mathgroup at smc.vnet.net
- Subject: [mg110488] Re: whats wrong with this code ?!
- From: Leonid Shifrin <lshifr at gmail.com>
- Date: Mon, 21 Jun 2010 02:09:51 -0400 (EDT)
Hi,
Here is the correct code for your method:
ClearAll[qksort];
qksort[x_List, left_Integer, right_Integer] :=
If[right - left >= 1, Module[{i, z}, {i, z} = split[x, left, right];
{qksort[z[[left ;; i - 1]], 1, i - left], z[[i]],
qksort[z[[i + 1 ;; right]], 1, right - i]} // Flatten], x]
I ommitted previous functions since no changes are needed for them.
Your code contains one non-obvious inefficiency though, and that is in the
way you deal with lists, particularly swapping function. Using ReplacePart
and idiom z = swap[z,...] means that you copy the entire list (actually
twice - once internally via ReplacePart and once explicitly) to swap only
two elements. Therefore, a single swap operation has a linear rather than
the constant time complexity in the size of the list whose elements are
being swapped.
This is hidden for small lists by the fact that other operations such as
list indexing and breaking list into pieces are costly and shadow this
effect. Also, most operations in qsort are with small lists, for which this
effect is not visible. You will start seeing it for lists of ~50000 elements
or so, where OTOH the use of home-made sort is only of academic interest
anyway, given the highly efficient built-in sorting function.
Anyway, below is a similar implementation based on pass-by-reference
semantics:
ClearAll[swapPbR];
SetAttributes[swapPbR, HoldFirst];
swapPbR[x_, i_Integer, j_Integer] :=
x[[{i, j}]] = x[[{j, i}]];
ClearAll[splitPbR];
SetAttributes[splitPbR, HoldFirst];
splitPbR[x_, left_Integer, right_Integer] :=
Module[{l = RandomInteger[{left, right}], T, i = left},
T = x[[l]]; swapPbR[x, left, l];
Do[If[x[[j]] < T, swapPbR[x, ++i, j]], {j, left + 1, right}];
swapPbR[x, left, i];
i];
ClearAll[qksortPbR];
qksortPbR[x_List, left_Integer, right_Integer] :=
Module[{i, qsort, xl = x},
qsort[l_Integer, r_Integer] :=
If[r - l >= 1,
i = splitPbR[xl, l, r];
qsort[l, i - 1];
qsort[i + 1, r]];
qsort[left, right];
xl];
This implementation is based on pass-by-reference semantics and in-place
list modification for all main functions. I use a local copy of the original
list <xl>, and recursive local <qsort> function defined in the Module scope,
which allows me to embed <xl> into it directly without passing it as a
parameter. The < swapPbR> function works on the original list passed to it,
rather than creating a copy, and is constant-time. The function <splitPbR>
also modifies the original list. Note that I omitted the head-testing
patterns _List, since they will slow the function down and are not strictly
necessary for dependent functions, and OTOH x_List pattern may not match if
this argument is held.
I find that this is a good example of a (rare) case where pass-by-reference
can indeed have some benefits in Mathematica. You can do some benchamarks
and see that PbR version is about twice faster for smalller lists and starts
to win big for larger ones. Of course, it is still much slower than the
built-in Sort.
Hope this helps.
Regards,
Leonid
On Sat, Jun 19, 2010 at 4:47 AM, becko <becko565 at hotmail.com> wrote:
> ok. I give up. I've been struggling with this the entire night. I have
> three functions: swap[..], split[..] and qksort[..]. The objective is to
> implement a recursive sort algorithm. I have tried to execute it on
> list={2,5,4,7,9,1};. But I keep getting the "Cannot take positions ..
> through .. in .." message. You may need to execute it a few times to see
> the error (because of it depends on the RandomInteger). Here are the
> three functions. Thanks in advance.
>
> swap[x_List,i_Integer,j_Integer]:=ReplacePart[x,{i->x[[j]],j->x[[i]]}]
>
> slowsort[x_List]:=
> Module[{z=x},
> Do[
> If[z[[j]]<z[[r]],z=swap[z,j,r]],
> {r,1,Length[z]-1},{j,r+1,Length[z]}
> ];
> z
> ]
>
> split[x_List,left_Integer,right_Integer]:=
> Module[{L=RandomInteger[{left,right}],z,T,i=left},
> T=x[[L]];z=swap[x,left,L];
> Do[
> If [ z[[j]]<T,z=swap[z,++i,j] ],
> {j,left+1,right}
> ];
> z=swap[z,left,i];
> {i,z}
> ]
>
> qksort[x_List,left_Integer,right_Integer]:=
> If[right-left>=1,
> Module[{i,z},
> {i,z}=split[x,left,right];
>
> {qksort[z,left,i-1][[left;;i-1]],z[[i]],qksort[z,i+1,right][[i+1;;right]]}//Flatten
> ],
> x
> ]
>
>