Anonymous user
Sorting Algorithms/Circle Sort: Difference between revisions
Added solution for Action!
(Added solution for Action!) |
|||
Line 320:
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>
| |||