Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
(Updated second D entry) |
(added FunL) |
||
Line 913: | Line 913: | ||
end program Heapsort_Demo</lang> |
end program Heapsort_Demo</lang> |
||
=={{header|FunL}}== |
|||
Direct, line by line translation of the pseudocode. The array object (using Scala's <code>ArraySeq</code> class) has built-in method <code>length</code>, so the <code>count</code> parameter is not needed. |
|||
<lang funl>def heapSort( a ) = |
|||
heapify( a ) |
|||
end = a.length() - 1 |
|||
while end > 0 |
|||
a(end), a(0) = a(0), a(end) |
|||
end-- |
|||
siftDown( a, 0, end ) |
|||
def heapify( a ) = |
|||
start = (a.length() - 2)\2 |
|||
while start >= 0 |
|||
siftDown( a, start, a.length() - 1 ) |
|||
start-- |
|||
def siftDown( a, start, end ) = |
|||
root = start |
|||
while root*2 + 1 <= end |
|||
child = root*2 + 1 |
|||
if child + 1 <= end and a(child) < a(child + 1) |
|||
child++ |
|||
if a(root) < a(child) |
|||
a(root), a(child) = a(child), a(root) |
|||
root = child |
|||
else |
|||
break |
|||
a = array( [7, 2, 6, 1, 9, 5, 0, 3, 8, 4] ) |
|||
heapSort( a ) |
|||
println( a )</lang> |
|||
{{out}} |
|||
<pre> |
|||
ArraySeq(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |