Sorting Algorithms/Circle Sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 06:07, 7 January 2015

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

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 cir_sort_inner(int *x, int n) { int i, j, t, swaps;

if (n < 2) return 0;

for (swaps = i = 0, j = n - 1; i < j; i++, j--) if (x[i] > x[j]) t=x[i], x[i]=x[j], x[j]=t, swaps++;

return swaps + cir_sort_inner(x, j + 1) + cir_sort_inner(x + i, n - i); }

//helper function to show arrays before each call void cir_sort(int *x, int n) { int i, s;

do { for (i = 0; i < n; i++) printf("%d ", x[i]); printf(": %d swaps\n", s = cir_sort_inner(x, n)); } while (s); }

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

return 0; }</lang>

Output:

5 -1 101 -4 0 1 8 6 2 3 : 9 swaps
-4 0 -1 3 6 1 2 5 8 101 : 6 swaps
-4 -1 0 1 2 3 5 6 8 101 : 0 swaps

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>

python

The doctest passes with odd and even length lists. Please see circle_sort.__doc__ for example use and output. <lang python>

python3
doctest with python3 -m doctest thisfile.py

def circle_sort(A:list, L:int=0, R:int=None)->'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]
   
   swaps = 0
   if R is None:
       R = len(A)
   n = R-L
   if n < 2:
       return swaps
   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
   #print(A)
   return swaps + circle_sort(A, L, L+m) + circle_sort(A, L+m, R)

</lang>

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>