
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)



See also

 For more information on Circle sorting, see Sourceforge.


DEFINE MAX_COUNT="100"
INT ARRAY stack(MAX_COUNT)
INT stackSize
 
PROC PrintArray(INT ARRAY a INT size)
  INT i
 
  Put('[)
  FOR i=0 TO size-1
  DO
    IF i>0 THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN
 
PROC InitStack()
  stackSize=0
RETURN
 
BYTE FUNC IsEmpty()
  IF stackSize=0 THEN
    RETURN (1)
  FI
RETURN (0)
 
PROC Push(INT low,high)
  stack(stackSize)=low  stackSize==+1
  stack(stackSize)=high stackSize==+1
RETURN
 
PROC Pop(INT POINTER low,high)
  stackSize==-1 high^=stack(stackSize)
  stackSize==-1 low^=stack(stackSize)
RETURN
 
INT FUNC Partition(INT ARRAY a INT low,high)
  INT part,v,i,tmp
 
  v=a(high)
  part=low-1
 
  FOR i=low TO high-1
  DO
    IF a(i)<=v THEN
      part==+1
      tmp=a(part) a(part)=a(i) a(i)=tmp
    FI
  OD
 
  part==+1
  tmp=a(part) a(part)=a(high) a(high)=tmp
RETURN (part)
 
PROC CircleSort(INT ARRAY a INT size)
  INT swaps,low,high,lo,hi,tmp,mid
 
  InitStack()
  DO
    swaps=0
    Push(0,size-1)
    WHILE IsEmpty()=0
    DO
      Pop(@low,@high)
      IF low<high THEN
        lo=low hi=high
        WHILE lo<hi
        DO
          IF a(hi)<a(lo) THEN
            tmp=a(lo) a(lo)=a(hi) a(hi)=tmp
            swaps==+1
          FI
          lo==+1 hi==-1
        OD
        IF lo=hi AND a(lo+1)<a(lo) THEN
          tmp=a(lo) a(lo)=a(lo+1) a(lo+1)=tmp
          swaps==+1
        FI
        mid=(lo+hi)/2
        Push(low,mid)
        Push(mid+1,high)
      FI
    OD
  UNTIL swaps=0
  OD
RETURN
 
PROC Test(INT ARRAY a INT size)
  PrintE("Array before sort:")
  PrintArray(a,size)
  CircleSort(a,size)
  PrintE("Array after sort:")
  PrintArray(a,size)
  PutE()
RETURN
 
PROC Main()
  INT ARRAY
    a(10)=[1 4 65535 0 3 7 4 8 20 65530],
    b(21)=[10 9 8 7 6 5 4 3 2 1 0
      65535 65534 65533 65532 65531
      65530 65529 65528 65527 65526],
    c(8)=[101 102 103 104 105 106 107 108],
    d(12)=[1 65535 1 65535 1 65535 1
      65535 1 65535 1 65535]
 
  Test(a,10)
  Test(b,21)
  Test(c,8)
  Test(d,12)
RETURN