Sorting Algorithms/Circle Sort
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:
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
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>
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>
- python3
- tests: expect no output.
- doctest with python3 -m doctest thisfile.py
- 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
- 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>
REXX
<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 say 'before sort: ' x /* [↑] get numbers; use default?*/
- =words(x) /*obtain the number of elements. */
do i=1 for #; @.i=word(x,i); end /*assign numbers to the array @.*/
call circleSort 1, # /*invoke circle sort subroutine. */ y=@.1
do j=2 to #; y=y @.j; end /*assign array numbers to a list.*/
say ' after sort: ' y /*display the sorted list of nums*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────CIRCLESORT subroutine───────────────*/ circleSort: procedure expose @.; parse arg lo,hi /*get the arguments.*/
do while .circleSort(1,hi,0) \==0 /*invoke until done.*/
end /*while*/
return /*sort is complete. */ /*──────────────────────────────────.CIRCLESORT subroutine──────────────*/ .circleSort: procedure expose @.; parse arg lo,hi,swaps /*get the args*/ if swaps== then swaps=0 /*assume 0 ? */ if lo==hi then return swaps /*we done ? */ high=hi; low=lo; mid=(hi-lo) % 2 /*assign vars.*/
do while lo<hi /*sort section*/
if @.lo>@.hi then do /*out of ord ?*/
parse value @.lo @.hi with @.hi @.lo /*swap values.*/
swaps=swaps+1 /*bump cntr. */
end
lo=lo+1; hi=hi-1 /*bump or sub.*/
end /*while lo<hi*/
hip=hi+1 /*point: HI+1 */ if lo==hi then if @.lo>@.hip then do /*out of ord? */
parse value @.lo @.hip with @.hip @.lo
swaps=swaps+1 /*bump cntr. */
end
swaps=.circleSort(low,low+mid,swaps) /*sort lower. */ swaps=.circleSort(low+mid+1,high,swaps) /* " higher,*/ return swaps /*section done*/</lang> output when using the default inputs:
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)
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
RETURN</lang>