Sorting Algorithms/Circle Sort: Difference between revisions

 

Sort an array of integers (of any convenient size) into ascending order using Circlesort.

* 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 1 2 3 5 6 8 101

</pre>

 

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

!

!

implicit none

public :: circle_sort

contains

implicit none

integer :: lo, hi, mid

integer :: temp

if (right <= left) return

do while (lo < hi)

if (a(hi) < a(lo)) then

temp = a(lo)

a(lo) = a(hi)

a(hi) = temp

lo = lo + 1

hi = hi - 1

end do

endif

subroutine circle_sort(a, n)

implicit none

integer, intent(in) :: n

end do

end subroutine circle_sort

end module circlesort

program sort

use 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

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

 

=={{header|J}}==

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]

{{works with|jq|1.4}}

 

 

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

 

 

my $swaps = 0;

++$swaps;

}

++$hi if --$hi == ++$lo

}

$swaps;

}

 

{{out}}

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

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

 

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

'#("cat" "chair" "sponge" "table")

</pre>

 

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

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

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

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

<pre>

before sort: 6 7 8 9 2 5 3 4 1

after sort: 1 2 3 4 5 6 7 8 9

</pre>

<pre>

before sort: 2 3 3 5 5 1 1 7 7 6 6 4 4 0 0

after sort: 0 0 1 1 2 3 3 4 4 5 5 6 6 7 7

</pre>

<pre>

before sort: 2 3 44 44 5.77 +1 -12345 -3 -3.9 1e7 0

</pre>

<pre>

before sort: assinine donkey bovine cattle canine dog corvine crow equine horse feline cat hircine goat leporine hare lupine wolf murine rodent piscine fish porcine pig ursine bear vulpine fox

 

=={{header|Ring}}==

# Project : Sorting Algorithms/Circle Sort

 

test = [-4, -1, 1, 0, 5, -7, -2, 4, -6, -3, 2, 6, 3, 7, -5]

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

<pre>

</pre>

 

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