Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
Line 4,279: | Line 4,279: | ||
{3,5,"and","apples","oranges"} |
{3,5,"and","apples","oranges"} |
||
</pre> |
</pre> |
||
=={{header|Picat}}== |
|||
<lang Picat>main => |
|||
_ = random2(), |
|||
A = [random(-10,10) : _ in 1..30], |
|||
println(A), |
|||
heapSort(A), |
|||
println(A). |
|||
heapSort(A) => |
|||
heapify(A), |
|||
End = A.len, |
|||
while (End > 1) |
|||
swap(A, End, 1), |
|||
End := End - 1, |
|||
siftDown(A, 1, End) |
|||
end. |
|||
heapify(A) => |
|||
Count = A.len, |
|||
Start = Count // 2, |
|||
while (Start >= 1) |
|||
siftDown(A, Start, Count), |
|||
Start := Start - 1 |
|||
end. |
|||
siftDown(A, Start, End) => |
|||
Root = Start, |
|||
Loop = true, |
|||
while (Root * 2 - 1 < End, Loop == true) |
|||
Child := Root * 2- 1, |
|||
if Child + 1 <= End, A[Child] @< A[Child+1] then |
|||
Child := Child + 1 |
|||
end, |
|||
if A[Root] @< A[Child] then |
|||
swap(A,Root, Child), |
|||
Root := Child |
|||
else |
|||
Loop := false |
|||
end |
|||
end. |
|||
swap(L,I,J) => |
|||
T = L[I], |
|||
L[I] := L[J], |
|||
L[J] := T.</lang> |
|||
{{out}} |
|||
<pre>[6,2,3,1,9,2,5,1,-7,1,2,1,-1,-7,2,0,4,-6,4,-8,1,9,3,5,-6,-6,0,7,-8,-2] |
|||
[-8,-8,-7,-7,-6,-6,-6,-2,-1,0,0,1,1,1,1,1,2,2,2,2,3,3,4,4,5,5,6,7,9,9]</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |