Sorting Algorithms/Circle Sort: Difference between revisions

{{trans|Python}}

 

V n = r - l

I n < 2

print(l.len)

print(n)

 

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program circleSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

<pre>

Display table before sort.

=={{header|Action!}}==

Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.

INT ARRAY stack(MAX_COUNT)

INT stackSize

Test(c,8)

Test(d,12)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Circle_Sort.png Screenshot from Atari 8-bit computer]

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program circleSort.s */

.include "../affichage.inc"

 

<pre>

Display table before sort.

Table sorted.

</pre>

 

=={{header|AutoHotkey}}==

while circlesort(nums, 1, nums.Count(), 0) ; 1-based

continue

swaps := circlesort(Arr, low+mid+1, high, swaps)

return swaps

{{out}}

<pre>[1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>

 

=={{header|C}}==

 

int circle_sort_inner(int *start, int *end)

 

return 0;

{{out}}

<pre>

 

=={{header|C#}}==

using System.Linq;

 

}

}

{{out}}

<pre>

 

=={{header|C++}}==

 

int circlesort(int* arr, int lo, int hi, int swaps) {

circlesortDriver(arr, sizeof(arr)/sizeof(int));

return 0;

Output:

<pre>6 7 8 9 2 5 3 4 1

 

=={{header|CoffeeScript}}==

if lo == hi

return (swaps)

 

while circlesort(VA,0,VA.length-1,0)

Output:

<pre>console: -1,1,0,3,4,5,8,12,2,9,6,10,7,13,11,14

 

=={{header|D}}==

 

void circlesort(T)(T[] items) if (isMutable!T) {

assert(data.isSorted);

}

{{out}}

<pre>[-4, -1, 0, 1, 2, 3, 5, 6, 8, 101]</pre>

{{libheader| System.SysUtils}}

{{Trans|Go}}

program Sorting_Algorithms;

 

end;

readln;

 

=={{header|Elixir}}==

def circle_sort(data) do

List.to_tuple(data)

data = [6, 7, 8, 9, 2, 5, 3, 4, 1]

IO.puts "before sort: #{inspect data}"

 

{{out}}

=={{header|Forth}}==

This one features the newest version of the algorithm on [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge].

 

defer precedes ( addr addr -- flag )

: .sample sample /sample cells bounds do i ? 1 cells +loop ;

 

=={{header|Fortran}}==

!

module circlesort

end program sort

 

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' for boundry checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsorted -4 -1 1 0 5 -7 -2 4 -6 -3 2 6 3 7 -5

 

=={{header|Go}}==

 

import "fmt"

fmt.Printf("Sorted : %v\n\n", a)

}

 

{{out}}

This code uses the tortoise-and-the-hare technique to split the input list in two and compare the relevant positions.

 

 

circleSort :: Ord a => [a] -> [a]

swap d x (s,y:ys,ls,rs)

| bool (<=) (<) d x y = ( d || s,ys,x:ls,y:rs)

 

{{out}}

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.

 

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

pre =: , (-~ >.&.(2&^.))@# # >./ NB. extend data to next power of 2 length

post =: ({.~ #)~ NB. remove the extra data

Examples:

show =: [ smoutput

 

│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│

└─────────────────────────────┴──────────────────────────────────────────────────────┘

 

=={{header|Java}}==

 

public class CircleSort {

arr[idx2] = tmp;

}

 

<pre>[2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]

 

"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;

 

def swap(i;j): .[i] as $t | .[i] = .[j] | .[j] = $t;

| if $swaps == 0 then .

else circlesort

'''Example:'''

 

{{out}}

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

 

lo == hi && return swaps

high = hi

 

v = rand(10)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun<T: Comparable<T>> circleSort(array: Array<T>, lo: Int, hi: Int, nSwaps: Int): Int {

while (circleSort(array2, 0, array2.size - 1, 0) != 0) ;

println("Sorted : ${array2.asList()}")

 

{{out}}

=={{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

local array = {6, 7, 8, 9, 2, 5, 3, 4, 1}

circleSort(array)

{{out}}

<pre>1 2 3 4 5 6 7 8 9</pre>

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

CircleSort[d_List, l_, h_] :=

Module[{high, low, mid, lo = l, hi = h, data = d},

NestedCircleSort[Echo@{2, 1}]

NestedCircleSort[Echo@{1}]

{{out}}

<pre>>>{6,7,8,9,2,5,3,4,1}

 

=={{header|Nim}}==

var localSwaps: int = swaps

var localHi: int = hi

echo "Original: ", $arr[i]

arr[i].circleSort()

 

{{out}}

=={{header|Objeck}}==

{{trans|Objeck}}

function : Main(args : String[]) ~ Nil {

circleSort([2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]);

}

}

 

Output:

=={{header|PARI/GP}}==

This follows the pseudocode pretty closely.

{

local(v=v); \\ share with cs

}

print(example=[6,7,8,9,2,5,3,4,1]);

{{out}}

<pre>[6, 7, 8, 9, 2, 5, 3, 4, 1]

 

=={{header|Pascal}}==

{

source file name on linux is ./p.p

writeln();

end.

 

=={{header|Perl}}==

Less flexible than the Raku version, as written does only numeric comparisons.

{{trans|Raku}}

our @x; local *x = shift;

my($beg,$end) = @_;

 

my @a = <16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88>;

{{out}}

<pre>-99 -78 16 20 36 -81 -29 46 25 59 -64 -7 39 26 88 -1 35 85 76 100

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

--array = shuffle(deep_copy(array))</span>

<span style="color: #000000;">circle_sort</span><span style="color: #0000FF;">()</span>

{{out}}

Shows the full inner workings: call depth and range being considered, after each swap made.

=={{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.

print(N)

print(L)

 

=={{header|Quackery}}==

 

 

[ drop true ] done

true swap

$ "bababadalgharaghtakamminarronnkonnbronntonnerronntuonnthunntrovarrhounawnskawntoohoohoordenenthurnuk"

dup echo$ cr

 

{{out}}

(diadic) function can be used to compare... e.g. <code>string&lt;?</code>.

 

(define (circle-sort v0 [<? <])

(define v (vector-copy v0))

(for ([_ 10]) (sort-random-vector))

 

 

{{out}}

 

This does generic comparisons, so it works on any ordered type, including numbers or strings.

my $swaps = 0;

if $beg < $end {

 

say @x = <The quick brown fox jumps over the lazy dog.>;

{{out}}

<pre>16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88

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.*/

swaps= .circleSrt(low, low+mid, swaps) /*sort the lower section. */

swaps= .circleSrt(low+mid+1, high, swaps) /* " " higher " */

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

# Project : Sorting Algorithms/Circle Sort

 

see svect

see "]" + nl

Output:

<pre>

 

=={{header|Ruby}}==

def circle_sort!

while _circle_sort!(0, size-1) > 0

ary = [6, 7, 8, 9, 2, 5, 3, 4, 1]

puts "before sort: #{ary}"

 

{{out}}

 

=={{header|Rust}}==

if low == high {

return swaps;

circle_sort(&mut v);

println!("after: {:?}", v);

 

{{out}}

 

=={{header|Scala}}==

 

def sort(arr: Array[Int]): Array[Int] = {

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) {

 

var strs = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane", "Alice"]

{{out}}

<pre>

 

=={{header|Swift}}==

func circSort(low: Int, high: Int, swaps: Int) -> Int {

if low == high {

print("before: \(array2)")

circleSort(&array2)

 

{{out}}

=={{header|uBasic/4tH}}==

This one uses the optimized version featured at [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge].

n = FUNC (_InitArray)

PROC _ShowArray (n)

 

PRINT

 

=={{header|Wren}}==

circleSort = Fn.new { |a, lo, hi, swaps|

if (lo == hi) return swaps

}

 

System.print("Before: %(a)")

while (circleSort.call(a, 0, a.count-1, 0) != 0) {}

System.print("After : %(a)")

System.print()

 

{{out}}

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|zkl}}==

csort:=fcn(list,lo,hi,swaps){

if(lo==hi) return(swaps);

while(csort(list,0,list.len()-1,0)){ list.println() }

list

{{out}}

<pre>

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

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