Sorting Algorithms/Circle Sort: Difference between revisions

From Rosetta Code
Content added Content deleted
(jq)
m (→‎{{header|jq}}: as defined in this section)
Line 251: Line 251:
With kudos to [[#Perl 6]].
With kudos to [[#Perl 6]].


"circlesort" as defined can be used to sort any JSON array. In case your jq does not have "until" as a builtin, here is its definition:
"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:
<lang jq>def until(cond; next):
<lang jq>def until(cond; next):
def _until: if cond then . else (next|_until) end;
def _until: if cond then . else (next|_until) end;
Line 295: Line 295:
<lang sh>$ jq -n -c -f -M circleSort.jq
<lang sh>$ jq -n -c -f -M circleSort.jq
["The","brown","dog","fox","jumps","lazy","over","quick","the"]</lang>
["The","brown","dog","fox","jumps","lazy","over","quick","the"]</lang>

=={{header|PARI/GP}}==
=={{header|PARI/GP}}==
This follows the pseudocode pretty closely.
This follows the pseudocode pretty closely.

Revision as of 20:31, 7 May 2015

Sorting Algorithms/Circle Sort is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log2n) sorts
Shell Sort

O(n2) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

Sort an array of integers (of any convenient size) into ascending order using Circlesort. In short, compare the first element to the last element, then the second element to the second last element, etc. Then split the array in two and recurse until there is only one single element in the array, like this: 

Before:
6 7 8 9 2 5 3 4 1
After:
1 4 3 5 2 9 8 7 6

Repeat this procedure until quiescence (i.e. until there are no swaps).

Show both the initial, unsorted list and the final sorted list. (Intermediate steps during sorting are optional.)

Optimizations (like doing 0.5 log2(n) iterations and then continue with an Insertion sort) are optional.

Pseudo code: 

 function circlesort (index lo, index hi, swaps)
 {
   if lo == hi return (swaps)
   high := hi
   low := lo
   mid := int((hi-lo)/2)
   while lo < hi {
     if  (value at lo) > (value at hi) {
        swap.values (lo,hi)
        swaps++
     }
     lo++
     hi--
   }
   if lo == hi
     if (value at lo) > (value at hi+1) {
         swap.values (lo,hi+1)
         swaps++
     }
   swaps := circlesort(low,low+mid,swaps)
   swaps := circlesort(low+mid+1,high,swaps)
   return(swaps)
 }
 while circlesort (0, sizeof(array)-1, 0)

For more information on Circle sorting, see Sourceforge.


C

<lang c>#include <stdio.h>

int circle_sort_inner(int *start, int *end) { int *p, *q, t, swapped;

if (start == end) return 0;

// funny "||" on next line is for the center element of odd-lengthed array for (swapped = 0, p = start, q = end; p *q) t = *p, *p = *q, *q = t, swapped = 1;

// q == p-1 at this point return swapped | circle_sort_inner(start, q) | circle_sort_inner(p, end); }

//helper function to show arrays before each call void circle_sort(int *x, int n) { do { int i; for (i = 0; i < n; i++) printf("%d ", x[i]); putchar('\n'); } while (circle_sort_inner(x, x + (n - 1))); }

int main(void) { int x[] = {5, -1, 101, -4, 0, 1, 8, 6, 2, 3}; circle_sort(x, sizeof(x) / sizeof(*x));

return 0; }</lang>

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

D

<lang d>import std.stdio, std.algorithm, std.array, std.traits;

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

   uint inner(size_t lo, size_t hi, uint swaps) {
       if (lo == hi)
           return swaps;
       auto high = hi;
       auto low = lo;
       immutable mid = (hi - lo) / 2;

       while (lo < hi) {
           if (items[lo] > items[hi]) {
               swap(items[lo], items[hi]);
               swaps++;
           }
           lo++;
           hi--;
       }

       if (lo == hi && items[lo] > items[hi + 1]) {
           swap(items[lo], items[hi + 1]);
           swaps++;
       }
       swaps = inner(low, low + mid, swaps);
       swaps = inner(low + mid + 1, high, swaps);
       return swaps;
   }

   if (!items.empty)
       while (inner(0, items.length - 1, 0)) {}

}

void main() { 

   import std.random, std.conv;

   auto a = [5, -1, 101, -4, 0, 1, 8, 6, 2, 3];
   a.circlesort;
   a.writeln;
   assert(a.isSorted);

   // Fuzzy test.
   int[30] items;
   foreach (immutable _; 0 .. 100_000) {
       auto data = items[0 .. uniform(0, items.length)];
       foreach (ref x; data)
           x = uniform(-items.length.signed * 3, items.length.signed * 3);
       data.circlesort;
       assert(data.isSorted);
   }

}</lang>

Output:
[-4, -1, 0, 1, 2, 3, 5, 6, 8, 101]

CoffeeScript

<lang>circlesort = (arr, lo, hi, swaps) -> 

 if lo == hi
    return (swaps)

 high = hi
 low  = lo
 mid = Math.floor((hi-lo)/2)

 while lo < hi
   if arr[lo] > arr[hi]
      t = arr[lo]
      arr[lo] = arr[hi]
      arr[hi] = t
      swaps++
   lo++
   hi--

 if lo == hi
    if arr[lo] > arr[hi+1]
       t = arr[lo]
       arr[lo] = arr[hi+1]
       arr[hi+1] = t
       swaps++

 swaps = circlesort(arr,low,low+mid,swaps)
 swaps = circlesort(arr,low+mid+1,high,swaps)

 return(swaps)

VA = [2,14,4,6,8,1,3,5,7,9,10,11,0,13,12,-1]

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

  console.log VA</lang>

Output: 

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

Forth

<lang>defer precedes ( addr addr -- flag ) variable (swaps) \ keeps track of swaps

[UNDEFINED] cell- [IF] : cell- 1 cells - ; [THEN]

(compare) ( a1 a2 -- a1 a2)
 over @ over @ precedes               \ if swapped, increment (swaps)
 if over over over @ over @ swap rot ! swap ! 1 (swaps) +! then
(circlesort) ( a n --)
 dup 1 > if
   over over                          ( array len)
   1- cells over + swap               ( 'end 'begin)
   begin
     over over >                      \ if we didn't pass the middle
   while                              \ check and swap opposite elements
     (compare) swap cell- swap cell+
   repeat                             \ check if there's a middle element
   over over = if cell- (compare) then drop drop
   over over 2/ recurse               \ sort first partition
   dup 2/ cells rot + swap dup 2/ - recurse exit
 then                                 \ sort second partition
 drop drop                            \ nothing to sort
sort begin 0 (swaps) ! over over (circlesort) (swaps) @ 0= until drop drop ;
noname < ; is precedes

10 constant /sample create sample 5 , -1 , 101 , -4 , 0 , 1 , 8 , 6 , 2 , 3 ,

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

sample /sample sort .sample</lang>

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.

<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 even_length_iteration =: ((,: |.) (([: <./ ({.~ _&,)) ,&$: ([: >./ (}.~ 0&,))) (1r2 * #))^:(1 < #) pre =: , (([: (-~ >.&.(2&^.)) #) # >./) NB. extend data to next power of 2 length post =: ({.~ #)~ NB. remove the extra data </lang> Examples: <lang J> 

  show =: [ smoutput

  8 ([: circle_sort&.>@show ;&(?~)) 13  NB. sort lists length 8 and 13

┌───────────────┬────────────────────────────┐ │0 6 7 3 4 5 2 1│3 10 1 4 7 8 5 6 2 0 9 11 12│ └───────────────┴────────────────────────────┘ ┌───────────────┬────────────────────────────┐ │0 1 2 3 4 5 6 7│0 1 2 3 4 5 6 7 8 9 10 11 12│ └───────────────┴────────────────────────────┘ 

  8 ([: circle_sort&.>@show ;&(1 }. 2 # ?~)) 13  NB. data has repetition

┌─────────────────────────────┬──────────────────────────────────────────────────────┐ │2 3 3 5 5 1 1 7 7 6 6 4 4 0 0│12 11 11 4 4 3 3 9 9 7 7 10 10 6 6 2 2 1 1 5 5 8 8 0 0│ └─────────────────────────────┴──────────────────────────────────────────────────────┘ ┌─────────────────────────────┬──────────────────────────────────────────────────────┐ │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│ └─────────────────────────────┴──────────────────────────────────────────────────────┘ </lang>

jq

Works with: jq version 1.4

With kudos to #Perl 6.

"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: <lang jq>def until(cond; next): 

    def _until: if cond then . else (next|_until) end;
    _until;</lang>

<lang jq>def circlesort: 

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

 # state: [lo, hi, swaps, array]
 def cs:

   # increment lo, decrement hi, and if they are equal, increment hi again
   # i.e. ++hi if --hi == $lo
   def next: # [lo, hi]
     .[0] += 1 | .[1] -= 1 | (if .[0] == .[1] then .[1] += 1 else . end) ;

   .[0] as $start | .[1] as $stop
   | if $start < $stop then
       until(.[0] >= .[1];

.[0] as $lo | .[1] as $hi | .[3] as $array 

             | if $array[$lo] > $array[$hi] then

.[3] = ($array | swap($lo; $hi)) 

                   | .[2] += 1         # swaps++
               else .
               end

| next) 

       | .[0] as $lo | .[1] as $hi
       | [$start, $hi, .[2], .[3]] | cs

| [$lo, $stop, .[2], .[3]] | cs 

     else .
     end ;

  [0, length-1, 0, .] | cs
  | .[2] as $swaps
  | .[3]
  | if $swaps == 0 then .
     else circlesort
     end ;</lang>

Example: <lang jq>"The quick brown fox jumps over the lazy dog" | split(" ") | circlesort</lang>

Output:

<lang sh>$ jq -n -c -f -M circleSort.jq ["The","brown","dog","fox","jumps","lazy","over","quick","the"]</lang>

PARI/GP

This follows the pseudocode pretty closely. <lang parigp>circlesort(v)= { local(v=v); \\ share with cs while (cs(1, #v),); v; } cs(lo, hi)= { if (lo == hi, return (0)); my(high=hi,low=lo,mid=(hi-lo)\2,swaps); while (lo < hi, if (v[lo] > v[hi], [v[lo],v[hi]]=[v[hi],v[lo]]; swaps++ ); lo++; hi-- ); if (lo==hi && v[lo] > v[hi+1], [v[lo],v[hi+1]]=[v[hi+1],v[lo]]; swaps++ ); swaps + cs(low,low+mid) + cs(low+mid+1,high); } print(example=[6,7,8,9,2,5,3,4,1]); print(circlesort(example));</lang>

Output:
[6, 7, 8, 9, 2, 5, 3, 4, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Perl 6

The given algorithm can be simplified in several ways. There's no need to compute the midpoint, since the hi/lo will end up there. The extra swap conditional can be eliminated by incrementing hi at the correct moment inside the loop. There's no need to pass accumulated swaps down the call stack.

This does generic comparisons, so it works on any ordered type, including numbers or strings. <lang perl6>sub circlesort (@x is rw, $beg, $end) { 

   my $swaps = 0;
   if $beg < $end {
       my ($lo, $hi) = $beg, $end;
       repeat {
           if @x[$lo] after @x[$hi] {
               @x[$lo,$hi] .= reverse;
               ++$swaps;
           }
           ++$hi if --$hi == ++$lo
       } while $lo < $hi;
       $swaps += circlesort(@x, $beg, $hi);
       $swaps += circlesort(@x, $lo, $end);
   }
   $swaps;

}

say my @x = (-100..100).roll(20); say @x while circlesort(@x, 0, @x.end);

say @x = <The quick brown fox jumps over the lazy dog.>; say @x while circlesort(@x, 0, @x.end);</lang>

Output:
16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88
-99 -78 16 20 36 -81 -29 46 25 59 -64 -7 39 26 88 -1 35 85 76 100
-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
The quick brown fox jumps over the lazy dog.
The brown fox jumps lazy dog. quick over the
The brown dog. fox jumps lazy over quick the

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. <lang python>

  1. python3
  2. tests: expect no output.
  3. doctest with python3 -m doctest thisfile.py
  4. additional tests: python3 thisfile.py

def circle_sort_backend(A:list, L:int, R:int)->'sort A in place, returning the number of swaps': 

   
       >>> L = [3, 2, 8, 28, 2,]
       >>> circle_sort(L)
       3
       >>> print(L)
       [2, 2, 3, 8, 28]
       >>> L = [3, 2, 8, 28,]
       >>> circle_sort(L)
       1
       >>> print(L)
       [2, 3, 8, 28]
   
   n = R-L
   if n < 2:
       return 0
   swaps = 0
   m = n//2
   for i in range(m):
       if A[R-(i+1)] < A[L+i]:
           (A[R-(i+1)], A[L+i],) = (A[L+i], A[R-(i+1)],)
           swaps += 1
   if (n & 1) and (A[L+m] < A[L+m-1]):
       (A[L+m-1], A[L+m],) = (A[L+m], A[L+m-1],)
       swaps += 1
   return swaps + circle_sort_backend(A, L, L+m) + circle_sort_backend(A, L+m, R)

def circle_sort(L:list)->'sort A in place, returning the number of swaps': 

   swaps = 0
   s = 1
   while s:
       s = circle_sort_backend(L, 0, len(L))
       swaps += s
   return swaps
  1. more tests!

if __name__ == '__main__': 

   from random import shuffle
   for i in range(309):
       L = list(range(i))
       M = L[:]
       shuffle(L)
       N = L[:]
       circle_sort(L)
       if L != M:
           print(len(L))
           print(N)
           print(L)

</lang>

Racket

By default this sorts with the numeric < but any other (diadic) function can be used to compare... e.g. string<?.

<lang racket>#lang racket (define (circle-sort v0 [<? <]) 

 (define v (vector-copy v0))

 (define (swap-if l r)
   (define v.l (vector-ref v l))
   (define v.r (vector-ref v r))
   (and (<? v.r v.l)
        (begin (vector-set! v l v.r) (vector-set! v r v.l) #t)))

 (define (inr-cs! L R)
   (cond
     [(>= L (- R 1)) #f] ; covers 0 or 1 vectors
     [else
      (define M (quotient (+ L R) 2))
      (define I-moved?
        (for/or ([l (in-range L M)] [r (in-range (- R 1) L -1)])
          (swap-if l r)))
      (define M-moved? (and (odd? (- L R)) (> M 0) (swap-if (- M 1) M)))
      (define L-moved? (inr-cs! L M))
      (define R-moved? (inr-cs! M R))
      (or I-moved? L-moved? R-moved? M-moved?)]))

 (let loop () (when (inr-cs! 0 (vector-length v)) (loop)))
 v)

(define (sort-random-vector) 

 (define v (build-vector (+ 2 (random 10)) (λ (i) (random 100))))
 (define v< (circle-sort v <))
 (define sorted? (apply <= (vector->list v<)))
 (printf "   ~.a\n-> ~.a [~a]\n\n" v v< sorted?))

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

(circle-sort '#("table" "chair" "cat" "sponge") string<?)</lang>

Output:
   #(36 94 63 51 33)
-> #(33 36 51 63 94) [#t]

   #(73 74 20 20 79)
-> #(20 20 73 74 79) [#t]

   #(83 42)
-> #(42 83) [#t]

   #(53 95 43 33 66 47 1 61 28 96)
-> #(1 28 33 43 47 53 61 66 95 96) [#t]

   #(71 85)
-> #(71 85) [#t]

   #(36 85 50 19 88 17 2 53 21)
-> #(2 17 19 21 36 50 53 85 88) [#t]

   #(5 97 62 21 99 73 17 16 37 28)
-> #(5 16 17 21 28 37 62 73 97 99) [#t]

   #(12 60 89 90 2 95 9 28)
-> #(2 9 12 28 60 89 90 95) [#t]

   #(50 32 30 47 63 74)
-> #(30 32 47 50 63 74) [#t]

   #(63 41)
-> #(41 63) [#t]

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

REXX

This REXX version will work with any numbers that REXX supports, including negative and floating point numbers. <lang rexx>/*REXX program uses a circle sort to sort an array (or list) of numbers.*/ parse arg x; if x= then x=6 7 8 9 2 5 3 4 1 /*use the defaults ? */ call make@ 'before sort:' /*display the list, make an array*/ call circleSort # /*invoke circle sort subroutine. */ call makeY ' after sort:' /*make a list, display the list. */ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────CIRCLESORT subroutine───────────────*/ circleSort: do while .circleSrt(1,arg(1),0)\==0; end; return /*done.*/ .circleSrt: procedure expose @.; parse arg lo,hi,swaps /*get the args. */ if lo==hi then return swaps /*are we done ? */ high=hi; low=lo; mid=(hi-lo) % 2 /*assign indices*/ 

                                                       /* [↓] a section*/
                  do while lo<hi                       /*sort section. */
                  if @.lo>@.hi  then call .swap lo,hi  /*out of order ?*/
                  lo=lo+1;  hi=hi-1                    /*add; subtract.*/
                  end   /*while lo<hi*/                /*just 1 section*/

hiP=hi+1 /*point to HI+1.*/ if lo==hi then if @.lo>@.hiP then call .swap lo,hiP /*out of order? */ swaps=.circleSrt(low, low+mid, swaps) /*sort lower. */ swaps=.circleSrt(low+mid+1, high, swaps) /* " higher, */ return swaps /*section done. */ /*──────────────────────────────────one─liner subroutines───────────────*/ .swap: arg a,b; parse value @.a @.b with @.b @.a; swaps=swaps+1; return make@: #=words(x); do i=1 for #; @.i=word(x,i); end; say arg(1) x; return makeY: y=@.1; do j=2 to #; y=y @.j; end; say arg(1) y; return</lang> output when using the default input: 

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

output when using the input of:   2 3 3 5 5 1 1 7 7 6 6 4 4 0 0 

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

output when using the input of:   2 3 44 44 5.77 +1 -12345 -3 -3.9 1e7 9 

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

Ruby

<lang ruby>class Array 

 def circle_sort!
   while _circle_sort!(0, size-1) > 0
   end
   self
 end
 
 private
 def _circle_sort!(lo, hi, swaps=0)
   return swaps if lo == hi
   low, high = lo, hi
   mid = (lo + hi) / 2
   while lo < hi
     if self[lo] > self[hi]
       self[lo], self[hi] = self[hi], self[lo]
       swaps += 1
     end
     lo += 1
     hi -= 1
   end
   if lo == hi && self[lo] > self[hi+1]
     self[lo], self[hi+1] = self[hi+1], self[lo]
     swaps += 1
   end
   swaps + _circle_sort!(low, mid) + _circle_sort!(mid+1, high)
 end

end

ary = [6, 7, 8, 9, 2, 5, 3, 4, 1] puts "before sort: #{ary}" puts " after sort: #{ary.circle_sort!}"</lang>

Output:
before sort: [6, 7, 8, 9, 2, 5, 3, 4, 1]
 after sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]

uBasic/4tH

<lang>PRINT "Circle sort:" 

 n = FUNC (_InitArray)
 PROC _ShowArray (n)
 PROC _Circlesort (n)
 PROC _ShowArray (n)

PRINT

END

_Circle PARAM (3) 

 IF a@ = b@ THEN RETURN (c@)

 LOCAL (3)
 d@ = a@
 e@ = b@
 f@ = (b@-a@)/2

 DO WHILE a@ < b@
   IF @(a@) > @(b@) THEN
      PUSH @(a@)
      @(a@) = @(b@)
      @(b@) = POP()
      c@ = c@ + 1
   ENDIF
   a@ = a@ + 1
   b@ = b@ - 1
 LOOP

 IF a@ = b@ THEN
    IF @(a@) > @(b@+1) THEN
       PUSH @(a@)
       @(a@) = @(b@+1)
       @(b@+1) = POP()
       c@ = c@ + 1
    ENDIF
 ENDIF

 c@ = FUNC (_Circle (d@, d@+f@, c@))
 c@ = FUNC (_Circle (d@+f@+1, e@, c@))

RETURN (c@)


_Circlesort PARAM(1) ' Circle sort 

 DO WHILE FUNC (_Circle (0, a@-1, 0))
 LOOP

RETURN


_InitArray ' Init example array 

 PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

 FOR i = 0 TO 9
   @(i) = POP()
 NEXT

RETURN (i)


_ShowArray PARAM (1) ' Show array subroutine 

 FOR i = 0 TO a@-1
   PRINT @(i),
 NEXT

 PRINT

RETURN</lang>

zkl

<lang zkl>fcn circleSort(list){ 

  csort:=fcn(list,lo,hi,swaps){
     if(lo==hi) return(swaps);
     high,low,mid:=hi,lo,(hi-lo)/2;
     while(lo<hi){

if(list[lo]>list[hi]){ list.swap(lo,hi); swaps+=1; } lo+=1; hi-=1; 

     }
     if(lo==hi)

if (list[lo]>list[hi+1]){ list.swap(lo,hi+1); swaps+=1; } 

     swaps=self.fcn(list,low,low + mid,swaps);
     swaps=self.fcn(list,low + mid + 1,high,swaps);
     return(swaps);
  };
  list.println();
  while(csort(list,0,list.len()-1,0)){ list.println() }
  list

}</lang> <lang zkl>circleSort(L(6,7,8,9,2,5,3,4,1)); circleSort(L(5,-1,101,-4,0,1,8,6,2,3));</lang>

Output:
L(6,7,8,9,2,5,3,4,1)
L(1,3,4,2,5,6,7,8,9)
L(1,2,3,4,5,6,7,8,9)
L(5,-1,101,-4,0,1,8,6,2,3)
L(-4,-1,0,3,6,1,2,8,5,101)
L(-4,-1,0,1,2,3,5,6,8,101)
Retrieved from "https://rosettacode.org/wiki/Sorting_Algorithms/Circle_Sort?oldid=253774"