Sorting Algorithms/Circle Sort: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|REXX}}: added whitespace, used consistent spelling of variables (uppercase/lowercase).) |
m (→{{header|Wren}}: Minor tidy) |
||
(17 intermediate revisions by 14 users not shown) | |||
Line 48:
* For more information on Circle sorting, see [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge].
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F circle_sort_backend(&A, Int l, r)
V n = r - l
I n < 2
R 0
V swaps = 0
V m = n I/ 2
L(i) 0 .< m
I A[r - (i + 1)] < A[l + i]
swap(&A[r - (i + 1)], &A[l + i])
swaps++
I (n [&] 1) != 0 & (A[l + m] < A[l + m - 1])
swap(&A[l + m - 1], &A[l + m])
swaps++
R swaps + circle_sort_backend(&A, l, l + m) + circle_sort_backend(&A, l + m, r)
F circle_sort(&l)
V swaps = 0
V s = 1
L s != 0
s = circle_sort_backend(&l, 0, l.len)
swaps += s
R swaps
L(i) 309
V l = Array(0 .< i)
V m = copy(l)
random:shuffle(&l)
V n = copy(l)
circle_sort(&l)
I l != m
print(l.len)
print(n)
print(l)</syntaxhighlight>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program circleSort64.s */
Line 257 ⟶ 294:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Display table before sort.
Line 284 ⟶ 321:
Table sorted.
</pre>
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.
<syntaxhighlight lang="action!">DEFINE MAX_COUNT="100"
INT ARRAY stack(MAX_COUNT)
INT stackSize
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 InitStack()
stackSize=0
RETURN
BYTE FUNC IsEmpty()
IF stackSize=0 THEN
RETURN (1)
FI
RETURN (0)
PROC Push(INT low,high)
stack(stackSize)=low stackSize==+1
stack(stackSize)=high stackSize==+1
RETURN
PROC Pop(INT POINTER low,high)
stackSize==-1 high^=stack(stackSize)
stackSize==-1 low^=stack(stackSize)
RETURN
INT FUNC Partition(INT ARRAY a INT low,high)
INT part,v,i,tmp
v=a(high)
part=low-1
FOR i=low TO high-1
DO
IF a(i)<=v THEN
part==+1
tmp=a(part) a(part)=a(i) a(i)=tmp
FI
OD
part==+1
tmp=a(part) a(part)=a(high) a(high)=tmp
RETURN (part)
PROC CircleSort(INT ARRAY a INT size)
INT swaps,low,high,lo,hi,tmp,mid
InitStack()
DO
swaps=0
Push(0,size-1)
WHILE IsEmpty()=0
DO
Pop(@low,@high)
IF low<high THEN
lo=low hi=high
WHILE lo<hi
DO
IF a(hi)<a(lo) THEN
tmp=a(lo) a(lo)=a(hi) a(hi)=tmp
swaps==+1
FI
lo==+1 hi==-1
OD
IF lo=hi AND a(lo+1)<a(lo) THEN
tmp=a(lo) a(lo)=a(lo+1) a(lo+1)=tmp
swaps==+1
FI
mid=(lo+hi)/2
Push(low,mid)
Push(mid+1,high)
FI
OD
UNTIL swaps=0
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
CircleSort(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/Circle_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|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program circleSort.s */
Line 481 ⟶ 656:
.include "../affichage.inc"
</syntaxhighlight>
<pre>
Display table before sort.
Line 502 ⟶ 677:
Table sorted.
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">innerCircleSort: function [ar, lo, hi, swaps][
localSwaps: swaps
localHi: hi
localLo: lo
if localLo = localHi -> return swaps
high: localHi
low: localLo
mid: (localHi - localLo) / 2
while [localLo < localHi] [
if ar\[localLo] > ar\[localHi] [
tmp: ar\[localLo]
ar\[localLo]: ar\[localHi]
ar\[localHi]: tmp
localSwaps: localSwaps + 1
]
localLo: localLo + 1
localHi: localHi - 1
]
if localLo = localHi [
if ar\[localLo] > ar\[localHi + 1] [
tmp: ar\[localLo]
ar\[localLo]: ar\[localHi + 1]
ar\[localHi + 1]: tmp
localSwaps: localSwaps + 1
]
]
localSwaps: innerCircleSort ar low low + mid localSwaps
localSwaps: innerCircleSort ar low + mid + 1 high localSwaps
return localSwaps
]
circleSort: function [arr][
result: new arr
while [not? zero? innerCircleSort result 0 dec size result 0][]
return result
]
print circleSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">nums := [6, 7, 8, 9, 2, 5, 3, 4, 1]
while circlesort(nums, 1, nums.Count(), 0) ; 1-based
continue
for i, v in nums
output .= v ", "
MsgBox % "[" Trim(output, ", ") "]"
return
circlesort(Arr, lo, hi, swaps){
if (lo = hi)
return swaps
high:= hi
low := lo
mid := Floor((hi - lo) / 2)
while (lo < hi) {
if (Arr[lo] > Arr[hi]){
tempVal := Arr[lo], Arr[lo] := Arr[hi], Arr[hi] := tempVal
swaps++
}
lo++
hi--
}
if (lo = hi)
if (Arr[lo] > Arr[hi+1]){
tempVal := Arr[lo], Arr[lo] := Arr[hi+1], Arr[hi+1] := tempVal
swaps++
}
swaps := circlesort(Arr, low, low+mid, swaps)
swaps := circlesort(Arr, low+mid+1, high, swaps)
return swaps
}</syntaxhighlight>
{{out}}
<pre>[1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>
=={{header|C}}==
<
int circle_sort_inner(int *start, int *end)
Line 536 ⟶ 794:
return 0;
}</
{{out}}
<pre>
Line 542 ⟶ 800:
-4 -1 0 3 6 1 2 8 5 101
-4 -1 0 1 2 3 5 6 8 101
</pre>
=={{header|C#}}==
<syntaxhighlight lang="c#">using System;
using System.Linq;
namespace CircleSort
{
internal class Program
{
public static int[] CircleSort(int[] array)
{
if (array.Length > 0)
while (CircleSortR(array, 0, array.Length - 1, 0) != 0)
continue;
return array;
}
private static int CircleSortR(int[] arr, int lo, int hi, int numSwaps)
{
if (lo == hi)
return numSwaps;
var high = hi;
var low = lo;
var mid = (hi - lo) / 2;
while (lo < hi)
{
if (arr[lo] > arr[hi])
{
(arr[lo], arr[hi]) = (arr[hi], arr[lo]);
numSwaps++;
}
lo++;
hi--;
}
if (lo == hi && arr[lo] > arr[hi + 1])
{
(arr[lo], arr[hi + 1]) = (arr[hi + 1], arr[lo]);
numSwaps++;
}
numSwaps = CircleSortR(arr, low, low + mid, numSwaps);
numSwaps = CircleSortR(arr, low + mid + 1, high, numSwaps);
return numSwaps;
}
private static void Main(string[] args)
{
var sortedArray = CircleSort(new int[] { 6, 7, 8, 9, 2, 5, 3, 4, 1 });
sortedArray.ToList().ForEach(i => Console.Write(i.ToString() + " "));
Console.WriteLine();
var sortedArray2 = CircleSort(new int[] { 2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1 });
sortedArray2.ToList().ForEach(i => Console.Write(i.ToString() + " "));
Console.WriteLine();
var sortedArray3 = CircleSort(new int[] { 2, 3, 3, 5, 5, 1, 1, 7, 7, 6, 6, 4, 4, 0, 0 });
sortedArray3.ToList().ForEach(i => Console.Write(i.ToString() + " "));
Console.ReadKey();
}
}
}</syntaxhighlight>
{{out}}
<pre>
1 2 3 4 5 6 7 8 9
-1 0 1 2 3 4 5 6 7 8 11 12 13 14
0 0 1 1 2 3 3 4 4 5 5 6 6 7 7
</pre>
=={{header|C++}}==
<
int circlesort(int* arr, int lo, int hi, int swaps) {
Line 591 ⟶ 918:
circlesortDriver(arr, sizeof(arr)/sizeof(int));
return 0;
}</
Output:
<pre>6 7 8 9 2 5 3 4 1
Line 598 ⟶ 925:
=={{header|CoffeeScript}}==
<syntaxhighlight lang="text">circlesort = (arr, lo, hi, swaps) ->
if lo == hi
return (swaps)
Line 630 ⟶ 957:
while circlesort(VA,0,VA.length-1,0)
console.log VA</
Output:
<pre>console: -1,1,0,3,4,5,8,12,2,9,6,10,7,13,11,14
Line 637 ⟶ 964:
=={{header|D}}==
<
void circlesort(T)(T[] items) if (isMutable!T) {
Line 686 ⟶ 1,013:
assert(data.isSorted);
}
}</
{{out}}
<pre>[-4, -1, 0, 1, 2, 3, 5, 6, 8, 101]</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
program Sorting_Algorithms;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
function CircleSort(a: TArray<Integer>; lo, hi, swaps: Integer): Integer;
begin
if lo = hi then
exit(swaps);
var high := hi;
var low := lo;
var mid := (hi - lo) div 2;
while lo < hi do
begin
if a[lo] > a[hi] then
begin
var tmp := a[lo];
a[lo] := a[hi];
a[hi] := tmp;
inc(swaps);
end;
inc(lo);
dec(hi);
end;
if lo = hi then
begin
if a[lo] > a[hi + 1] then
begin
var tmp := a[lo];
a[lo] := a[hi + 1];
a[hi + 1] := tmp;
inc(swaps);
end;
end;
swaps := CircleSort(a, low, low + mid, swaps);
swaps := CircleSort(a, low + mid + 1, high, swaps);
result := swaps;
end;
function ToString(a: TArray<Integer>): string;
begin
Result := '[';
for var e in a do
Result := Result + e.ToString + ',';
Result := Result + ']';
end;
const
aa: TArray<TArray<Integer>> = [[6, 7, 8, 9, 2, 5, 3, 4, 1], [2, 14, 4, 6, 8, 1,
3, 5, 7, 11, 0, 13, 12, -1]];
begin
for var a in aa do
begin
write('Original: ');
write(ToString(a));
while CircleSort(a, 0, high(a), 0) <> 0 do
;
writeln;
write('Sorted : ');
write(ToString(a));
writeln(#10#10);
end;
readln;
end.</syntaxhighlight>
=={{header|Elixir}}==
<
def circle_sort(data) do
List.to_tuple(data)
Line 733 ⟶ 1,134:
data = [6, 7, 8, 9, 2, 5, 3, 4, 1]
IO.puts "before sort: #{inspect data}"
IO.puts " after sort: #{inspect Sort.circle_sort(data)}"</
{{out}}
Line 743 ⟶ 1,144:
=={{header|Forth}}==
This one features the newest version of the algorithm on [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge].
<syntaxhighlight lang="text">[UNDEFINED] cell- [IF] : cell- 1 cells - ; [THEN]
defer precedes ( addr addr -- flag )
Line 775 ⟶ 1,176:
: .sample sample /sample cells bounds do i ? 1 cells +loop ;
sample /sample sort .sample</
=={{header|Fortran}}==
<
!
module circlesort
Line 855 ⟶ 1,256:
end program sort
</syntaxhighlight>
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Line 922 ⟶ 1,323:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>unsorted -4 -1 1 0 5 -7 -2 4 -6 -3 2 6 3 7 -5
Line 928 ⟶ 1,329:
=={{header|Go}}==
<
import "fmt"
Line 969 ⟶ 1,370:
fmt.Printf("Sorted : %v\n\n", a)
}
}</
{{out}}
Line 978 ⟶ 1,379:
Original: [2 14 4 6 8 1 3 5 7 11 0 13 12 -1]
Sorted : [-1 0 1 2 3 4 5 6 7 8 11 12 13 14]
</pre>
=={{header|Haskell}}==
This code uses the tortoise-and-the-hare technique to split the input list in two and compare the relevant positions.
<syntaxhighlight lang="haskell">import Data.Bool (bool)
circleSort :: Ord a => [a] -> [a]
circleSort xs = if swapped then circleSort ks else ks
where
(swapped,ks) = go False xs (False,[])
go d [] sks = sks
go d [x] (s,ks) = (s,x:ks)
go d xs (s,ks) =
let (st,_,ls,rs) = halve d s xs xs
in go False ls (go True rs (st,ks))
halve d s (y:ys) (_:_:zs) = swap d y (halve d s ys zs)
halve d s ys [] = (s,ys,[],[])
halve d s (y:ys) [_] = (s,ys,[y | e],[y | not e])
where e = y <= head ys
swap d x (s,y:ys,ls,rs)
| bool (<=) (<) d x y = ( d || s,ys,x:ls,y:rs)
| otherwise = (not d || s,ys,y:ls,x:rs)</syntaxhighlight>
{{out}}
<pre>
>>> circleSort [6,7,8,9,2,5,3,4,1]
[1,2,3,4,5,6,7,8,9]
>>> circleSort [2,14,4,6,8,1,3,5,7,11,0,13,12,-1]
[-1,0,1,2,3,4,5,6,7,8,11,12,13,14]
</pre>
Line 983 ⟶ 1,419:
Of more parsing and atomic data, or less parsing with large data groups the latter produces faster J programs. Consequently each iteration laminates the original with its reverse. It joins the recursive call to the pairwise minima of the left block to the recursive call of the pairwise maxima of the right block, repeating the operations while the output changes. This is sufficient for power of 2 length data. The pre verb adjusts the data length. And post recovers the original data. This implementation discards the "in place" property described at the sourceforge link.
<syntaxhighlight lang="j">
circle_sort =: post power_of_2_length@pre NB. the main sorting verb
power_of_2_length =: even_length_iteration^:_ NB. repeat while the answer changes
Line 989 ⟶ 1,425:
pre =: , (-~ >.&.(2&^.))@# # >./ NB. extend data to next power of 2 length
post =: ({.~ #)~ NB. remove the extra data
</syntaxhighlight>
Examples:
<syntaxhighlight lang="j">
show =: [ smoutput
Line 1,009 ⟶ 1,445:
│0 0 1 1 2 3 3 4 4 5 5 6 6 7 7│0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12│
└─────────────────────────────┴──────────────────────────────────────────────────────┘
</syntaxhighlight>
=={{header|Java}}==
<
public class CircleSort {
Line 1,060 ⟶ 1,496:
arr[idx2] = tmp;
}
}</
<pre>[2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]
Line 1,073 ⟶ 1,509:
"circlesort" as defined in this section can be used to sort any JSON array. In case your jq does not have "until" as a builtin, here is its definition:
<
def _until: if cond then . else (next|_until) end;
_until;</
<
def swap(i;j): .[i] as $t | .[i] = .[j] | .[j] = $t;
Line 1,109 ⟶ 1,545:
| if $swaps == 0 then .
else circlesort
end ;</
'''Example:'''
<
{{out}}
<
["The","brown","dog","fox","jumps","lazy","over","quick","the"]</
=={{header|Julia}}==
{{works with|Julia|0.6}}
<
lo == hi && return swaps
high = hi
Line 1,150 ⟶ 1,586:
v = rand(10)
println("# $v\n -> ", ciclesort!(v))</
{{out}}
Line 1,157 ⟶ 1,593:
=={{header|Kotlin}}==
<
fun<T: Comparable<T>> circleSort(array: Array<T>, lo: Int, hi: Int, nSwaps: Int): Int {
Line 1,200 ⟶ 1,636:
while (circleSort(array2, 0, array2.size - 1, 0) != 0) ;
println("Sorted : ${array2.asList()}")
}</
{{out}}
Line 1,213 ⟶ 1,649:
=={{header|Lua}}==
The first argument to the 'inner' function needs to be a reference to the table as Lua cannot use a pointer to the first element's memory address. Conversely the 'outer' function only needs one argument as the size of the table is innately knowable.
<
function innerCircle (t, lo, hi, swaps)
if lo == hi then return swaps end
Line 1,244 ⟶ 1,680:
local array = {6, 7, 8, 9, 2, 5, 3, 4, 1}
circleSort(array)
print(table.concat(array, " "))</
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[CircleSort, NestedCircleSort]
CircleSort[d_List, l_, h_] :=
Module[{high, low, mid, lo = l, hi = h, data = d},
If[lo == hi, Return[data]];
high = hi;
low = lo;
mid = Floor[(hi - lo)/2];
While[lo < hi,
If[data[[lo]] > data[[hi]],
data[[{lo, hi}]] //= Reverse;
];
lo++;
hi--
];
If[lo == hi,
If[data[[lo]] > data[[hi + 1]],
data[[{lo, hi + 1}]] //= Reverse;
]
];
data = CircleSort[data, low, low + mid];
data = CircleSort[data, low + mid + 1, high];
data
]
NestedCircleSort[{}] := {}
NestedCircleSort[d_List] := FixedPoint[CircleSort[#, 1, Length[#]] &, d]
NestedCircleSort[Echo@{6, 7, 8, 9, 2, 5, 3, 4, 1}]
NestedCircleSort[Echo@{6, 7, 8, 2, 5, 3, 4, 1}]
NestedCircleSort[Echo@{6, 2, 5, 7, 3, 4, 1}]
NestedCircleSort[Echo@{4, 6, 3, 5, 2, 1}]
NestedCircleSort[Echo@{1, 2, 3, 4, 5}]
NestedCircleSort[Echo@{2, 4, 3, 1}]
NestedCircleSort[Echo@{2, 3, 1}]
NestedCircleSort[Echo@{2, 1}]
NestedCircleSort[Echo@{1}]
NestedCircleSort[Echo@{}]</syntaxhighlight>
{{out}}
<pre>>>{6,7,8,9,2,5,3,4,1}
{1,2,3,4,5,6,7,8,9}
>>{6,7,8,2,5,3,4,1}
{1,2,3,4,5,6,7,8}
>>{6,2,5,7,3,4,1}
{1,2,3,4,5,6,7}
>>{4,6,3,5,2,1}
{1,2,3,4,5,6}
>>{1,2,3,4,5}
{1,2,3,4,5}
>>{2,4,3,1}
{1,2,3,4}
>>{2,3,1}
{1,2,3}
>>{2,1}
{1,2}
>>{1}
{1}
>>{}
{}</pre>
=={{header|Nim}}==
<
var localSwaps: int = swaps
var localHi: int = hi
Line 1,285 ⟶ 1,779:
echo "Original: ", $arr[i]
arr[i].circleSort()
echo "Sorted: ", $arr[i], if i != arr.high: "\n" else: ""</
{{out}}
Line 1,296 ⟶ 1,790:
=={{header|Objeck}}==
{{trans|Objeck}}
<
function : Main(args : String[]) ~ Nil {
circleSort([2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]);
Line 1,346 ⟶ 1,840:
}
}
</syntaxhighlight>
Output:
Line 1,358 ⟶ 1,852:
=={{header|PARI/GP}}==
This follows the pseudocode pretty closely.
<
{
local(v=v); \\ share with cs
Line 1,383 ⟶ 1,877:
}
print(example=[6,7,8,9,2,5,3,4,1]);
print(circlesort(example));</
{{out}}
<pre>[6, 7, 8, 9, 2, 5, 3, 4, 1]
Line 1,389 ⟶ 1,883:
=={{header|Pascal}}==
<
{
source file name on linux is ./p.p
Line 1,467 ⟶ 1,961:
writeln();
end.
</syntaxhighlight>
=={{header|Perl}}==
Less flexible than the Raku version, as written does only numeric comparisons.
{{trans|Raku}}
<
our @x; local *x = shift;
my($beg,$end) = @_;
Line 1,494 ⟶ 1,988:
my @a = <16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88>;
while (circlesort(\@a, 0, $#a)) { print join(' ', @a), "\n" }</
{{out}}
<pre>-99 -78 16 20 36 -81 -29 46 25 59 -64 -7 39 26 88 -1 35 85 76 100
Line 1,502 ⟶ 1,996:
=={{header|Phix}}==
<!--<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: #008080;">function</span> <span style="color: #000000;">circle_sort_inner</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">swaps</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">hi</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">high</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">low</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">high</span><span style="color: #0000FF;">-</span><span style="color: #000000;">low</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">hi</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">=</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">alo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">ahi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">alo</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">ahi</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ahi</span>
<span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">alo</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;">"%V level %d, low %d, high %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">array</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">,</span><span style="color: #000000;">low</span><span style="color: #0000FF;">,</span><span style="color: #000000;">high</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">swaps</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: #000000;">lo</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">hi</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: #000000;">swaps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">circle_sort_inner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">low</span><span style="color: #0000FF;">,</span><span style="color: #000000;">low</span><span style="color: #0000FF;">+</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">swaps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">swaps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">circle_sort_inner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">low</span><span style="color: #0000FF;">+</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">high</span><span style="color: #0000FF;">,</span><span style="color: #000000;">swaps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">swaps</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">circle_sort</span><span style="color: #0000FF;">()</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;">"%V <== (initial)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">array</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">circle_sort_inner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</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: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #0000FF;">?</span><span style="color: #008000;">"loop"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</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;">"%V <== (sorted)\n"</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;">procedure</span>
<span style="color: #000000;">array</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: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">101</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">4</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;">8</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;">3</span><span style="color: #0000FF;">}</span>
<span style="color: #000080;font-style:italic;">--array = {-4,-1,1,0,5,-7,-2,4,-6,-3,2,6,3,7,-5}
--array = {6, 7, 8, 9, 2, 5, 3, 4, 1}
--array = {2,14,4,6,8,1,3,5,7,9,10,11,0,13,12,-1}
--array = {"the","quick","brown","fox","jumps","over","the","lazy","dog"}
--array = {0.603704, 0.293639, 0.513965, 0.746246, 0.245282, 0.930508, 0.550878, 0.622534, 0.006089, 0.270426}
--array = shuffle(deep_copy(array))</span>
<span style="color: #000000;">circle_sort</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
Shows the full inner workings: call depth and range being considered, after each swap made.
<pre>
"loop"
"loop"
</pre>
=={{header|Python}}==
The doctest passes with odd and even length lists. As do the random tests. Please see circle_sort.__doc__ for example use and output.
<
#python3
#tests: expect no output.
Line 1,621 ⟶ 2,122:
print(N)
print(L)
</syntaxhighlight>
=={{header|Quackery}}==
Having read the information on [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge] mentioned in the task description, I note that the circle sort is most elegant when sorting an array the length of which is a power of two. Rather than mess with the central element of an odd length array and forego potential parallelisation I chose to pad the array to the nearest power of two with elements that were guaranteed to be in the right place (here, numbers one larger than the largest item in the array and trim it down to size after sorting. Additionally, rather than flagging exchanges, I use an O(n) test to see if a subarray is sorted to avoid unnecessary recursive calls.
The link at the end of the Sourceforge page to a paper on the subject is broken. [https://www.cscjournals.org/manuscript/Journals/IJEA/Volume6/Issue2/IJEA-48.pdf This link works.]
In the demonstration, I sort the characters in a string. In Quackery a string is a particular use of a nest of numbers (dynamic array of bignums). The string is a word from a famously circular novel. It seemed appropriate for such a novel "circle sort".
<syntaxhighlight lang="quackery"> [ dup size 2 < iff
[ drop true ] done
true swap
dup [] != if
[ behead swap witheach
[ tuck > if
[ dip not
conclude ] ] ]
drop ] is sorted ( [ --> b )
[ behead swap witheach
[ 2dup < iff
nip else drop ] ] is largest ( [ --> n )
[ dup largest 1+
over size
dup 1
[ 2dup > while
1 << again ]
nip swap -
dup dip [ of join ]
swap ] is pad ( [ --> n [ )
[ swap dup if
[ negate split drop ] ] is unpad ( n [ --> [ )
[ dup size times
[ i i^ > not iff
conclude done
dup i peek
over i^ peek
2dup < iff
[ rot i poke
i^ poke ]
else 2drop ] ] is reorder ( [ --> [ )
[ pad
[ [ dup sorted if done
reorder
dup size 2 / split
recurse swap
recurse swap join ]
dup sorted until ]
unpad ] is circlesort ( [ --> [ )
$ "bababadalgharaghtakamminarronnkonnbronntonnerronntuonnthunntrovarrhounawnskawntoohoohoordenenthurnuk"
dup echo$ cr
circlesort echo$ cr</syntaxhighlight>
{{out}}
<pre>bababadalgharaghtakamminarronnkonnbronntonnerronntuonnthunntrovarrhounawnskawntoohoohoordenenthurnuk
aaaaaaaaaaaabbbbddeeegghhhhhhhikkkklmmnnnnnnnnnnnnnnnnnnnnnoooooooooooooorrrrrrrrrrrstttttttuuuuuvww
</pre>
=={{header|Racket}}==
Line 1,628 ⟶ 2,194:
(diadic) function can be used to compare... e.g. <code>string<?</code>.
<
(define (circle-sort v0 [<? <])
(define v (vector-copy v0))
Line 1,662 ⟶ 2,228:
(for ([_ 10]) (sort-random-vector))
(circle-sort '#("table" "chair" "cat" "sponge") string<?)</
{{out}}
Line 1,706 ⟶ 2,272:
This does generic comparisons, so it works on any ordered type, including numbers or strings.
<syntaxhighlight lang="raku"
my $swaps = 0;
if $beg < $end {
Line 1,727 ⟶ 2,293:
say @x = <The quick brown fox jumps over the lazy dog.>;
say @x while circlesort(@x, 0, @x.end);</
{{out}}
<pre>16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88
Line 1,740 ⟶ 2,306:
This REXX version will work with any numbers that REXX supports, including negative and/or floating point numbers;
<br>it also will work with character strings.
<
parse arg x /*obtain optional arguments from the CL*/
if x='' | x="," then x= 6 7 8 9 2 5 3 4 1 /*Not specified? Then use the default.*/
Line 1,765 ⟶ 2,331:
swaps= .circleSrt(low, low+mid, swaps) /*sort the lower section. */
swaps= .circleSrt(low+mid+1, high, swaps) /* " " higher " */
return swaps /*the section sorting is done*/</
{{out|output|text= when using the default input:}}
<pre>
Line 1,788 ⟶ 2,354:
=={{header|Ring}}==
<
# Project : Sorting Algorithms/Circle Sort
Line 1,833 ⟶ 2,399:
see svect
see "]" + nl
</syntaxhighlight>
Output:
<pre>
Line 1,840 ⟶ 2,406:
=={{header|Ruby}}==
<
def circle_sort!
while _circle_sort!(0, size-1) > 0
Line 1,870 ⟶ 2,436:
ary = [6, 7, 8, 9, 2, 5, 3, 4, 1]
puts "before sort: #{ary}"
puts " after sort: #{ary.circle_sort!}"</
{{out}}
Line 1,877 ⟶ 2,443:
=={{header|Rust}}==
<
if low == high {
return swaps;
Line 1,918 ⟶ 2,484:
circle_sort(&mut v);
println!("after: {:?}", v);
}</
{{out}}
Line 1,927 ⟶ 2,493:
=={{header|Scala}}==
<
def sort(arr: Array[Int]): Array[Int] = {
Line 1,966 ⟶ 2,532:
println(sort(Array[Int](2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1)).mkString(", "))
}</
=={{header|Sidef}}==
<
var swaps = 0
if (beg < end) {
Line 1,990 ⟶ 2,556:
var strs = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane", "Alice"]
do { say strs } while circlesort(strs)</
{{out}}
<pre>
Line 2,003 ⟶ 2,569:
=={{header|Swift}}==
<
func circSort(low: Int, high: Int, swaps: Int) -> Int {
if low == high {
Line 2,041 ⟶ 2,607:
print("before: \(array2)")
circleSort(&array2)
print(" after: \(array2)")</
{{out}}
Line 2,053 ⟶ 2,619:
=={{header|uBasic/4tH}}==
This one uses the optimized version featured at [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge].
<syntaxhighlight lang="text">PRINT "Circle sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
Line 2,110 ⟶ 2,676:
PRINT
RETURN</
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="vlang">fn circle_sort(mut a []int, l int, h int, s int) int {
mut hi := h
mut lo := l
mut swaps := s
if lo == hi {
return swaps
}
high, low := hi, lo
mid := (hi - lo) / 2
for lo < hi {
if a[lo] > a[hi] {
a[lo], a[hi] = a[hi], a[lo]
swaps++
}
lo++
hi--
}
if lo == hi {
if a[lo] > a[hi+1] {
a[lo], a[hi+1] = a[hi+1], a[lo]
swaps++
}
}
swaps = circle_sort(mut a, low, low+mid, swaps)
swaps = circle_sort(mut a, low+mid+1, high, swaps)
return swaps
}
fn main() {
aa := [
[6, 7, 8, 9, 2, 5, 3, 4, 1],
[2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1],
]
for a1 in aa {
mut a:=a1.clone()
println("Original: $a")
for circle_sort(mut a, 0, a.len-1, 0) != 0 {
// empty block
}
println("Sorted : $a\n")
}
}</syntaxhighlight>
{{out}}
<pre>
Original: [6, 7, 8, 9, 2, 5, 3, 4, 1]
Sorted : [1, 2, 3, 4, 5, 6, 7, 8, 9]
Original: [2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]
Sorted : [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14]
</pre>
=={{header|Wren}}==
<
circleSort = Fn.new { |a, lo, hi, swaps|
if (lo == hi) return swaps
Line 2,142 ⟶ 2,762:
}
var
for (a in
System.print("Before: %(a)")
while (circleSort.call(a, 0, a.count-1, 0) != 0) {}
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 2,157 ⟶ 2,777:
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>
=={{header|zkl}}==
<
csort:=fcn(list,lo,hi,swaps){
if(lo==hi) return(swaps);
Line 2,183 ⟶ 2,842:
while(csort(list,0,list.len()-1,0)){ list.println() }
list
}</
<
circleSort(L(5,-1,101,-4,0,1,8,6,2,3));</
{{out}}
<pre>
Line 2,203 ⟶ 2,862:
This version of Circle sort was based on the optimized version on [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge]. It will also show a few asterisks while running, because it will take some time to finish (about two minutes).
<
10 DIM a(100): DIM s(32): RANDOMIZE : LET p=1: GO SUB 3000: GO SUB 2000: GO SUB 4000
20 STOP
Line 2,215 ⟶ 2,874:
3000 FOR x=1 TO 100: LET a(x)=RND: NEXT x: RETURN
4000 FOR x=1 TO 100: PRINT x,a(x): NEXT x: RETURN
</syntaxhighlight>
|