Sorting algorithms/Cycle sort: Difference between revisions
m
→{{header|Wren}}: 'as' is now a keyword.
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: 'as' is now a keyword.) |
||
| (6 intermediate revisions by 5 users not shown) | |||
Line 286:
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>
Line 1,672 ⟶ 1,825:
use warnings;
sub cycleSort :prototype(@) {
my ($array) = @_;
my $writes = 0;
Line 2,266 ⟶ 2,419:
func f(i, Ref item, bool=false) {
pos = (i + array.
return(false) if (bool && pos==i)
while (*item == array[pos]) { ++pos }
Line 2,276 ⟶ 2,429:
array.each_kv { |i, item|
f(i, \item, true) || next
while (pos
f(i, \item)
}
Line 2,367 ⟶ 2,520:
=={{header|Wren}}==
Translation of the Python code in the Wikipedia article.
<syntaxhighlight lang="
var writes = 0
var len = a.count
Line 2,397 ⟶ 2,550:
}
var
for (a in
System.print("Before : %(a)")
var w = cycleSort.call(a)
Line 2,415 ⟶ 2,568:
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>
| |||