Sorting Algorithms/Circle Sort: Difference between revisions
Added Algol 68
Drkameleon (talk | contribs) (added Arturo) |
(Added Algol 68) |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 457:
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
</pre>
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # circlesort #
# swaps a and b #
PRIO =:= = 9;
OP =:= = ( REF INT a, b )VOID: BEGIN INT t = a; a := b; b := t END;
# sorts data in-place and returns a reference to data #
OP CIRCLESORT = ( REF[]INT data )REF[]INT:
BEGIN
PROC circlesort = ( REF[]INT data, INT low, high, swaps so far )INT:
IF low >= high THEN swaps so far
ELSE
INT swaps := swaps so far;
INT hi := high;
INT lo := low;
INT mid = ( hi - lo ) OVER 2;
WHILE lo < hi DO
IF data[ lo ] > data[ hi ] THEN
data[ lo ] =:= data[ hi ];
swaps +:= 1
FI;
lo +:= 1;
hi -:= 1
OD;
IF lo = hi AND hi < UPB data THEN
IF data[ lo ] > data[ hi + 1 ] THEN
data[ lo ] =:= data[ hi + 1 ];
swaps +:= 1
FI
FI;
swaps := circlesort( data, low, low + mid, swaps );
swaps := circlesort( data, low + mid + 1, high, swaps )
FI # circlesort # ;
WHILE circlesort( data, LWB data, UPB data, 0 ) > 0 DO SKIP OD;
data
END # CIRCLESORT # ;
# prints the elements of an array of integers separated by spaces #
OP SHOW = ( []INT list )VOID:
FOR i FROM LWB list TO UPB list DO
print( ( " ", whole( list[ i ], 0 ) ) )
OD # SHOW # ;
# tests the CIRCLESORT operator #
PROC test circle sort = ( []INT unsorted )VOID:
BEGIN
[ LWB unsorted : UPB unsorted ]INT data := unsorted;
print( ( "[" ) );
SHOW unsorted;
print( ( " ]", newline, " -> [" ) );
SHOW CIRCLESORT data;
print( ( " ]", newline ) )
END # test circle sort # ;
# task test case #
test circle sort( ( 6, 7, 8, 9, 2, 5, 3, 4, 1 ) );
# test cases from the Action! sample #
test circle sort( ( 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 ) );
test circle sort( ( 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10 ) );
test circle sort( ( 101, 102, 103, 104, 105, 106, 107, 108 ) );
test circle sort( ( 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 ) );
# additional tests #
test circle sort( ( ) );
test circle sort( ( 1 ) )
END
</syntaxhighlight>
{{out}}
<pre>
[ 6 7 8 9 2 5 3 4 1 ]
-> [ 1 2 3 4 5 6 7 8 9 ]
[ 1 4 -1 0 3 7 4 8 20 -6 ]
-> [ -6 -1 0 1 3 4 4 7 8 20 ]
[ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ]
-> [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ]
[ 101 102 103 104 105 106 107 108 ]
-> [ 101 102 103 104 105 106 107 108 ]
[ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ]
-> [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ]
[ ]
-> [ ]
[ 1 ]
-> [ 1 ]
</pre>
Line 1,090 ⟶ 1,178:
readln;
end.</syntaxhighlight>
=={{header|EasyLang}}==
<syntaxhighlight>
global d[] .
func circsort lo hi swaps .
if lo = hi
return swaps
.
high = hi
low = lo
mid = (hi - lo) div 2
while lo < hi
if d[lo] > d[hi]
swap d[lo] d[hi]
swaps += 1
.
lo += 1
hi -= 1
.
if lo = hi
if d[lo] > d[hi + 1]
swap d[lo] d[hi + 1]
swaps += 1
.
.
swaps = circsort low (low + mid) swaps
swaps = circsort (low + mid + 1) high swaps
return swaps
.
d[] = [ -4 -1 1 0 5 -7 -2 4 -6 -3 2 6 3 7 -5 ]
while circsort 1 len d[] 0 > 0
#
.
print d[]
</syntaxhighlight>
{{out}}
<pre>
[ -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ]
</pre>
=={{header|Elixir}}==
Line 2,733 ⟶ 2,860:
=={{header|Wren}}==
<syntaxhighlight lang="
circleSort = Fn.new { |a, lo, hi, swaps|
if (lo == hi) return swaps
Line 2,762 ⟶ 2,889:
}
var
for (a in
System.print("Before: %(a)")
while (circleSort.call(a, 0, a.count-1, 0) != 0) {}
Line 2,777 ⟶ 2,904:
Before: [2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]
After : [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">int Array;
func CircleSort(Lo, Hi, Swaps);
int Lo, Hi, Swaps;
int Low, High, Mid, T;
[if Lo = Hi then return Swaps;
Low:= Lo;
High:= Hi;
Mid:= (Hi-Lo)/2;
while Lo < Hi do
[if Array(Lo) > Array(Hi) then
[T:= Array(Lo); Array(Lo):= Array(Hi); Array(Hi):= T;
Swaps:= Swaps+1;
];
Lo:= Lo+1;
Hi:= Hi-1;
];
if Lo = Hi then
if Array(Lo) > Array(Hi+1) then
[T:= Array(Lo); Array(Lo):= Array(Hi+1); Array(Hi+1):= T;
Swaps:= Swaps+1;
];
Swaps:= CircleSort(Low, Low+Mid, Swaps);
Swaps:= CircleSort(Low+Mid+1, High, Swaps);
return Swaps;
];
int I;
[Array:= [5, -1, 101, -4, 0, 1, 8, 6, 2, 3];
while CircleSort(0, 10-1, 0) # 0 do [];
for I:= 0 to 10-1 do
[IntOut(0, Array(I)); ChOut(0, ^ )];
]</syntaxhighlight>
{{out}}
<pre>
-4 -1 0 1 2 3 5 6 8 101
</pre>
| |||