Rosetta Code

Quickselect algorithm: Difference between revisions

Page Discussion

Quickselect algorithm (view source)

Revision as of 20:00, 18 May 2021

6,923 bytes added ,  3 years ago
m
→‎{{header|Phix}}: fixed the performance issue, and syntax coloured it
m (→‎{{header|Phix}}: fixed the performance issue, and syntax coloured it)
Line 2,054:
 
=={{header|Phix}}==
<!--<lang Phix>(phixonline)-->
Note the (three) commented-out multiple assignments are nowhere near as performant as the long-hand equivalents;
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</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;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">}</span>
perhaps there may be a way to narrow down the divide in some future release of the compiler...
 
<lang Phix>global function quick_select(sequence s, integer k)
integer left = 1, right = length(s), pos
object pivotv, tmp
<span style="color: #008080;">function</span> <span style="color: #000000;">quick_select</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
while left<right do
<span style="color: #004080;">integer</span> <span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">right</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>
pivotv = s[k];
<span style="color: #008080;">while</span> <span style="color: #000000;">left</span><span style="color: #0000FF;"><</span><span style="color: #000000;">right</span> <span style="color: #008080;">do</span>
-- {s[k], s[right]} = {s[right], s[k]}
<span style="color: #004080;">object</span> <span style="color: #000000;">pivotv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">];</span>
tmp = s[k]
<span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</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;">right</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]}</span>
s[k] = s[right]
<span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">left</span>
s[right]=tmp
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">left</span> <span style="color: #008080;">to</span> <span style="color: #000000;">right</span> <span style="color: #008080;">do</span>
pos = left
<span style="color: #008080;">if</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;">pivotv</span> <span style="color: #008080;">then</span>
for i=left to right do
<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;">pos</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;">pos</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>
if s[i]<pivotv then
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
-- {s[i], s[pos]} = {s[pos], s[i]}
<span style="color: #008080;">end</span> tmp<span style="color: s[i]#008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
s[i] = s[pos]
<span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</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;">pos</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">]}</span>
s[pos]=tmp
<span style="color: #008080;">if</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">==</span><span style="color: #000000;">k</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>
pos += 1
<span style="color: #008080;">if</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;"><</span><span style="color: #000000;">k</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
end for
<span style="color: #008080;">else</span>
-- {s[right], s[pos]} = {s[pos], s[right]}
<span style="color: #000000;">right</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span>
tmp = s[right]
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
s[right] = s[pos]
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
s[pos]=tmp
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
if pos==k then exit end if
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
if pos<k then
left = pos + 1
<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: #000000;">10</span> <span style="color: #008080;">do</span>
else
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">quick_select</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
right = pos - 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;">" %d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end while
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
return {s,s[k]}
<!--</lang>-->
end function
 
sequence s = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4}
integer r
for i=1 to 10 do
{s,r} = quick_select(s,i)
printf(1," %d",r)
end for
{} = wait_key()</lang>
{{out}}
<pre>
Petelomax
7,805

edits

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