Sorting algorithms/Cycle sort: Difference between revisions
Content deleted Content added
→{{header|REXX}}: added version 4. |
|||
(75 intermediate revisions by 33 users not shown) | |||
Line 1:
{{draft task|Sorting Algorithms}}
{{Sorting Algorithm}}
[[Category:Sorting]]
{{Wikipedia|Cycle_sort}}
<!-- also known as a cyclic sort !-->
<br>
From the [[wp:Cycle sort|the Wikipedia entry]] on cycle sorting:
:'''Cycle sort''' is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm.
:It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.
:Unlike nearly every other sort, items are never written elsewhere in the array simply to push them out of the way of the action.
:Each value is either written zero times, if it's already in its correct position, or written one time to its correct position.
:This matches the minimal number of overwrites required for a completed in-place sort.
:Minimizing the number of writes is useful when making writes to some huge data set is very expensive, such as with EEPROMs like Flash memory where each write reduces the lifespan of the memory.
;See also:
* [http://www.youtube.com/watch?v=ZSJGf5Ngw18 Youtube] Visualization and audibilization of Cycle Sort algorithm.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F cycleSort(&vector)
V writes = 0
L(=item) vector
V cycleStart = L.index
V pos = cycleStart
L(item2) vector[cycleStart+1..]
I item2 < item
pos++
I pos == cycleStart
L.continue
L item == vector[pos]
pos++
swap(&vector[pos], &item)
writes++
L pos != cycleStart
pos = cycleStart
L(item2) vector[cycleStart+1..]
I item2 < item
pos++
L item == vector[pos]
pos++
swap(&vector[pos], &item)
writes++
R writes
V x = [Float(0), 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
V xcopy = copy(x)
V writes = cycleSort(&xcopy)
I xcopy != sorted(x)
print(‘Wrong order!’)
E
print("#.\nIs correctly sorted using cycleSort to".format(x))
print("#.\nUsing #. writes.".format(xcopy, writes))</syntaxhighlight>
{{out}}
<pre>
[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
Is correctly sorted using cycleSort to
[0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9]
Using 10 writes.
</pre>
=={{header|360 Assembly}}==
{{trans|NetRexx}}
The program uses ASM structured macros and two ASSIST macros to keep the code as short as possible.
<syntaxhighlight lang="360asm">* Cycle sort 26/06/2016
CYCLESRT CSECT
USING CYCLESRT,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
STM R14,R12,12(R13) prolog
ST R13,4(R15) "
ST R15,8(R13) "
LR R13,R15 "
LA RJ,1 jcycle=1
L R2,N n
BCTR R2,0 n-1
ST R2,NM1 nm1=n-1
DO WHILE=(C,RJ,LE,NM1) do jcycle=1 to n-1
LR R1,RJ jcycle
SLA R1,2 .
L RM,A-4(R1) item=a(jcycle)
LR RK,RJ kpos=jcycle /*find{*/
LA RI,1(RJ) i=jcycle+1
DO WHILE=(C,RI,LE,N) do i=jcycle+1 to n
LR R1,RI i
SLA R1,2 .
L R2,A-4(R1) a(i)
IF CR,R2,LT,RM THEN if a(i)<item then
LA RK,1(RK) kpos=kpos+1
ENDIF , end if
LA RI,1(RI) i=i+1
ENDDO , end do /*}*/
IF CR,RK,NE,RJ THEN if kpos^=jcycle then ======
LR R1,RK kpos /*put{*/
SLA R1,2 .
LA R2,A-4(R1) @a(kpos)
DO WHILE=(C,RM,EQ,0(R2)) do while item=a(kpos)
LA RK,1(RK) kpos=kpos+1
LA R2,4(R2) @a(kpos)=@a(kpos)+4
ENDDO , end do
LR R1,RK kpos
SLA R1,2 .
LA R2,A-4(R1) @a(kpos)
L RT,0(R2) temp=a(kpos)
ST RM,0(R2) a(kpos)=item
LR RM,RT item=temp
L R2,WRITES writes
LA R2,1(R2) writes+1
ST R2,WRITES writes=writes+1 /*}*/
DO WHILE=(CR,RK,NE,RJ) do while(kpos^=jcycle) -----
LR RK,RJ kpos=jcycle /*find{*/
LA RI,1(RJ) i=jcycle+1
DO WHILE=(C,RI,LE,N) do i=jcycle+1 to n
LR R1,RI i
SLA R1,2 .
L R2,A-4(R1) a(i)
IF CR,R2,LT,RM THEN if a(i)<item then
LA RK,1(RK) kpos=kpos+1
ENDIF , end if
LA RI,1(RI) i=i+1
ENDDO , end do /*}*/
LR R1,RK kpos /*put{*/
SLA R1,2 .
LA R2,A-4(R1) @a(kpos)
DO WHILE=(C,RM,EQ,0(R2)) do while item=a(kpos)
LA RK,1(RK) kpos=kpos+1
LA R2,4(R2) @a(kpos)=@a(kpos)+4
ENDDO , end do
LR R1,RK kpos
SLA R1,2 .
LA R2,A-4(R1) @a(kpos)
L RT,0(R2) temp=a(kpos)
ST RM,0(R2) a(kpos)=item
LR RM,RT item=temp
L R2,WRITES writes
LA R2,1(R2) writes+1
ST R2,WRITES writes=writes+1 /*}*/
ENDDO , end while ------------------
ENDIF , end if =====================
LA RJ,1(RJ) jcycle=jcycle+1
ENDDO , end do jcycle
LA R3,PG pgi=0
LA RI,1 i=1
DO WHILE=(C,RI,LE,N) do i=1 to n
LR R1,RI i
SLA R1,2 .
L R2,A-4(R1) a(i)
XDECO R2,XDEC edit a(i)
MVC 0(4,R3),XDEC+8 output a(i)
LA R3,4(R3) pgi=pgi+4
LA RI,1(RI) i=i+1
ENDDO , end do
XPRNT PG,L'PG print buffer
L R1,WRITES writes
XDECO R1,XDEC edit writes
MVC XDEC(7),=CL7'writes='
XPRNT XDEC,L'XDEC print buffer
L R13,4(0,R13) epilog
LM R14,R12,12(R13) "
XR R15,R15 "
BR R14 exit
A DC F'4',F'65',F'2',F'-31',F'0',F'99',F'2',F'83',F'782',F'1'
DC F'45',F'82',F'69',F'82',F'104',F'58',F'88',F'112',F'89',F'74'
N DC A((N-A)/L'A) number of items of a
NM1 DS F n-1
PG DC CL80' ' buffer
XDEC DS CL12 temp for xdeco
WRITES DC F'0' number of writes
YREGS
RI EQU 6 i
RJ EQU 7 jcycle
RK EQU 8 kpos
RT EQU 9 temp
RM EQU 10 item
END CYCLESRT</syntaxhighlight>
{{out}}
<pre>
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC CycleSort(INT ARRAY a INT size)
BYTE start,i,pos
INT item,tmp
FOR start=0 TO size-2
DO
item=a(start)
pos=start
FOR i=start+1 TO size-1
DO
IF a(i)<item THEN
pos==+1
FI
OD
IF pos#start THEN
tmp=a(pos) a(pos)=item item=tmp
WHILE pos#start
DO
pos=start
FOR i=start+1 TO size-1
DO
IF a(i)<item THEN
pos==+1
FI
OD
WHILE item=a(pos)
DO
pos==+1
OD
tmp=a(pos) a(pos)=item item=tmp
OD
FI
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
CycleSort(a,size)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 3 7 4 8 20 65530],
b(21)=[10 9 8 7 6 5 4 3 2 1 0
65535 65534 65533 65532 65531
65530 65529 65528 65527 65526],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,10)
Test(b,21)
Test(c,8)
Test(d,12)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Cycle_sort.png Screenshot from Atari 8-bit computer]
<pre>
Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]
Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]
Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]
Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
</pre>
=={{header|ALGOL 68}}==
{{Trans|Action!}}
<syntaxhighlight lang="algol68">
BEGIN # cycle sort - translated from the Action! sample #
# prints the elements of a #
OP SHOW = ( REF[]INT a )VOID:
BEGIN
print( ( "[" ) );
FOR i FROM LWB a TO UPB a DO
print( ( " ", whole( a[ i ], 0 ) ) )
OD;
print( " ]" )
END # SHOW # ;
# swaps a and b #
PRIO =:= = 1;
OP =:= = ( REF INT a, b )VOID: BEGIN INT t := a; a := b; b := t END;
# cycle sorts a #
PROC cycle sort = ( REF[]INT a )VOID:
FOR start FROM LWB a TO UPB a - 1 DO
INT item := a[ start ];
INT pos := start;
FOR i FROM start + 1 TO UPB a DO
IF a[ i ] < item THEN
pos +:= 1
FI
OD;
IF pos /= start THEN
item =:= a[ pos ];
WHILE pos /= start DO
pos := start;
FOR i FROM start + 1 TO UPB a DO
IF a[ i ] < item THEN
pos +:= 1
FI
OD;
WHILE item = a[ pos ] DO
pos +:= 1
OD;
a[ pos ] =:= item
OD
FI
OD # cycle sort # ;
PROC test = ( REF[]INT a )VOID:
BEGIN
print( ( "Array before sort: " ) ); SHOW a; print( ( newline ) );
cycle sort( a );
print( ( "Array after sort: " ) ); SHOW a; print( ( newline ) );
END # test # ;
BEGIN # tests #
[ 10 ]INT a := []INT( 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 );
[ 21 ]INT b := []INT( 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10
);
[ 8 ]INT c := []INT( 101, 102, 103, 104, 105, 106, 107, 108 );
[ 12 ]INT d := []INT( 1 ,-1, 1,-1, 1, -1, 1, -1, 1, -1, 1, -1 );
test( a );
test( b );
test( c );
test( d )
END
END
</syntaxhighlight>
{{out}}
<pre>
Array before sort: [ 1 4 -1 0 3 7 4 8 20 -6 ]
Array after sort: [ -6 -1 0 1 3 4 4 7 8 20 ]
Array before sort: [ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ]
Array after sort: [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ]
Array before sort: [ 101 102 103 104 105 106 107 108 ]
Array after sort: [ 101 102 103 104 105 106 107 108 ]
Array before sort: [ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ]
Array after sort: [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ]
</pre>
=={{header|ALGOL W}}==
{{Trans|Lua}}
<syntaxhighlight lang="algolw">
begin % cycle sort %
% cycle sorts a, the bounds of a must be specified in lb and ub %
integer procedure cycleSort ( integer array a ( * ); integer value lb, ub ) ;
begin
% swaps a and b %
procedure swap ( integer value result a, b ) ;
begin integer t;
t := a; a := b; b := t;
swaps := swaps + 1
end swap ;
integer swaps, cycleStart, cycleEnd, val, pos;
swaps := 0;
cycleStart := lb - 1;
while cycleStart < ub do begin
val := a( cycleStart + 1 );
% count the number of values that are smaller than val since cycleStart %
pos := cycleStart;
for i := cycleStart + 1 until ub - 1 do begin
if a( i + 1 ) < val then pos := pos + 1
end for_i ;
if pos not = cycleStart then begin % there aren't any %
while val = a( pos + 1 ) do pos := pos + 1;
swap( a( pos + 1 ), val ); % put val in final position %
% repeat as long as we can find values to swap %
% otherwise start new cycle %
while pos not = cycleStart do begin
pos := cycleStart;
for i := cycleStart + 1 until ub- 1 do begin
if a( i + 1 ) < val then pos := pos + 1;
end for_i ;
while val = a( pos + 1 ) do pos := pos + 1;
swap( a( pos + 1 ), val );
end while_pos_ne_cycleStart
end if_pos_ne_cycleStart ;
cycleStart := cycleStart + 1
end while_cycleStart_lt_ub ;
swaps
end cycleSort ;
% prints the elements of a from lb to ub %
procedure writeonArray( integer array a ( * ); integer value lb, ub ) ;
begin
writeon( "(" );
for i := lb until ub do writeon( i_w := 1, s_w := 0, " ", a( i ) );
writeon( " )" )
end writeonArray ;
begin % tests %
integer array arr ( 1 :: 16 );
integer aPos, swaps;
aPos := 1;
for v := 5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1 do begin
arr( aPos ) := v;
aPos := aPos + 1
end for_v ;
writeonArray( arr, 1, 16 );
writeon( " -> " );
swaps := cycleSort( arr, 1, 16 );
writeonArray( arr, 1, 16 );
write( i_w := 1, s_w := 0, "swaps: ", swaps )
end
end.
</syntaxhighlight>
{{out}}
<pre>
( 5 0 1 2 2 3 5 1 1 0 5 6 9 8 0 1 ) -> ( 0 0 0 1 1 1 1 2 2 3 5 5 5 6 8 9 )
swaps: 14
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">cycleSort: function [items][
a: new items
position: 0
loop 0..dec dec size a 'cycleStart [
item: a\[cycleStart]
position: cycleStart
loop (cycleStart+1)..dec size a 'i [
if (get a i) < item -> position: position + 1
]
if position = cycleStart -> continue
while [item = a\[position]] -> position: position + 1
tmp: a\[position]
a\[position]: item
item: tmp
while [position <> cycleStart][
position: cycleStart
loop (cycleStart+1)..dec size a 'i [
if a\[i] < item -> position: position + 1
]
while [item = a\[position]] -> position: position + 1
tmp: a\[position]
a\[position]: item
item: tmp
]
]
return a
]
print cycleSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
// Sort an array in place and return the number of writes
let cyclesort(v, len) = valof
$( let writes, temp = 0, ?
// Loop through the array to find cycles to rotate
for start = 0 to len-1
$( let item = v!start
// Find where to put the item
let pos = start
for i = start+1 to len-1
if v!i < item then pos := pos + 1
// If the item is already there, this is not a cycle
if pos = start loop
// Otherwise, put the item there or right after any duplicates
while item = v!pos do pos := pos + 1
temp := v!pos
v!pos := item
item := temp
writes := writes + 1
// Rotate the rest of the cycle
until pos = start
$( // Find where to put the item
pos := start
for i = start+1 to len-1
if v!i < item then pos := pos + 1
// Put the item there or right after any duplicates
while item = v!pos do pos := pos + 1
temp := v!pos
v!pos := item
item := temp
writes := writes + 1
$)
$)
resultis writes
$)
let writevec(v, len) be
$( for i = 0 to len-1 do
writef("%N ", v!i)
wrch('*N')
$)
let start() be
$( let v = table 0,1,2,2,2,2,1,9,3,5,5,8,4,7,0,6
let l = 16
let w = ?
writes("Before: ") ; writevec(v, l)
w := cyclesort(v)
writes("After: ") ; writevec(v, l)
writef("Writes: %N*N", w)
$)</syntaxhighlight>
{{out}}
<pre>Before: 0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6
After: 0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9
Writes: 10</pre>
=={{header|C}}==
{{trans|NetRexx}}
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>
int cycleSort(int * list, size_t l_len);
void show_array(int * array, size_t a_len);
/*
* Sort an array in place and return the number of writes.
*/
int cycleSort(int * list, size_t l_len)
{
int writes = 0;
/* Loop through the array to find cycles to rotate. */
for (int cycleStart = 0; cycleStart < l_len - 1; ++cycleStart)
{
int item = list[cycleStart];
int swap_tmp;
/* Find where to put the item. */
int pos = cycleStart;
for (int i = cycleStart + 1; i < l_len; ++i)
{
if (list[i] < item)
{
++pos;
}
}
/* If the item is already there, this is not a cycle. */
if (pos == cycleStart)
{
continue;
}
/* Otherwise, put the item there or right after any duplicates. */
while (item == list[pos])
{
++pos;
}
swap_tmp = list[pos];
list[pos] = item;
item = swap_tmp;
++writes;
/* Rotate the rest of the cycle. */
while (pos != cycleStart)
{
/* Find where to put the item. */
pos = cycleStart;
for (int i = cycleStart + 1; i < l_len; ++i)
{
if (list[i] < item)
{
++pos;
}
}
/* Put the item there or right after any duplicates. */
while (item == list[pos])
{
++pos;
}
swap_tmp = list[pos];
list[pos] = item;
item = swap_tmp;
++writes;
}
}
return writes;
}
int main(int argc, char ** argv)
{
int arr[] = { 0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6, };
int arr_k = sizeof(arr) / sizeof(arr[0]);
int writes;
show_array(arr, arr_k);
writes = cycleSort(arr, arr_k);
show_array(arr, arr_k);
printf("writes: %d\n", writes);
return 0;
}
void show_array(int * array, size_t a_len)
{
for (int ix = 0; ix < a_len; ++ix)
{
printf("%d ", array[ix]);
}
putchar('\n');
return;
}
</syntaxhighlight>
{{out}}
<pre>
0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6
0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9
writes: 10
</pre>
=={{header|C++}}==
Based on example code on Wikipedia
<syntaxhighlight lang="cpp">
#include <time.h>
#include <iostream>
#include <vector>
using namespace std;
class cSort
{
public:
void doIt( vector<unsigned> s )
{
sq = s; display(); c_sort();
cout << "writes: " << wr << endl; display();
}
private:
void display()
{
copy( sq.begin(), sq.end(), ostream_iterator<unsigned>( std::cout, " " ) );
cout << endl;
}
void c_sort()
{
wr = 0;
unsigned it, p, vlen = static_cast<unsigned>( sq.size() );
for( unsigned c = 0; c < vlen - 1; c++ )
{
it = sq[c];
p = c;
for( unsigned d = c + 1; d < vlen; d++ )
if( sq[d] < it ) p++;
if( c == p ) continue;
doSwap( p, it );
while( c != p )
{
p = c;
for( unsigned e = c + 1; e < vlen; e++ )
if( sq[e] < it ) p++;
doSwap( p, it );
}
}
}
void doSwap( unsigned& p, unsigned& it )
{
while( sq[p] == it ) p++;
swap( it, sq[p] );
wr++;
}
vector<unsigned> sq;
unsigned wr;
};
int main(int argc, char ** argv)
{
srand( static_cast<unsigned>( time( NULL ) ) );
vector<unsigned> s;
for( int x = 0; x < 20; x++ )
s.push_back( rand() % 100 + 21 );
cSort c; c.doIt( s );
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
38 119 38 33 33 28 24 101 108 120 99 59 69 24 117 22 90 94 78 75
writes: 19
22 24 24 28 33 33 38 38 59 69 75 78 90 94 99 101 108 117 119 120
</pre>
=={{header|D}}==
This version doesn't use Phobos algorithms beside 'swap'. Algorithms can be used to find where to put the item1 and
{{trans|Python}}
<
/// Sort an array in place and return the number of writes.
Line 60 ⟶ 786:
writefln("%s\nusing %d writes.", xs, nWrites);
}
}</
{{out}}
<pre>[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
Line 66 ⟶ 792:
[0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9]
using 10 writes.</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang=text>
proc cyclesort . a[] .
for cs = 1 to len a[] - 1
item = a[cs]
pos = cs
for i = cs + 1 to len a[]
if a[i] < item
pos += 1
.
.
if pos <> cs
while item = a[pos]
pos += 1
.
t = a[pos]
a[pos] = item
item = t
while pos <> cs
pos = cs
for i = cs + 1 to len a[]
if a[i] < item
pos += 1
.
.
while item = a[pos]
pos += 1
.
t = a[pos]
a[pos] = item
item = t
.
.
.
.
d[] = [ 88 18 31 44 4 0 8 81 14 78 20 76 84 33 73 75 82 5 62 70 ]
cyclesort d[]
print d[]
</syntaxhighlight>
{{out}}
<pre>
[ 0 4 5 8 14 18 20 31 33 44 62 70 73 75 76 78 81 82 84 88 ]
</pre>
=={{header|Elixir}}==
{{trans|Ruby}}
<syntaxhighlight lang="elixir">defmodule Sort do
def cycleSort(list) do
tuple = List.to_tuple(list)
# Loop through the array to find cycles to rotate.
{data,writes} = Enum.reduce(0 .. tuple_size(tuple)-2, {tuple,0}, fn cycleStart,{data,writes} ->
item = elem(data, cycleStart)
pos = find_pos(data, cycleStart, item)
if pos == cycleStart do
# If the item is already there, this is not a cycle.
{data, writes}
else
# Otherwise, put the item there or right after any duplicates.
{data, item} = swap(data, pos, item)
rotate(data, cycleStart, item, writes+1)
end
end)
{Tuple.to_list(data), writes}
end
# Rotate the rest of the cycle.
defp rotate(data, cycleStart, item, writes) do
pos = find_pos(data, cycleStart, item)
{data, item} = swap(data, pos, item)
if pos==cycleStart, do: {data, writes+1},
else: rotate(data, cycleStart, item, writes+1)
end
# Find where to put the item.
defp find_pos(data, cycleStart, item) do
cycleStart + Enum.count(cycleStart+1..tuple_size(data)-1, &elem(data, &1) < item)
end
# Put the item there or right after any duplicates.
defp swap(data, pos, item) when elem(data, pos)==item, do: swap(data, pos+1, item)
defp swap(data, pos, item) do
{put_elem(data, pos, item), elem(data, pos)}
end
end
IO.inspect a = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
{b, writes} = Sort.cycleSort(a)
IO.puts "writes : #{writes}"
IO.inspect b</syntaxhighlight>
{{out}}
<pre>
[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
writes : 10
[0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9]
</pre>
=={{header|FreeBASIC}}==
Uses algorithm in Wikipedia article:
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
' sort an array in place and return the number of writes
Function cycleSort(array() As Integer) As Integer
Dim length As Integer = UBound(array) - LBound(array) + 1
If Length = 0 Then Return 0
Dim As Integer item, position, writes = 0
' loop through the array to find cycles to rotate
For cycleStart As Integer = LBound(array) To UBound(array) - 1
item = array(cycleStart)
' find where to put the item
position = cycleStart
For i As Integer = cycleStart + 1 To UBound(array)
If array(i) < item Then position += 1
Next i
' If the item is already there, this is not a cycle
If position = cycleStart Then Continue For
' Otherwise, put the item there or right after any duplicates
While item = array(position)
position += 1
Wend
Swap array(position), item
writes += 1
'rotate the rest of the cycle
While position <> cycleStart
' Find where to put the item
position = cycleStart
For i As Integer = cycleStart + 1 To UBound(array)
If array(i) < item Then position += 1
Next i
' Put the item there or right after any duplicates
While item = array(position)
position += 1
Wend
Swap array(position), item
writes +=1
Wend
Next cycleStart
Return writes
End Function
Sub printArray(array() As Integer)
For i As Integer = LBound(array) To UBound(array)
Print Str(array(i)); " ";
Next
Print
End Sub
Dim array(1 To 16) As Integer = {0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6}
printArray(array())
Dim writes As Integer = cycleSort(array())
Print "After sorting with"; writes; " writes :"
printArray(array())
Print
Dim array2(1 To 20) As Integer = {38, 119, 38, 33, 33, 28, 24, 101, 108, 120, 99, 59, 69, 24, 117, 22, 90, 94, 78, 75}
printArray(array2())
writes = cycleSort(array2())
Print "After sorting with"; writes; " writes :"
printArray(array2())
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
{{out}}
<pre>
0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6
After sorting with 10 writes :
0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9
38 119 38 33 33 28 24 101 108 120 99 59 69 24 117 22 90 94 78 75
After sorting with 19 writes :
22 24 24 28 33 33 38 38 59 69 75 78 90 94 99 101 108 117 119 120
</pre>
=={{header|Go}}==
This implementation was translated from the example code on Wikipedia.
<
import (
Line 132 ⟶ 1,038:
fmt.Printf("writes %d\n", cyclesort(ints))
fmt.Println(ints)
}</
{{out}}
Line 142 ⟶ 1,048:
Note: output may be different due to the random numbers used.
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">class CycleSort {
static void main(String[] args) {
int[] arr = [5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]
println(Arrays.toString(arr))
int writes = cycleSort(arr)
println(Arrays.toString(arr))
println("writes: " + writes)
}
static int cycleSort(int[] a) {
int writes = 0
for (int cycleStart = 0; cycleStart < a.length - 1; cycleStart++) {
int val = a[cycleStart]
// count the number of values that are smaller than val
// since cycleStart
int pos = cycleStart
for (int i = cycleStart + 1; i < a.length; i++) {
if (a[i] < val) {
pos++
}
}
// there aren't any
if (pos == cycleStart) {
continue
}
// skip duplicates
while (val == a[pos]) {
pos++
}
// put val into final position
int tmp = a[pos]
a[pos] = val
val = tmp
writes++
// repeat as long as we can find values to swap
// otherwise start new cycle
while (pos != cycleStart) {
pos = cycleStart
for (int i = cycleStart + 1; i < a.length; i++) {
if (a[i] < val) {
pos++
}
}
while (val == a[pos]) {
pos++
}
tmp = a[pos]
a[pos] = val
val = tmp
writes++
}
}
return writes
}
}</syntaxhighlight>
{{out}}
<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9]
writes: 14</pre>
=={{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:
<syntaxhighlight 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
)</syntaxhighlight>
{{out|Example use}}
<syntaxhighlight 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</syntaxhighlight>
Meanwhile, if we just wanted the "value at a time swapping" mechanism,
an idiomatic approach might look something like this:
<syntaxhighlight 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
)</syntaxhighlight>
{{out|Example use}}
<syntaxhighlight 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</syntaxhighlight>
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:
<syntaxhighlight 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
)</syntaxhighlight>
{{out|Example use}}
<syntaxhighlight 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</syntaxhighlight>
Note that we've saved a write in this case, by following the wikipedia algorithm.
=={{header|Java}}==
<syntaxhighlight lang="java">import java.util.Arrays;
public class CycleSort {
public static void main(String[] args) {
int[] arr = {5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1};
System.out.println(Arrays.toString(arr));
int writes = cycleSort(arr);
System.out.println(Arrays.toString(arr));
System.out.println("writes: " + writes);
}
static int cycleSort(int[] a) {
int writes = 0;
for (int cycleStart = 0; cycleStart < a.length - 1; cycleStart++) {
int val = a[cycleStart];
// count the number of values that are smaller than val
// since cycleStart
int pos = cycleStart;
for (int i = cycleStart + 1; i < a.length; i++)
if (a[i] < val)
pos++;
// there aren't any
if (pos == cycleStart)
continue;
// skip duplicates
while (val == a[pos])
pos++;
// put val into final position
int tmp = a[pos];
a[pos] = val;
val = tmp;
writes++;
// repeat as long as we can find values to swap
// otherwise start new cycle
while (pos != cycleStart) {
pos = cycleStart;
for (int i = cycleStart + 1; i < a.length; i++)
if (a[i] < val)
pos++;
while (val == a[pos])
pos++;
tmp = a[pos];
a[pos] = val;
val = tmp;
writes++;
}
}
return writes;
}
}</syntaxhighlight>
{{out}}
<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9]
writes: 14</pre>
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
The following implementation is based on the [[#Wren|Wren]] entry except for the
use of `swap`, which exposes a bug in the Wren version (as of 2021.09.12) regarding `writes`.
<syntaxhighlight lang="jq">
# Output: {a: sortedInput, write: numberOfSwaps}
def cycleSort:
def swap(f;g): g as $t | g = f | f = $t | .writes += 1;
{ a: ., writes: 0, len: length }
| reduce range(0; .len - 1) as $cs (.;
.item = .a[$cs]
| .pos = $cs
| reduce range($cs+1; .len) as $i (.;
if .a[$i] < .item then .pos += 1 else . end )
| if .pos != $cs
then until (.item != .a[.pos]; .pos += 1)
| swap(.a[.pos]; .item)
| until (.pos == $cs;
.pos = $cs
| reduce range($cs+1; .len) as $i (.;
if .a[$i] < .item then .pos += 1 else . end)
| until (.item != .a[.pos]; .pos += 1)
| swap(.a[.pos]; .item) )
else .
end )
| {a, writes} ;</syntaxhighlight>
'''The Task'''
<syntaxhighlight lang="jq">[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6],
[4, 65, 2, -31, 0, 99, 2, 83, 782, 1],
[7, 5, 2, 6, 1, 4, 2, 6, 3]
| "Before : \(.)",
(cycleSort
| "After : \(.a)",
"Writes : \(.writes)",
"")</syntaxhighlight>
{{out}}
<pre>
Before : [0,1,2,2,2,2,1,9,3.5,5,8,4,7,0,6]
After : [0,0,1,1,2,2,2,2,3.5,4,5,6,7,8,9]
Writes : 10
Before : [4,65,2,-31,0,99,2,83,782,1]
After : [-31,0,1,2,2,4,65,83,99,782]
Writes : 9
Before : [7,5,2,6,1,4,2,6,3]
After : [1,2,2,3,4,5,6,6,7]
Writes : 7
</pre>
=={{header|Julia}}==
{{works with|Julia|0.6}}
<syntaxhighlight lang="julia">function cyclesort!(v::Vector)
writes = 0
for (cyclestart, item) in enumerate(v)
pos = cyclestart
for item2 in v[cyclestart + 1:end]
if item2 < item pos += 1 end
end
if pos == cyclestart continue end
while item == v[pos]
pos += 1
end
v[pos], item = item, v[pos]
writes += 1
while pos != cyclestart
pos = cyclestart
for item2 in v[cyclestart + 1:end]
if item2 < item pos += 1 end
end
while item == v[pos]
pos += 1
end
v[pos], item = item, v[pos]
writes += 1
end
end
return v
end
v = rand(-10:10, 10)
println("# unordered: $v\n -> ordered: ", cyclesort!(v))</syntaxhighlight>
{{out}}
<pre># unordered: [-2, -2, -5, -9, 8, 7, 2, -1, 3, -6]
-> ordered: [-9, -6, -5, -2, -2, -1, 2, 3, 7, 8]</pre>
=={{header|Kotlin}}==
Translation of the algorithm in the Wikipedia article:
<syntaxhighlight lang="scala">// version 1.1.0
/** Sort an array in place and return the number of writes */
fun <T : Comparable<T>> cycleSort(array: Array<T>): Int {
var writes = 0
// Loop through the array to find cycles to rotate.
for (cycleStart in 0 until array.size - 1) {
var item = array[cycleStart]
// Find where to put the item.
var pos = cycleStart
for (i in cycleStart + 1 until array.size) if (array[i] < item) pos++
// If the item is already there, this is not a cycle.
if (pos == cycleStart) continue
// Otherwise, put the item there or right after any duplicates.
while (item == array[pos]) pos++
val temp = array[pos]
array[pos] = item
item = temp
writes++
// Rotate the rest of the cycle.
while (pos != cycleStart) {
// Find where to put the item.
pos = cycleStart
for (i in cycleStart + 1 until array.size) if (array[i] < item) pos++
// Otherwise, put the item there or right after any duplicates.
while (item == array[pos]) pos++
val temp2 = array[pos]
array[pos] = item
item = temp2
writes++
}
}
return writes
}
fun <T : Comparable<T>> printResults(array: Array<T>) {
println(array.asList())
val writes = cycleSort(array)
println("After sorting with $writes writes:")
println(array.asList())
println()
}
fun main(args: Array<String>) {
val array = arrayOf(0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6)
printResults(array)
val array2 = arrayOf(5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1)
printResults(array2)
val array3 = "the quick brown fox jumps over the lazy dog".split(' ').toTypedArray()
printResults(array3)
val array4 = "sphinx of black quartz judge my vow".replace(" ", "").toCharArray().distinct().toTypedArray()
printResults(array4)
}</syntaxhighlight>
{{out}}
<pre>
[0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6]
After sorting with 10 writes:
[0, 0, 1, 1, 2, 2, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9]
[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]
After sorting with 14 writes:
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9]
[the, quick, brown, fox, jumps, over, the, lazy, dog]
After sorting with 8 writes:
[brown, dog, fox, jumps, lazy, over, quick, the, the]
[s, p, h, i, n, x, o, f, b, l, a, c, k, q, u, r, t, z, j, d, g, e, m, y, v, w]
After sorting with 26 writes:
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z]
</pre>
=={{header|Lua}}==
{{trans|Java}}
<syntaxhighlight lang="lua">function printa(a)
io.write("[")
for i,v in ipairs(a) do
if i > 1 then
io.write(", ")
end
io.write(v)
end
io.write("]")
end
function cycle_sort(a)
local writes = 0
local cycle_start = 0
while cycle_start < #a - 1 do
local val = a[cycle_start + 1]
-- count the number of values that are smaller than val since cycle_start
local pos = cycle_start
local i = cycle_start + 1
while i < #a do
if a[i + 1] < val then
pos = pos + 1
end
i = i + 1
end
-- there aren't any
if pos ~= cycle_start then
-- skip duplicates
while val == a[pos + 1] do
pos = pos + 1
end
-- put val in final position
a[pos + 1], val = val, a[pos + 1]
writes = writes + 1
-- repeat as long as we can find values to swap
-- otherwise start new cycle
while pos ~= cycle_start do
pos = cycle_start
local i = cycle_start + 1
while i < #a do
if a[i + 1] < val then
pos = pos + 1
end
i = i + 1
end
while val == a[pos + 1] do
pos = pos + 1
end
a[pos + 1], val = val, a[pos + 1]
writes = writes + 1
end
end
cycle_start = cycle_start + 1
end
return writes
end
arr = {5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1}
printa(arr)
print()
writes = cycle_sort(arr)
printa(arr)
print()
print("writes: " .. writes)</syntaxhighlight>
{{out}}
<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9]
writes: 14</pre>
=={{header|NetRexx}}==
Direct translation of [[wp:Cycle sort|the Wikipedia entry]] example
<syntaxhighlight lang="netrexx">/* Rexx */
options replace format comments java crossref symbols nobinary
runSample(arg)
return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- Sort an array in place and return the number of writes.
method cycleSort(array = Rexx[]) public static
writes = 0
-- Loop through the array to find cycles to rotate.
loop cycleStart = 0 to array.length - 1 - 1
item = array[cycleStart]
-- Find where to put the item.
pos = cycleStart
loop i = cycleStart + 1 to array.length - 1
if array[i] < item then
pos = pos + 1
end i
-- If the item is already there, this is not a cycle.
if pos == cycleStart then
iterate
-- Otherwise, put the item there or right after any duplicates.
loop while item == array[pos]
pos = pos + 1
end
swap_tmp = array[pos]
array[pos] = item
item = swap_tmp
writes = writes + 1
-- Rotate the rest of the cycle.
loop while pos \= cycleStart
-- Find where to put the item.
pos = cycleStart
loop i = cycleStart + 1 to array.length - 1
if array[i] < item then
pos = pos + 1
end i
-- Put the item there or right after any duplicates.
loop while item == array[pos]
pos = pos + 1
end
swap_tmp = array[pos]
array[pos] = item
item = swap_tmp
writes = writes + 1
end
end cycleStart
return writes
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) public static
samples = ArrayList()
samples.add([1, 9, 3, 5, 8, 4, 7, 0, 6, 2])
samples.add([0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6])
samples.add(['Greygill Hole', 'Ogof Draenen', 'Ogof Ffynnon Ddu', 'Malham Tarn Pot'])
samples.add([-3.14 ,3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4])
samples.add(['George Washington: Virginia', 'John Adams: Massachusetts', 'Thomas Jefferson: Virginia', 'James Madison: Virginia', 'James Monroe: Virginia'])
list = Rexx[]
loop i_ = 0 to samples.size() - 1
list = Rexx[] samples.get(i_)
say 'Input list ' Arrays.asList(list)
writes = cycleSort(list)
say 'Sorted list' Arrays.asList(list)
say 'Total number of writes:' writes
say
end i_
return
</syntaxhighlight>
{{out}}
<pre>
Input list [1, 9, 3, 5, 8, 4, 7, 0, 6, 2]
Sorted list [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Total number of writes: 10
Input list [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
Sorted list [0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9]
Total number of writes: 10
Input list [Greygill Hole, Ogof Draenen, Ogof Ffynnon Ddu, Malham Tarn Pot]
Sorted list [Greygill Hole, Malham Tarn Pot, Ogof Draenen, Ogof Ffynnon Ddu]
Total number of writes: 3
Input list [-3.14, 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4]
Sorted list [-3.14, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9]
Total number of writes: 34
Input list [George Washington: Virginia, John Adams: Massachusetts, Thomas Jefferson: Virginia, James Madison: Virginia, James Monroe: Virginia]
Sorted list [George Washington: Virginia, James Madison: Virginia, James Monroe: Virginia, John Adams: Massachusetts, Thomas Jefferson: Virginia]
Total number of writes: 4</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">proc cycleSort[T](a: var openArray[T]): int =
var position, writes: int = 0
var item: T
for cycleStart in a.low..a.high - 1:
item = a[cycleStart]
position = cycleStart
for i in cycleStart + 1..a.high:
if a[i] < item:
inc position
if position == cycleStart:
continue
while item == a[position]:
inc position
swap a[position], item
inc writes
while position != cycleStart:
position = cycleStart
for i in cycleStart + 1..a.high:
if a[i] < item:
inc position
while item == a[position]:
inc position
swap a[position], item
inc writes
result = writes
var array1 = @[1, 9, 3, 5, 8, 4, 7, 0, 6, 2]
var array2 = @[0'f64, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
var array3 = @["Greygill Hole", "Ogof Draenen", "Ogof Ffynnon Ddu", "Malham Tarn Pot"]
var array4 = @[-3.14 ,3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4]
var array5 = @["George Washington: Virginia", "John Adams: Massachusetts", "Thomas Jefferson: Virginia", "James Madison: Virginia", "James Monroe: Virginia"]
var writes = 0
echo "Original: ", $array1
writes = array1.cycleSort()
echo "Sorted: ", $array1
echo "Total number of writes: ", writes, "\n"
echo "Original: ", $array2
writes = array2.cycleSort()
echo "Sorted: ", $array2
echo "Total number of writes: ", writes, "\n"
echo "Original: ", $array3
writes = array3.cycleSort()
echo "Sorted: ", $array3
echo "Total number of writes: ", writes, "\n"
echo "Original: ", $array4
writes = array4.cycleSort()
echo "Sorted: ", $array4
echo "Total number of writes: ", writes, "\n"
echo "Original: ", $array5
writes = array5.cycleSort()
echo "Sorted: ", $array5
echo "Total number of writes: ", writes</syntaxhighlight>
{{out}}
<pre>Original: @[1, 9, 3, 5, 8, 4, 7, 0, 6, 2]
Sorted: @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Total number of writes: 10
Original: @[0.0, 1.0, 2.0, 2.0, 2.0, 2.0, 1.0, 9.0, 3.5, 5.0, 8.0, 4.0, 7.0, 0.0, 6.0]
Sorted: @[0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 3.5, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0]
Total number of writes: 10
Original: @["Greygill Hole", "Ogof Draenen", "Ogof Ffynnon Ddu", "Malham Tarn Pot"]
Sorted: @["Greygill Hole", "Malham Tarn Pot", "Ogof Draenen", "Ogof Ffynnon Ddu"]
Total number of writes: 3
Original: @[-3.14, 3.0, 1.0, 4.0, 1.0, 5.0, 9.0, 2.0, 6.0, 5.0, 3.0, 5.0, 8.0, 9.0, 7.0, 9.0, 3.0, 2.0, 3.0, 8.0, 4.0, 6.0, 2.0, 6.0, 4.0, 3.0, 3.0, 8.0, 3.0, 2.0, 7.0, 9.0, 5.0, 0.0, 2.0, 8.0, 8.0, 4.0]
Sorted: @[-3.14, 0.0, 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 2.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 4.0, 4.0, 5.0, 5.0, 5.0, 5.0, 6.0, 6.0, 6.0, 7.0, 7.0, 8.0, 8.0, 8.0, 8.0, 8.0, 9.0, 9.0, 9.0, 9.0]
Total number of writes: 34
Original: @["George Washington: Virginia", "John Adams: Massachusetts", "Thomas Jefferson: Virginia", "James Madison: Virginia", "James Monroe: Virginia"]
Sorted: @["George Washington: Virginia", "James Madison: Virginia", "James Monroe: Virginia", "John Adams: Massachusetts", "Thomas Jefferson: Virginia"]
Total number of writes: 4</pre>
=={{header|Objeck}}==
{{trans|Java}}
<syntaxhighlight lang="objeck">class Test {
function : Main(args : String[]) ~ Nil {
arr := [5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1];
arr->ToString()->PrintLine();
writes := CycleSort(arr);
"writes: {$writes}"->PrintLine();
arr->ToString()->PrintLine();
}
function : CycleSort(a : Int[]) ~ Int {
writes := 0;
for(cycleStart := 0; cycleStart < a->Size() - 1; cycleStart+=1;) {
val := a[cycleStart];
pos := cycleStart;
for(i := cycleStart + 1; i < a->Size(); i+=1;) {
if(a[i] < val) {
pos++;
};
};
if(pos <> cycleStart) {
while(val = a[pos]) {
pos+=1;
};
tmp := a[pos];
a[pos] := val;
val := tmp;
writes+=1;
while(pos <> cycleStart) {
pos := cycleStart;
for(i := cycleStart + 1; i < a->Size(); i+=1;) {
if(a[i] < val) {
pos+=1;
};
};
while(val = a[pos]) {
pos++;
};
tmp := a[pos];
a[pos] := val;
val := tmp;
writes++;
};
};
};
return writes;
}
}</syntaxhighlight>
<pre>
[5,0,1,2,2,3,5,1,1,0,5,6,9,8,0,1]
writes: 14
[0,0,0,1,1,1,1,2,2,3,5,5,5,6,8,9]
</pre>
=={{header|ooRexx}}==
<
* 13.06.2014 Walter Pachl
* Modified from Rexx Version 2
Line 208 ⟶ 1,844:
Say format(i,2) a.i
End
Return</
{{out}}
<pre>
Line 228 ⟶ 1,864:
This took 4 writes.</pre>
=={{header|Perl
This is based on the Wikipedia pseudocode.
<syntaxhighlight lang="perl">use strict;
use warnings;
sub cycleSort :prototype(@) {
my ($array) = @_;
my $writes = 0;
my @alreadysorted;
# For each index except the last:
for my $start ( 0 .. $#$array - 1 ) {
next if $alreadysorted[$start];
my $item = $array->[$start];
# If there are N items less than $item, then we
# must move $item N items rightward.
my $pos = $start + grep $array->[$_] lt $item, $start + 1 .. $#$array;
# If the item is where it should be, continue.
next if $pos == $start;
# If $item is one of several repetitions, move it to the right
# of the last repeat.
++$pos while $item eq $array->[ $pos ];
# Store $item at $pos, where it belongs, and fetch the
# value that had been at $pos, and put it in $item.
($array->[ $pos ], $item) = ($item, $array->[ $pos ]);
++$writes;
# Whatever $item is now, it certainly doesn't belong at $pos;
do {
# Find the correct $pos,
$pos = $start + grep $array->[$_] lt $item, $start+1 .. $#$array;
++$pos while $item eq $array->[ $pos ];
# Swap the value there with $item,
($array->[ $pos ] , $item ) = ($item, $array->[ $pos ]);
# And mark $pos as having the correct value in it..
$alreadysorted[ $pos ] = 1;
++$writes;
# The loop ends after we have just written an item to $start
} while $pos != $start;
}
$writes;
}
use List::Util 'shuffle';
my @test = shuffle( ('a'..'z') x 2 );
print "Before sorting: @test\n";
print "There were ", cycleSort( \@test ), " writes\n";
print "After sorting: @test\n";
</syntaxhighlight>
{{out}}
<pre>Before sorting: a t d b f g y l t p w c r r x i y j k i z q e v a f o q j u x k m h s u v z g m b o l e n h p n c s w d
There were 50 writes
After sorting: a a b b c c d d e e f f g g h h i i j j k k l l m m n n o o p p q q r r s s t t u u v v w w x x y y z z</pre>
=={{header|Phix}}==
{{trans|NetRexx}}
plus some factoring out of common code
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">array</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">item</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">writes</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">find_item</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">cycle_start</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Find where to put the item.</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_start</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">cycle_start</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">item</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">put_item</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- Put the item there or right after any duplicates.</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">item</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">ap</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">item</span>
<span style="color: #000000;">item</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ap</span>
<span style="color: #000000;">writes</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000080;font-style:italic;">-- Sort an array in place and return the number of writes.</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">cycleSort</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">writes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">array</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Loop through the array to find cycles to rotate.</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">cycle_start</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">item</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cycle_start</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">find_item</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle_start</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- If the item is already there, this is not a cycle.</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">cycle_start</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">put_item</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- Rotate the rest of the cycle.</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">cycle_start</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">find_item</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle_start</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">put_item</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">samples</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3.5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"Greygill Hole"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Ogof Draenen"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Ogof Ffynnon Ddu"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Malham Tarn Pot"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">3.14</span> <span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">samples</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">array</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">samples</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Input list "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">array</span>
<span style="color: #000000;">cycleSort</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Sorted list "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">array</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Total number of writes: %d (out of %d)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">writes</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Input list {1,9,3,5,8,4,7,0,6,2}
Total number of writes: 10 (out of 10)
Input list {0,1,2,2,2,2,1,9,3.5,5,8,4,7,0,6}
Sorted list {0,0,1,1,2,2,2,2,3.5,4,5,6,7,8,9}
Total number of writes: 10 (out of 15)
Input list {"Greygill Hole","Ogof Draenen","Ogof Ffynnon Ddu","Malham Tarn Pot"}
Sorted list {"Greygill Hole","Malham Tarn Pot","Ogof Draenen","Ogof Ffynnon Ddu"}
Total number of writes: 3 (out of 4)
Input list {-3.14,3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4}
Sorted list {-3.14,0,1,1,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,7,7,8,8,8,8,8,9,9,9,9}
Total number of writes: 34 (out of 38)
Input list {5,0,1,2,2,3,5,1,1,0,5,6,9,8,0,1}
Sorted list {0,0,0,1,1,1,1,2,2,3,5,5,5,6,8,9}
Total number of writes: 14 (out of 16)
Input list {1,1,1,1,1,1}
Sorted list {1,1,1,1,1,1}
Total number of writes: 0 (out of 6)
</pre>
Line 279 ⟶ 2,010:
The Wikipedia algorithm pseudocode is very nearly Python. The main changes needed were to change the name array to vector to stop it obscuring a built-in name, and iterating over an enumerated collection rather than using explicit indices.
<
"Sort a vector in place and return the number of writes."
writes = 0
Line 328 ⟶ 2,059:
else:
print('%r\nIs correctly sorted using cycleSort to'
'\n%r\nUsing %i writes.' % (x, xcopy, writes))</
{{out}}
Line 335 ⟶ 2,066:
[0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9]
Using 10 writes.</pre>
=={{header|Racket}}==
<syntaxhighlight lang="racket">#lang racket/base
(require racket/match)
;; Sort an array in place and return the number of writes.
(define (cycle-sort! v < =?)
(define v-len (vector-length v))
(for/sum ; Loop through the array to find cycles to rotate.
((cycle-start (in-range 0 (sub1 v-len))))
(define item (vector-ref v cycle-start))
(define (find-insertion-point) ; Find where to put the item.
(+ cycle-start
(for/sum
((i (in-range (add1 cycle-start) v-len))
#:when (< (vector-ref v i) item)) 1)))
;; Put the item there or right after any duplicates
(define (insert-after-duplicates pos)
(match (vector-ref v pos)
[(== item =?) (insert-after-duplicates (add1 pos))]
[tmp (vector-set! v pos item) ; / swap
(set! item tmp) ; \ [this is my only write point]
pos]))
(define i-p (find-insertion-point))
(if (= i-p cycle-start)
0 ; If the item is already there, this is not a cycle.
(let loop ; Rotate the rest of the cycle.
((e-p (insert-after-duplicates i-p))
(W 1 #| we've already written once |#))
(if (= e-p cycle-start)
W
(loop (insert-after-duplicates (find-insertion-point))
(add1 W))))))) ; we've written again!
(module+ main
;; This will be random with duplicates
(define A (list->vector (build-list 30 (λ (i) (random 20)))))
A
(cycle-sort! A < =)
A
(define B #(1 1 1 1 1 1))
B
(cycle-sort! B < =))</syntaxhighlight>
{{out}}
<pre>'#(7 17 5 16 14 9 18 10 1 4 10 1 9 3 3 0 1 18 16 12 9 14 14 12 19 2 12 15 16 8)
28
'#(0 1 1 1 2 3 3 4 5 7 8 9 9 9 10 10 12 12 12 14 14 14 15 16 16 16 17 18 18 19)
'#(1 1 1 1 1 1)
0</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub cycle_sort ( @nums ) {
my $writes = 0;
# Loop through the array to find cycles to rotate.
for @nums.kv -> $cycle_start, $item is copy {
# Find where to put the item.
my $pos = $cycle_start
+ @nums[ $cycle_start ^.. * ].grep: * < $item;
# If the item is already there, this is not a cycle.
next if $pos == $cycle_start;
# Otherwise, put the item there or right after any duplicates.
$pos++ while $item == @nums[$pos];
( @nums[$pos], $item ) .= reverse;
$writes++;
# Rotate the rest of the cycle.
while $pos != $cycle_start {
# Find where to put the item.
$pos = $cycle_start
+ @nums[ $cycle_start ^.. * ].grep: * < $item;
# Put the item there or right after any duplicates.
$pos++ while $item == @nums[$pos];
( @nums[$pos], $item ) .= reverse;
$writes++;
}
}
return $writes;
}
my @a = <0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6>;
say @a;
say 'writes ', cycle_sort(@a);
say @a;
</syntaxhighlight>
{{out}}
<pre>0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6
writes 10
0 0 1 1 2 2 2 2 3.5 4 5 6 7 8 9
</pre>
=={{header|REXX}}==
===version 1===
<
* 12.06.2014 Walter Pachl translated from Wikipedia's code
* 20.06.2014 WP corrected (courtesy Alan Sampson)
* 30.05.2017 WP fixed for Classic Rexx (courtesy GS)
**********************************************************************/
list='1 9 3 5 8 4 7 0 6 2'
Line 347 ⟶ 2,180:
End
Say list
Say 'writes='writes
ol=''
Do i=0 To n-1
Line 355 ⟶ 2,189:
Exit
cycleSort: procedure expose array. n
writes = 0
/* Loop through the array to find cycles to rotate. */
do cycleStart=0 to n-2
item = array.cycleStart
/* Find where to put the item. */
pos = cycleStart
Do i=cycleStart+1 to n
if array.i < item Then
pos
End
/* If the item is already there, this is not a cycle. */
if pos == cycleStart Then
Iterate
/* Otherwise, put the item there or right after any duplicates. */
Do while item == array.pos
pos
End
Parse Value array.pos item With item array.pos
writes
/* Rotate the rest of the cycle. */
Do while pos <> cycleStart
/* Find where to put the item. */
pos = cycleStart
Do i=cycleStart + 1 to n-1
if array.i < item Then
pos
End
/* Put the item there or right after any duplicates. */
Do while item == array.pos
pos
End
Parse Value array.pos item With item array.pos
writes
End
End
{{out}}
<pre>1 9 3 5 8 4 7 0 6 2
Line 392 ⟶ 2,238:
===version 2===
This REXX version demonstrates the use of negative numbers and
As a default, the program uses (for the input list) some digits of pi, which for practical purposes, appear random.
<
parse arg z
if z='' then z= -3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4
say 'unsorted list: ' z /*show the original unsorted
w= sortCycle(z) /*W: the
say '
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
sortCycle: procedure expose y; parse arg y;
do i=1 for #; @.i=
do
end /*j*/
do k=c+1 to #;
call .putX
end /*while p\==c*/
end /*c*/
y=@.1; do m=2 for #-1; y=y @.m; end; return mv /*put the array back into the Y
/*──────────────────────────────────────────────────────────────────────────────────────*/
.putX: mv= mv+1; do p=p while x==@.p; end; parse value @.p x with x @.p; return</syntaxhighlight>
<pre>
unsorted list: -3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4
sorted list: -3.14 0 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 7 7 8 8 8 8 8 9 9 9 9
and
</pre>
<pre>
unsorted list: FM Stereo has been around since 1961.
sorted list: 1961. FM Stereo around been has since
and
</pre>
Note (for the above output). This REXX program was executed on an '''ASCII''' machine.
<br>On an '''ASCII''' machine, the order of sorting is numbers, uppercase letters, lowercase letters.<br>
==
<syntaxhighlight lang="ring">
# Project : Sorting algorithms/Cycle sort
array = [0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6]
seearray(array)
writes = cyclesort(array)
see "after sorting with " + writes + " writes :" + nl
seearray(array)
see nl
array2 = [38, 119, 38, 33, 33, 28, 24, 101, 108, 120, 99, 59, 69, 24, 117, 22, 90, 94, 78, 75]
seearray(array2)
writes = cyclesort(array2)
see "after sorting with " + writes + " writes :" + nl
seearray(array2)
func cyclesort(array)
length = len(array)
if length = 0
return 0
ok
writes = 0
for cyclestart = 1 to len(array) - 1
for i = cyclestart + 1 to
ok
next
if position = cyclestart
loop
ok
while item = array[position]
position = position+ 1
end
temp = item
item = array[position]
array[position] = temp
writes = writes + 1
while position != cyclestart
position = cyclestart
for i = cyclestart + 1 to len(array)
if array[i] < item
position = position + 1
ok
next
while item = array[position]
position = position + 1
end
temp = item
item = array[position]
array[position] = temp
writes = writes + 1
end
next
return writes
func seearray(array)
for i = 1 to len(array)
see string(array[i]) + " "
next
see nl
</syntaxhighlight>
Output:
<pre>
0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6
after sorting with 10 writes :
0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9
38 119 38 33 33 28 24 101 108 120 99 59 69 24 117 22 90 94 78 75
after sorting with 19 writes :
22 24 24 28 33 33 38 38 59 69 75 78 90 94 99 101 108 117 119 120
</pre>
=={{header|Ruby}}==
Direct translation of the pseudocode on the Wikipedia.
<syntaxhighlight lang="ruby">def cycleSort!(array)
writes = 0
# Loop through the array to find cycles to rotate.
for cycleStart in 0 .. array.size-2
item = array[cycleStart]
# Find where to put the item.
pos = cycleStart
for i in cycleStart+1 ... array.size
pos += 1 if array[i] < item
end
# If the item is already there, this is not a cycle.
next if pos == cycleStart
# Otherwise, put the item there or right after any duplicates.
pos += 1 while item == array[pos]
array[pos], item = item, array[pos]
writes += 1
# Rotate the rest of the cycle.
while pos != cycleStart
# Find where to put the item.
pos = cycleStart
for i in cycleStart+1 ... array.size
pos += 1 if array[i] < item
end
# Put the item there or right after any duplicates.
pos += 1 while item == array[pos]
array[pos], item = item, array[pos]
writes += 1
end
end
writes
end
p a = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
puts "writes : #{cycleSort!(a)}"
p a</syntaxhighlight>
{{out}}
<pre>
[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
writes : 10
[0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9]
</pre>
=={{header|Scala}}==
Translation of Java version
<syntaxhighlight lang="scala">
def cycleSort(a: Array[Int]): (Array[Int], Int) = {
var writes = 0
for (cycleStart <- 0 until a.length - 1) {
var value = a(cycleStart)
// count the number of values that are smaller than value since cycleStart
var pos = cycleStart
for (i <- cycleStart + 1 until a.length)
if (a(i) < value) pos += 1
// skip if there aren't any
if (pos != cycleStart) {
// skip duplicates
while (a(pos) == value) pos += 1
// put val into final position
val tmp = a(pos)
a(pos) = value
value = tmp
writes += 1
// repeat as long as we can find values to swap
// otherwise start new cycle
while (pos != cycleStart) {
pos = cycleStart
for (i <- cycleStart + 1 until a.length)
if (a(i) < value) pos += 1
while (a(pos) == value) pos += 1
val tmp = a(pos)
a(pos) = value
value = tmp
writes += 1
}
}
}
(a, writes)
}
</syntaxhighlight>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func cycle_sort (array) {
var (writes=0, pos=0)
func f(i, Ref item, bool=false) {
pos = (i + array.slice(i+1).count{ _ < *item })
return(false) if (bool && pos==i)
while (*item == array[pos]) { ++pos }
(array[pos], *item) = (*item, array[pos])
++writes
return true
}
array.each_kv { |i, item|
f(i, \item, true) || next
while (pos != i) {
f(i, \item)
}
}
return writes
}
var a = %n(0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6)
say a.join(' ')
say ('writes ', cycle_sort(a))
say a.join(' ')</syntaxhighlight>
{{out}}
<pre>
0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6
writes 10
0 0 1 1 2 2 2 2 3.5 4 5 6 7 8 9
</pre>
=={{header|Tcl}}==
Direct translation of the pseudocode on the Wikipedia page
<syntaxhighlight lang="tcl">proc cycleSort {listVar} {
upvar 1 $listVar array
set writes 0
# Loop through the array to find cycles to rotate.
for {set cycleStart 0} {$cycleStart < [llength $array]} {incr cycleStart} {
set item [lindex $array $cycleStart]
# Find where to put the item.
set pos $cycleStart
for {set i [expr {$pos + 1}]} {$i < [llength $array]} {incr i} {
incr pos [expr {[lindex $array $i] < $item}]
}
# If the item is already there, this is not a cycle.
if {$pos == $cycleStart} continue
# Otherwise, put the item there or right after any duplicates.
while {$item == [lindex $array $pos]} {
incr pos
}
set tmp [lindex $array $pos]
lset array $pos $item
set item $tmp
incr writes
# Rotate the rest of the cycle.
while {$pos != $cycleStart} {
# Find where to put the item.
set pos $cycleStart
for {set i [expr {$cycleStart + 1}]} {$i < [llength $array]} {incr i} {
incr pos [expr {[lindex $array $i] < $item}]
}
# Put the item there or right after any duplicates.
while {$item == [lindex $array $pos]} {
incr pos
}
set tmp [lindex $array $pos]
lset array $pos $item
set item $tmp
incr writes
}
}
return $writes
}</syntaxhighlight>
'''Demonstrating:'''
<syntaxhighlight lang="tcl">set example {0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6}
puts "Data was: $example"
set writes [cycleSort example]
puts "Data is now: $example"
if {$example eq [lsort -real $example]} {
puts "\twhich is correctly sorted"
} else {
puts "\twhich is the wrong order!"
}
puts "Writes required: $writes"</syntaxhighlight>
{{out}}
<pre>
Data was: 0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6
Data is now: 0 0 1 1 2 2 2 2 3.5 4 5 6 7 8 9
which is correctly sorted
Writes required: 10
</pre>
=={{header|Wren}}==
Translation of the Python code in the Wikipedia article.
<syntaxhighlight lang="wren">var cycleSort = Fn.new { |a|
var writes = 0
var len = a.count
for (cs in 0...len-1) {
var item = a[cs]
var pos = cs
for (i in cs+1...len) {
if (a[i] < item) pos = pos + 1
}
if (pos != cs) {
while (item == a[pos]) pos = pos + 1
var t = a[pos]
a[pos] = item
item = t
while (pos != cs) {
pos = cs
for (i in cs+1...len) {
if (a[i] < item) pos = pos + 1
}
while (item == a[pos]) pos = pos + 1
var t = a[pos]
a[pos] = item
item = t
writes = writes + 1
}
}
}
return writes
}
var array = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (a in array) {
System.print("Before : %(a)")
var w = cycleSort.call(a)
System.print("After : %(a)")
System.print("Writes : %(w)")
System.print()
}</syntaxhighlight>
{{out}}
<pre>
Before : [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
After : [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]
Writes : 7
Before : [7, 5, 2, 6, 1, 4, 2, 6, 3]
After : [1, 2, 2, 3, 4, 5, 6, 6, 7]
Writes : 6
</pre>
=={{header|XPL0}}==
{{trans|Wren}}
<syntaxhighlight lang "XPL0">func CycleSort(A, Len);
int A, Len;
int Writes, I, J, Item, Pos, T;
[Writes:= 0;
for J:= 0 to Len-2 do
[Item:= A(J);
Pos:= J;
for I:= J+1 to Len-1 do
if A(I) < Item then Pos:= Pos+1;
if Pos # J then
[while Item = A(Pos) do Pos:= Pos+1;
T:= A(Pos); A(Pos):= Item; Item:= T;
while Pos # J do
[Pos:= J;
for I:= J+1 to Len-1 do
if A(I) < Item then Pos:= Pos+1;
while Item = A(Pos) do Pos:= Pos+1;
T:= A(Pos); A(Pos):= Item; Item:= T;
Writes:= Writes+1;
];
];
];
return Writes;
];
int As, Lens, A, W, I;
[As:= [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1],
[7, 5, 2, 6, 1, 4, 2, 6, 3] ];
Lens:= [10, 9];
for A:= 0 to 2-1 do
[Text(0, "Before : [");
for I:= 0 to Lens(A)-1 do
[IntOut(0, As(A,I));
Text(0, if I = Lens(A)-1 then "]^m^j" else ", ");
];
W:= CycleSort(As(A), Lens(A));
Text(0, "After : [");
for I:= 0 to Lens(A)-1 do
[IntOut(0, As(A,I));
Text(0, if I = Lens(A)-1 then "]^m^j" else ", ");
];
Text(0, "Writes : "); IntOut(0, W); CrLf(0); CrLf(0);
];
]</syntaxhighlight>
{{out}}
<pre>
Before : [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
After : [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]
Writes : 7
Before : [7, 5, 2, 6, 1, 4, 2, 6, 3]
After : [1, 2, 2, 3, 4, 5, 6, 6, 7]
Writes : 6
</pre>
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Cycle_sort
// by Galileo, 04/2022
sub cyclesort(array())
local writes, lenarray, item, pos, i, prov
lenarray = arraysize(array(), 1)
for cyclestart = 1 to lenarray
item = array(cyclestart)
pos = cyclestart
for i = cyclestart + 1 to lenarray
if array(i) < item pos = pos + 1
next
if pos = cyclestart continue
while item = array(pos)
pos = pos + 1
wend
prov = array(pos) : array(pos) = item : item = prov
writes = writes + 1
while pos != cyclestart
pos = cyclestart
for i = cyclestart + 1 to lenarray
if array(i) < item pos = pos + 1
next
while item = array(pos)
pos = pos + 1
wend
prov = array(pos) : array(pos) = item : item = prov
writes = writes + 1
wend
next
return writes
end sub
sub printArray(array())
local i
for i = 1 to arraysize(array(), 1)
print array(i), " ";
next
print
end sub
dim ints(10)
for i = 1 to 10
ints(i) = int(ran(10))
next
printArray(ints())
print "writes ", cyclesort(ints())
printArray(ints())</syntaxhighlight>
{{out}}
<pre>9 9 9 6 8 1 9 7 3 4
writes 8
1 3 4 6 7 8 9 9 9 9
---Program done, press RETURN---</pre>
|