Sorting Algorithms/Circle Sort: Difference between revisions
Content added Content deleted
Alpha bravo (talk | contribs) (Added AutoHotkey) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 1,754:
=={{header|Phix}}==
<!--<lang Phix>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">array</span>
<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>
<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>
<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>
<span style="color: #000000;">low</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #000000;">swaps</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">swaps</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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 <== (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>
<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 <== (sorted)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">array</span><span style="color: #0000FF;">})</span>
<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}
▲ --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>
"loop"
"loop"
</pre>
|