Sorting algorithms/Cycle sort: Difference between revisions

=={{header|J}}==

J's sort is natively a single write sort, but it assigns the whole array at once. It would be trivial do the writes one at a time, and to avoid updating values which are not changed:

<lang J>noncyc=:3 :0

writes=. 0

for_item. /:~y do.

if. item ~: item_index{y do.

writes=. writes+1

y=.item item_index} y

end.

end.

smoutput (":writes),' writes'

y

)</lang>

Example use:

<lang J> noncyc 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9

17 writes

0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</lang>

Meanwhile, if we just wanted the "value at a time swapping" mechanism, an idiomatic approach might look something like this:

<lang j>cyc0=:3 :0

c=. (#~ 1 < #@>)C./:/: y

writes=. 0

for_box. c do.

inds=. >box

v=. ({:inds) { y

for_ind. inds do.

writes=. writes+1

t=. ind{ y

y=. v ind} y

v=. t

end.

end.

smoutput (":writes),' writes'

y

)</lang>

Example use:

<lang J> cyc0 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9

18 writes

0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</lang>

This gives us an extra write, because we're using a generic cycle abstraction.

Also that's still a bit different from the wikipedia algorithm. We might model the wikipedia algorithm like this:

<lang J>cyc1=:3 :0

writes=. 0

for_index. i.(#y)-1 do.

item=. index{y

adj=. item+/ .>(1+index)}.y

if. 0<adj do.

pos=. index+adj

while. item=pos{y do. pos=.pos+1 end.

writes=. writes+1

t=. pos{y

y=. item pos} y

item=. t

while. pos ~: index do.

pos=. index+item+/ .>(1+index)}.y

while. item=pos{y do. pos=.pos+1 end.

writes=. writes+1

t=. pos{y

y=. item pos} y

item=. t

end.

end.

end.

smoutput (":writes),' writes'

y

)</lang>

Example use:

<lang J> cyc1 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9

17 writes

0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</lang>

Note that we've saved a write in this case, by following the wikipedia algorithm.