Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

17 views

Skip to first unread message

Jun 19, 2010, 7:47:41 AM6/19/10

to

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.

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

]

Jun 20, 2010, 3:47:11 AM6/20/10

to

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

Jun 21, 2010, 2:14:51 AM6/21/10

to

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

0 new messages

Search

Clear search

Close search

Google apps

Main menu