Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
No edit summary |
(→{{header|FreeBASIC}}: fix a bug (e.g. [1, 2, 3, 4, 5] was wrongly sorted to [1, 2, 3, 5, 4]) and formatting) |
||
| Line 1,546: | Line 1,546: | ||
' for boundary checks on array's compile with: fbc -s console -exx |
' for boundary checks on array's compile with: fbc -s console -exx |
||
' sort from lower bound to the |
' sort from lower bound to the higher bound |
||
' array's can have subscript range from -2147483648 to +2147483647 |
' array's can have subscript range from -2147483648 to +2147483647 |
||
Sub siftdown(hs() As Long, start As ULong |
Sub siftdown(hs() As Long, start As ULong, end_ As ULong) |
||
Dim As ULong root = start |
Dim As ULong root = start |
||
Dim As Long lb = LBound(hs) |
Dim As Long lb = LBound(hs) |
||
While root * 2 +1 < end_ |
While root * 2 + 1 < end_ |
||
Dim As ULong child = root * 2 +1 |
Dim As ULong child = root * 2 + 1 |
||
If (child + |
If (child + 1 < end_) And (hs(lb + child) < hs(lb + child + 1)) Then |
||
child = child +1 |
child = child + 1 |
||
End If |
End If |
||
If hs(lb + root) < hs(lb + child) Then |
If hs(lb + root) < hs(lb + child) Then |
||
| Line 1,566: | Line 1,565: | ||
End If |
End If |
||
Wend |
Wend |
||
End Sub |
End Sub |
||
Sub heapsort(hs() As Long) |
Sub heapsort(hs() As Long) |
||
Dim As Long lb = LBound(hs) |
Dim As Long lb = LBound(hs) |
||
Dim As ULong count = UBound(hs) - lb |
Dim As ULong count = UBound(hs) - lb + 1 |
||
Dim As Long start = (count -2) \ 2 |
Dim As Long start = lb + (count - 2) \ 2 |
||
While start >= 0 |
While start >= 0 |
||
siftdown(hs(), start, count) |
siftdown(hs(), start, count) |
||
start = start -1 |
start = start - 1 |
||
Wend |
Wend |
||
Dim As ULong end_ = count |
Dim As ULong end_ = count - 1 |
||
While end_ > 0 |
While end_ > 0 |
||
Swap hs(lb + end_), hs(lb) |
Swap hs(lb + end_), hs(lb) |
||
siftdown(hs(), 0, end_) |
siftdown(hs(), 0, end_) |
||
end_ = end_ -1 |
end_ = end_ - 1 |
||
Wend |
Wend |
||
End Sub |
End Sub |
||
| Line 1,597: | Line 1,593: | ||
For i = lb To ub : array(i) = i : Next |
For i = lb To ub : array(i) = i : Next |
||
For i = lb To ub |
For i = lb To ub |
||
Swap array(i), array(Int(Rnd * (ub - lb +1)) + lb) |
Swap array(i), array(Int(Rnd * (ub - lb + 1)) + lb) |
||
Next |
Next |
||