Dutch national flag problem: Difference between revisions
Content added Content deleted
(Added Algol 68) |
m (→{{header|Phix}}: bugfix (j<n ==> j<=n), added syntax colouring, made p2js compatible) |
||
Line 2,719: | Line 2,719: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Minimizes the number of read and swap operations, straight translation of the wikipedia pseudocode: |
Minimizes the number of read and swap operations, straight translation of the wikipedia pseudocode: |
||
<!--<lang Phix>(phixonline)--> |
|||
<lang Phix>function three_way_partition(sequence s, integer mid) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer i=1, j=1, n = length(s) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">three_way_partition</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">mid</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
while j < n do |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
if s[j] < mid then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">mid</span> <span style="color: #008080;">then</span> |
|||
{s[i],s[j]} = {s[j],s[i]} |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]}</span> |
|||
i += 1 |
|||
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
j += 1 |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
elsif s[j] > mid then |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">mid</span> <span style="color: #008080;">then</span> |
|||
{s[j],s[n]} = {s[n],s[j]} |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]}</span> |
|||
n -= 1 |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
else |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
return s |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
constant colours = {"red","white","blue"} |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">colours</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"red"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"white"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"blue"</span><span style="color: #0000FF;">}</span> |
|||
enum /*red,*/ white = 2, blue, maxc = blue |
|||
<span style="color: #008080;">enum</span> <span style="color: #000080;font-style:italic;">/*red,*/</span> <span style="color: #000000;">white</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">blue</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">blue</span> |
|||
procedure show(string msg, sequence s) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">msg</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to length(s) do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">))</span> |
|||
s[i] = colours[s[i]] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">colours</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span> |
|||
printf(1,"%s: %s\n",{msg,join(s)}) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end procedure |
|||
<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;">"%s: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">msg</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
sequence unsorted, sorted |
|||
while 1 do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">unsorted</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sorted</span> |
|||
unsorted = sq_rand(repeat(maxc,12)) |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
⚫ | |||
<span style="color: #000000;">unsorted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">))</span> |
|||
sorted = three_way_partition(unsorted, white) |
|||
⚫ | |||
if unsorted!=sorted then exit end if |
|||
<span style="color: #000000;">sorted</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">three_way_partition</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">unsorted</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">white</span><span style="color: #0000FF;">)</span> |
|||
?"oops" |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">unsorted</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">sorted</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"oops"</span> |
|||
show("Unsorted",unsorted) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
show("Sorted",sorted)</lang> |
|||
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Unsorted"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">unsorted</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Sorted"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sorted</span><span style="color: #0000FF;">)</span> |
|||
<!--</lang>--> |
|||
<small>I thought of unsorted=shuffle(unsorted) in the "oops" loop, but of course that'd repeat forever should they all be the same colour.</small> |
<small>I thought of unsorted=shuffle(unsorted) in the "oops" loop, but of course that'd repeat forever should they all be the same colour.</small> |
||
{{out}} |
{{out}} |