Sorting Algorithms/Circle Sort: Difference between revisions
(Added Circlesort algorithm as Draft task) |
(Forced TOC) |
||
Line 36: | Line 36: | ||
For more information on Circle sorting, see [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge]. |
For more information on Circle sorting, see [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge]. |
||
__FORCETOC__ |
|||
=={{header|C}}== |
=={{header|C}}== |
Revision as of 18:59, 4 January 2015
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>#include <stdio.h>
int CircleSort (int* a, int n, int swaps) {
int* sta = a; /* calculate start address */ int* end = a + (n - 1); /* calculate end address */ int t; /* temporary value for swapping */
if (n > 1) /* if array size is larger than 1 */ { /* then perform the sort */ while (sta < end) /* sort as long as begin address */ { /* is smaller than end address */ if (*sta > *end) /* if first element is larger than end */ { /* then swap 'em */ t = *sta; *sta = *end; *end = t; swaps++; } /* and increment no. swaps */ sta++; end--; /* now adjust addresses for next */ } /* iteration */
if (sta == end) /* if addresses are the same, then */ { /* array size was uneven */ sta--; /* so also sort pivot element */ /* decrement the starting address */ if (*sta > *end) /* and swap the elements, if required */ { t = *sta; *sta = *end; *end = t; swaps++; } } /* now sort both halves of the array */ swaps = CircleSort (a, n/2, swaps); return (CircleSort (a + n/2, n - n/2, swaps)); } /* note "n - n/2" <> "n/2" */
return (swaps); /* do nothing, just pass through */
}
int main() {
int x[] = { 5, -1, 101, -4, 0, 1, 8, 6, 2, 3 }; size_t i, len = sizeof(x)/sizeof(x[0]);
while (CircleSort (x, len, 0)); for (i = 0; i < len; i++) printf("%d\n", x[i]); return 0;
}</lang>
Output:
-4 -1 0 1 2 3 5 6 8 101
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>
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>