Sorting algorithms/Heapsort: Difference between revisions
m
→{{header|AppleScript}}: Tidied.
m (→{{header|AppleScript}}: Tidied.) |
|||
Line 657:
-- Heap sort algorithm: J.W.J. Williams.
on heapSort(theList, l, r) -- Sort items l thru r of theList.
set listLen to (count theList)▼
-- Convert negative and/or transposed range indices.
if (l > r) then set {l, r} to {r, l}
script o
-- The list
-- c is 2 in a binary heap, so we get (n * 2) - (l - 1). Preset the constant part here.▼
property const : l - 1▼
property lst : theList
▲ --
▲ property const : l - 1
-- Arrange the sort range into a "heap" with its "top" at the leftmost position.▼
end repeat▼
repeat with endOfHeap from r to (l + 1) by -1▼
set removedValue to item endOfHeap of my lst▼
▲ -- Sift a value down into the heap from a given root node.
▲ on siftDown(siftValue, root, endOfHeap)
repeat until (child comes after endOfHeap)
if (child comes before endOfHeap) then
set child2 to child + 1
set
if (
set child to child2
set
end if
end if
if (childV > siftV) then
else
exit repeat
Line 708 ⟶ 693:
-- Insert the sifted-down value at the node reached.
set
end siftDown
end script
▲ set listLen to (count theList)
▲ if (listLen > 1) then
▲ if (l < 0) then set l to listLen + l + 1
▲ if (r < 0) then set r to listLen + r + 1
repeat with endOfHeap from
set endV to o's lst's item endOfHeap
tell o
end
return -- nothing
end heapSort
property sort : heapSort
-- Demo:
local aList
▲-- Sort items 1 thru -1 of a copy.
▲return output</lang>
{{output}}
<
▲Sorted: {0, 10, 11, 13, 13, 22, 22, 22, 24, 27, 28, 39, 41, 44, 47, 51, 53, 54, 63, 66, 75, 78, 84, 88, 93}"</pre>
=={{header|ARM Assembly}}==
|