Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
(Replace translated implementation with native implementation of pseudocode from the introduction) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 3,711: | Line 3,711: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<lang Phix>(phixonline)--> |
|||
<lang Phix>function siftDown(sequence arr, integer s, integer last) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer root = s |
|||
while root*2<=last do |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">)</span> |
|||
integer child = root*2 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span> |
|||
if child<last and arr[child]<arr[child+1] then |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">last</span> <span style="color: #008080;">do</span> |
|||
child += 1 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">child</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span> |
|||
end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">child</span><span style="color: #0000FF;"><</span><span style="color: #000000;">last</span> <span style="color: #008080;">and</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
if arr[root]>=arr[child] then exit end if |
|||
<span style="color: #000000;">child</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
object tmp = arr[root] |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
arr[root] = arr[child] |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]>=</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</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> |
|||
arr[child] = tmp |
|||
<span style="color: #004080;">object</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]</span> |
|||
root = child |
|||
<span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</span> |
|||
end while |
|||
<span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span> |
|||
return arr |
|||
<span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">child</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">arr</span> |
|||
function heapify(sequence arr, integer count) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
integer s = floor(count/2) |
|||
while s>0 do |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">heapify</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">)</span> |
|||
arr = siftDown(arr,s,count) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
s -= 1 |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span> |
|||
end while |
|||
<span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span> |
|||
return arr |
|||
<span style="color: #000000;">s</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: #008080;">return</span> <span style="color: #000000;">arr</span> |
|||
function heap_sort(sequence arr) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
integer last = length(arr) |
|||
arr = heapify(arr,last) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">heap_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">)</span> |
|||
while last>1 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">)</span> |
|||
object tmp = arr[1] |
|||
<span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">heapify</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last</span><span style="color: #0000FF;">)</span> |
|||
arr[1] = arr[last] |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
arr[last] = tmp |
|||
<span style="color: #004080;">object</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
last -= 1 |
|||
<span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span> |
|||
arr = siftDown(arr,1,last) |
|||
<span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span> |
|||
end while |
|||
<span style="color: #000000;">last</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
return arr |
|||
<span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last</span><span style="color: #0000FF;">)</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">arr</span> |
|||
?heap_sort({5,"oranges","and",3,"apples"})</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">heap_sort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"oranges"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"and"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"apples"</span><span style="color: #0000FF;">})</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |