Sorting Algorithms/Circle Sort: Difference between revisions

* For more information on Circle sorting, see [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge].

<br><br>

 

=={{header|C}}==

 

int circle_sort_inner(int *start, int *end)

 

return 0;

{{out}}

<pre>

-4 -1 0 3 6 1 2 8 5 101

-4 -1 0 1 2 3 5 6 8 101

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

 

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

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>

 

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

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

print(N)

print(L)

 

=={{header|Racket}}==

(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

 

=={{header|REXX}}==

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

call make_array 'before sort:' /*display the list and make an array. */

call make_list ' after sort:' /*make a list and display it to console*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

.circleSrt: procedure expose @.; parse arg LO,HI,swaps /*obtain LO & HI arguments.*/

if LO==HI then return swaps /*1 element? Done with sort.*/

/* [↓] sort a section of #'s*/

do while LO<HI /*sort within a section. */

if @.LO>@.HI then call .swap LO,HI /*are numbers out of order ? */

end /*while*/ /*just process one section. */

if LO==HI & @.LO>@._ then call .swap LO, _ /*numbers still out of order?*/

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

["Alice", "Jane", "Alice", "Joe", "John", "Kate", "Zerg"]

["Alice", "Alice", "Jane", "Joe", "John", "Kate", "Zerg"]

</pre>

 

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