Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted
Line 657: Line 657:
-- Heap sort algorithm: J.W.J. Williams.
-- Heap sort algorithm: J.W.J. Williams.
on heapSort(theList, l, r) -- Sort items l thru r of theList.
on heapSort(theList, l, r) -- Sort items l thru r of theList.
⚫
set listLen to (count theList)
⚫
if (listLen < 2) then return
-- Convert negative and/or transposed range indices.
⚫
if (l < 0) then set l to listLen + l + 1
⚫
if (r < 0) then set r to listLen + r + 1
if (l > r) then set {l, r} to {r, l}
⚫
script o
script o
-- The list index of each heap node's first child is calculated as l + (n - l) * c + 1,
-- The list as a script property to allow faster references to its items.
-- where l is the left index of the sort range (top of heap), n the node index, and c the number of children per node.
⚫
-- 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 lst : theList
⚫
-- In a binary heap, the list index of each node's first child is (node index * 2) - (l - 1). Preset the constant part.
⚫
property const : l - 1
⚫
-- Private subhandler: sift a value down into the heap from a given node.
on hsrt(l, r)
⚫
on siftDown(siftV, node, endOfHeap)
⚫
-- Arrange the sort range into a "heap" with its "top" at the leftmost position.
repeat with i from (l + r) div 2 to l by -1
set child to node * 2 - const
siftDown(item i of my lst, i, r)
⚫
end repeat
⚫
-- Sort the heap.
⚫
repeat with endOfHeap from r to (l + 1) by -1
-- Remove the value at the end.
⚫
set removedValue to item endOfHeap of my lst
-- Move the highest value in the heap from the top to the vacated slot.
set item endOfHeap of my lst to item l of my lst
-- Sift the removed value back into the reduced heap from the top.
siftDown(removedValue, l, endOfHeap - 1)
end repeat
end hsrt
⚫
⚫
-- Sift a value down into the heap from a given root node.
⚫
on siftDown(siftValue, root, endOfHeap)
set child to root * 2 - const
repeat until (child comes after endOfHeap)
repeat until (child comes after endOfHeap)
-- Determine the higher-valued child of this root (if more than one).
set childV to my lst's item child
set childValue to item child of my lst
if (child comes before endOfHeap) then
if (child comes before endOfHeap) then
set child2 to child + 1
set child2 to child + 1
set child2Value to item child2 of my lst
set child2V to my lst's item child2
if (child2Value > childValue) then
if (child2V > childV) then
set child to child2
set child to child2
set childValue to child2Value
set childV to child2V
end if
end if
end if
end if
if (childV > siftV) then
-- If the higher child value's greater than the one being sifted down, advance it to this node
set my lst's item node to childV
-- and prepare to repeat the above with the node from which it came. Otherwise stop sifting.
set node to child
if (childValue > siftValue) then
set child to node * 2 - const
set item root of my lst to childValue
set root to child
set child to root * 2 - const
else
else
exit repeat
exit repeat
Line 708: Line 693:
-- Insert the sifted-down value at the node reached.
-- Insert the sifted-down value at the node reached.
set item root of my lst to siftValue
set my lst's item node to siftV
end siftDown
end siftDown
end script
end script
⚫
-- Arrange the sort range into a "heap" with its "top" at the leftmost position.
⚫
set listLen to (count theList)
⚫
repeat with i from (l + r) div 2 to l by -1
⚫
if (listLen > 1) then
-- Convert negative and/or transposed range indices.
tell o to siftDown(its lst's item i, i, r)
⚫
end repeat
⚫
if (l < 0) then set l to listLen + l + 1
⚫
-- Unpick the heap.
⚫
if (r < 0) then set r to listLen + r + 1
if (l > r) then set {l, r} to {r, l}
repeat with endOfHeap from r to (l + 1) by -1
set endV to o's lst's item endOfHeap
⚫
set o's lst's item endOfHeap to o's lst's item l
-- Do the sort.
o's hsrt(l, r)
tell o to siftDown(endV, l, endOfHeap - 1)
end if
end repeat
return -- nothing
return -- nothing
end heapSort
end heapSort
property sort : heapSort


-- Demo:
set aList to {}
local aList
repeat with i from 1 to 25
⚫
set aList to {74, 95, 9, 56, 76, 33, 51, 27, 62, 55, 86, 60, 65, 32, 10, 62, 72, 87, 86, 85, 36, 20, 44, 17, 60}
set end of aList to (random number 100)
⚫
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
end repeat
⚫
return aList</lang>

⚫
-- Sort items 1 thru -1 of a copy.
set sortedCopy to aList's items
heapSort(sortedCopy, 1, -1)

set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ", "
set output to "Original: {" & aList & "}
Sorted: {" & sortedCopy & "}"
set AppleScript's text item delimiters to astid

⚫
return output</lang>


{{output}}
{{output}}
<pre>"Original: {28, 39, 41, 27, 78, 13, 11, 88, 10, 63, 13, 24, 51, 84, 47, 22, 0, 75, 66, 93, 22, 54, 44, 22, 53}
<lang applescript>9, 10, 17, 20, 27, 32, 33, 36, 44, 51, 55, 56, 60, 60, 62, 62, 65, 72, 74, 76, 85, 86, 86, 87, 95}</lang>
⚫
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}}==
=={{header|ARM Assembly}}==
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Heapsort"