Rosetta Code

Sorting Algorithms/Circle Sort: Difference between revisions

Page Discussion

Sorting Algorithms/Circle Sort (view source)

Revision as of 17:23, 15 May 2021

8,325 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
(Added AutoHotkey)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 1,754:
 
=={{header|Phix}}==
<!--<lang Phix>sequence array(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 
function circle_sort_inner(integer lo, hi, swaps, level=1)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">array</span>
if lo!=hi then
integer high := hi,
<span style="color: #008080;">function</span> <span style="color: #000000;">circle_sort_inner</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">swaps</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
low := lo,
<span style="color: #008080;">if</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">hi</span> <span style="color: #008080;">then</span>
mid := floor((high-low)/2)
<span style="color: #004080;">integer</span> <span style="color: #000000;">high</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span>
while lo <= hi do
<span style="color: #000000;">low</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span>
hi += (lo=hi)
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">high</span><span style="color: #0000FF;">-</span><span style="color: #000000;">low</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
if array[lo] > array[hi] then
<span style="color: #008080;">while</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">hi</span> <span style="color: #008080;">do</span>
{array[lo],array[hi]} = {array[hi],array[lo]}
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">=</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">)</span>
?{array,"level",level,{low,high}}
<span style="color: #004080;">object</span> <span style="color: #000000;">alo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">],</span>
swaps += 1
<span style="color: #000000;">ahi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #008080;">if</span> <span style="color: #000000;">alo</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">ahi</span> <span style="color: #008080;">then</span>
lo += 1
<span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ahi</span>
hi -= 1
<span style="color: #000000;">array</span><span style="color: #0000FF;">[</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">alo</span>
end while
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V level %d, low %d, high %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">array</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">,</span><span style="color: #000000;">low</span><span style="color: #0000FF;">,</span><span style="color: #000000;">high</span><span style="color: #0000FF;">})</span>
swaps = circle_sort_inner(low,low+mid,swaps,level+1)
<span style="color: #000000;">swaps</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
swaps = circle_sort_inner(low+mid+1,high,swaps,level+1)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
return swaps
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 
<span style="color: #000000;">swaps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">circle_sort_inner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">low</span><span style="color: #0000FF;">,</span><span style="color: #000000;">low</span><span style="color: #0000FF;">+</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">swaps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
procedure circle_sort()
<span style="color: #000000;">swaps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">circle_sort_inner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">low</span><span style="color: #0000FF;">+</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">high</span><span style="color: #0000FF;">,</span><span style="color: #000000;">swaps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
?{array,"<== (initial)"}
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
while circle_sort_inner(1, length(array), 0) do ?"loop" end while
<span style="color: #008080;">return</span> <span style="color: #000000;">swaps</span>
?{array,"<== (sorted)"}
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end procedure
 
<span style="color: #008080;">procedure</span> <span style="color: #000000;">circle_sort</span><span style="color: #0000FF;">()</span>
array = {5, -1, 101, -4, 0, 1, 8, 6, 2, 3}▼
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V &lt;== (initial)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">array</span><span style="color: #0000FF;">})</span>
--array = {-4,-1,1,0,5,-7,-2,4,-6,-3,2,6,3,7,-5}▼
<span style="color: #008080;">while</span> <span style="color: #000000;">circle_sort_inner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #0000FF;">?</span><span style="color: #008000;">"loop"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
--array = {6, 7, 8, 9, 2, 5, 3, 4, 1}
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V &lt;== (sorted)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">array</span><span style="color: #0000FF;">})</span>
--array = {2,14,4,6,8,1,3,5,7,9,10,11,0,13,12,-1}
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
--array = {"the","quick","brown","fox","jumps","over","the","lazy","dog"}▼
--array = {0.603704, 0.293639, 0.513965, 0.746246, 0.245282, 0.930508, 0.550878, 0.622534, 0.006089, 0.270426}▼
<span style="color: #000000;">array</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">101</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">}</span>
--array = shuffle(array)▼
<span style="color: #000080;font-style:italic;">--array = {-4,-1,1,0,5,-7,-2,4,-6,-3,2,6,3,7,-5}
circle_sort()</lang>
▲ --array = {56, -17, 1018, -49, 02, 15, 83, 64, 2, 31}
▲ --array = {-2,14,4,-16,8,1,03,5,-7,-29,410,-611,-30,213,6,3,712,-51}
▲ --array = {"the","quick","brown","fox","jumps","over","the","lazy","dog"}
▲ --array = {0.603704, 0.293639, 0.513965, 0.746246, 0.245282, 0.930508, 0.550878, 0.622534, 0.006089, 0.270426}
▲ --array = shuffle(deep_copy(array))</span>
<span style="color: #000000;">circle_sort</span><span style="color: #0000FF;">()</span>
<!--</lang>-->
{{out}}
Shows the full inner workings: call depth and range being considered, after each swap made.
<pre>
{{5,-1,101,-4,0,1,8,6,2,3}," <== (initial)"}
{{3,-1,101,-4,0,1,8,6,2,5}," level", 1,{ low 1, high 10}}
{{3,-1,6,-4,0,1,8,101,2,5}," level", 1,{ low 1, high 10}}
{{0,-1,6,-4,3,1,8,101,2,5}," level", 2,{ low 1, high 5}}
{{0,-4,6,-1,3,1,8,101,2,5}," level", 2,{ low 1, high 5}}
{{0,-4,-1,6,3,1,8,101,2,5}," level", 2,{ low 1, high 5}}
{{-1,-4,0,6,3,1,8,101,2,5}," level", 3,{ low 1, high 3}}
{{-4,-1,0,6,3,1,8,101,2,5}," level", 4,{ low 1, high 2}}
{{-4,-1,0,3,6,1,8,101,2,5}," level", 3,{ low 4, high 5}}
{{-4,-1,0,3,6,1,2,101,8,5}," level", 2,{ low 6, high 10}}
{{-4,-1,0,3,6,1,2,8,101,5}," level", 2,{ low 6, high 10}}
{{-4,-1,0,3,6,1,2,8,5,101}," level", 3,{ low 9, high 10}}
"loop"
{{-4,-1,0,2,6,1,3,8,5,101}," level", 1,{ low 1, high 10}}
{{-4,-1,0,2,1,6,3,8,5,101}," level", 1,{ low 1, high 10}}
{{-4,-1,0,1,2,6,3,8,5,101}," level", 3,{ low 4, high 5}}
{{-4,-1,0,1,2,6,3,5,8,101}," level", 2,{ low 6, high 10}}
{{-4,-1,0,1,2,5,3,6,8,101}," level", 3,{ low 6, high 8}}
{{-4,-1,0,1,2,3,5,6,8,101}," level", 4,{ low 6, high 7}}
"loop"
{{-4,-1,0,1,2,3,5,6,8,101}," <== (sorted)"}
</pre>
 
Petelomax
7,805

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/253844"