Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
PatGarrett (talk | contribs) m (→{{header|360 Assembly}}: Superfluous blanks suppressed) |
|||
Line 2,677: | Line 2,677: | ||
Input = 6 7 2 1 8 9 5 3 4 |
Input = 6 7 2 1 8 9 5 3 4 |
||
Output = 1 2 3 4 5 6 7 8 9 |
Output = 1 2 3 4 5 6 7 8 9 |
||
</pre> |
|||
=={{header|Phix}}== |
|||
<lang Phix>function siftDown(sequence arr, integer s, integer last) |
|||
integer root = s |
|||
while root*2<=last do |
|||
integer child = root*2 |
|||
if child<last and arr[child]<arr[child+1] then |
|||
child += 1 |
|||
end if |
|||
if arr[root]>=arr[child] then exit end if |
|||
object tmp = arr[root] |
|||
arr[root] = arr[child] |
|||
arr[child] = tmp |
|||
root = child |
|||
end while |
|||
return arr |
|||
end function |
|||
function heapify(sequence arr, integer count) |
|||
integer s = floor(count/2) |
|||
while s>0 do |
|||
arr = siftDown(arr,s,count) |
|||
s -= 1 |
|||
end while |
|||
return arr |
|||
end function |
|||
function heap_sort(sequence arr) |
|||
integer last = length(arr) |
|||
arr = heapify(arr,last) |
|||
while last>1 do |
|||
object tmp = arr[1] |
|||
arr[1] = arr[last] |
|||
arr[last] = tmp |
|||
last -= 1 |
|||
arr = siftDown(arr,1,last) |
|||
end while |
|||
return arr |
|||
end function |
|||
?heap_sort({5,"oranges","and",3,"apples"})</lang> |
|||
{{out}} |
|||
<pre> |
|||
{3,5,"and","apples","oranges"} |
|||
</pre> |
</pre> |
||