whats wrong with this code ?!

[becko]

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
]

[Themis Matsoukas]

Get a good night's sleep. Then, fix the line

{
qksort[z,left,i-1][[left;;i-1]],
z[[i]],
qksort[z,i+1,right][[i+1;;right]]
}

If qksort[z,left,i-1] contains fewer elements that i-1, or qksort[z,i+1,right] contains fewer than right, you will get the error message. You may try to debug your qksort using a couple print statements, as in the example below:

qksort[x_List, left_Integer, right_Integer] := If[right - left >= 1,
Module[{i, z}, {i, z} = split[x, left, right];
Print["1--", {qksort[z, left, i - 1], {left, i - 1}}];
Print["2--", {qksort[z, i + 1, right], {i + 1, right}}];
{qksort[z, left, i - 1][[left ;; i - 1]], z[[i]],
qksort[z, i + 1, right][[i + 1 ;; right]]} // Flatten], x]

This will print your lists before picking out their parts, and will also show you which parts are to be picked.

Themis

[Leonid Shifrin]

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