Sorting Algorithms/Circle Sort: Difference between revisions
Content added Content deleted
(Added solution for Action!) |
|||
Line 320: | Line 320: | ||
Table sorted. |
Table sorted. |
||
</pre> |
|||
=={{header|Action!}}== |
|||
Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed. |
|||
<lang Action!>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</lang> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Circle_Sort.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Array before sort: |
|||
[1 4 -1 0 3 7 4 8 20 -6] |
|||
Array after sort: |
|||
[-6 -1 0 1 3 4 4 7 8 20] |
|||
Array before sort: |
|||
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10] |
|||
Array after sort: |
|||
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10] |
|||
Array before sort: |
|||
[101 102 103 104 105 106 107 108] |
|||
Array after sort: |
|||
[101 102 103 104 105 106 107 108] |
|||
Array before sort: |
|||
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1] |
|||
Array after sort: |
|||
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1] |
|||
</pre> |
</pre> |
||