Anonymous user
Sorting Algorithms/Circle Sort: Difference between revisions
m
comprehensive odd list length test inserted.
(added FreeBASIC) |
m (comprehensive odd list length test inserted.) |
||
Line 1:
{{draft task|Sorting Algorithms}}{{Sorting Algorithm}}
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'''
Line 11 ⟶ 6:
'''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:
Line 44 ⟶ 35:
'''while''' circlesort (0, '''sizeof'''(array)-1, 0)
For more information on Circle sorting, see [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge].
__FORCETOC__
=={{header|C}}==
<lang c>#include <stdio.h>
int
{
int
if (
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
{
int i, s;
do {
for (i = 0; i < n; i++)
printf(": %d swaps\n", s = cir_sort_inner(x, n));
} while (
}
int main(void)
{
int x[] = { 5, -1, 101, -4, 0, 1, 8, 6, 2, 3 };
return 0;
Line 86 ⟶ 75:
{{out}}
<pre>
5 -1 101 -4 0 1 8 6 2 3 : 9 swaps
-4 0 -1
-4 -1 0 1 2 3 5 6 8 101 : 0 swaps
</pre>
Line 183 ⟶ 172:
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</pre>
=={{header|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 over over over @ over @ swap rot ! swap !
;
: (circlesort) (
dup 1 > if
over over
1- cells over + swap ( 'end 'begin)
begin
over over > \ if we didn't pass the middle
(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>
=={{header|Python}}==
The doctest passes with odd and even length lists
<lang python>
#python3
Line 555 ⟶ 221:
def circle_sort_backend(A:list, L:int, R:int)->'sort A in place, returning the number of swaps':
'''
>>>
>>>
>>> for T in itertools.permutations(LR7):
... if L != LR7:
... print(L)
...
>>> L = [3, 2, 8, 28,]
>>> circle_sort(L)
Line 602 ⟶ 271:
print(L)
</lang>
=={{header|uBasic/4tH}}==
<lang>PRINT "Circle sort:"
n = FUNC (_InitArray)
Line 812 ⟶ 282:
END
IF a@ = b@ THEN RETURN (c@)
LOCAL (3)
d@ = a@
e@ = b@
f@ = (b@-a@)/2
DO WHILE
IF @(
@(b@) = POP()
c@ = c@ + 1
ENDIF
a@ = a@ + 1
b@ = b@ - 1
LOOP
IF a@ = b@ 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
Line 861 ⟶ 340:
PRINT
RETURN</lang>
|