Dutch national flag problem: Difference between revisions

Dutch national flag problem (view source)

Revision as of 16:03, 13 January 2022

8,891 bytes added , 2 years ago

m

→‎{{header|Phix}}: bugfix (j<n ==> j<=n), added syntax colouring, made p2js compatible

Petelomax

7,806

edits

Revision as of 18:24, 23 November 2021 (view source) Tigerofdarkness (talk \| contribs) (Added Algol 68) ← Older edit		Revision as of 16:03, 13 January 2022 (view source) Petelomax (talk \| contribs) m (→‎{{header\|Phix}}: bugfix (j<n ==> j<=n), added syntax colouring, made p2js compatible) Newer edit →
Line 2,719: =={{header\|Phix}}== 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 ~~j +~~style="color: 1#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> -- sorted = sort(unsorted) -- (works just as well)▼ <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)~~ ▲ <span style="color: #000080;font-style:italic;">-- sorted = sort(deep_copy(unsorted)) -- (works just as well)</span> ~~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> {{out}}