Rosetta Code

Sorting algorithms/Heapsort: Difference between revisions

Page Discussion

Sorting algorithms/Heapsort (view source)

Revision as of 11:11, 27 August 2021

1,197 bytes removed ,  2 years ago
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)▼
if (listLen >< 12) 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
-- The list index of each heap node's first child is calculated as la +script (nproperty -to l)allow *faster creferences +to 1,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
▲ -- c is 2 inIn a binary heap, sothe welist getindex of each node's first child is (nnode index * 2) - (l - 1). Preset the constant part here.
▲ property const : l - 1
-- SiftPrivate subhandler: sift a value down into the heap from a given root node.▼
on hsrt(l, r)
on siftDown(siftValuesiftV, rootnode, endOfHeap)▼
-- Arrange the sort range into a "heap" with its "top" at the leftmost position.▼
repeatset withchild ito fromnode (l + r) div* 2 to- l by -1const
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)
--set DeterminechildV theto higher-valuedmy childlst's ofitem this root (if more than one).child
set childValue to item child of my lst
if (child comes before endOfHeap) then
set child2 to child + 1
set child2Valuechild2V to my lst's item child2 of my lst
if (child2Valuechild2V > childValuechildV) then
set child to child2
set childValuechildV to child2Valuechild2V
end if
end if
if (childV > siftV) then
-- If the higher childset valuemy lst's greateritem than the one being sifted down, advance itnode to this nodechildV
-- and prepare to repeat the above with theset node from which it came. Otherwise stopto sifting.child
if (childValue > siftValue) thenset child to node * 2 - const
set item root of my lst to childValue
set root to child
set child to root * 2 - const
else
exit repeat
Line 708 ⟶ 693:
-- Insert the sifted-down value at the node reached.
set itemmy rootlst's ofitem my lstnode to siftValuesiftV
end siftDown
end script
▲ -- Arrange the sort range into a "heap" with its "top" at the leftmost position.
▲ set listLen to (count theList)
▲ repeat with endOfHeapi from r to (l + 1r) div 2 to l by -1
▲ if (listLen > 1) then
--tell Converto negativeto and/orsiftDown(its transposedlst's rangeitem indices.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
repeat with endOfHeap from ifr to (l >+ r1) thenby set {l, r} to {r, l}-1
set endV to o's lst's item endOfHeap
▲ set removedValueo's tolst's item endOfHeap ofto myo's lst's item l
-- Do the sort.
tell o's hsrtto siftDown(endV, l, rendOfHeap - 1)
end ifrepeat
return -- nothing
end heapSort
property sort : heapSort
 
-- Demo:
set aList to {}
local aList
repeat with i from 1 to 25
Sorted:set aList to {074, 1095, 119, 1356, 1376, 2233, 2251, 2227, 2462, 2755, 2886, 3960, 4165, 4432, 4710, 5162, 5372, 5487, 6386, 6685, 7536, 7820, 8444, 8817, 9360}"</pre>▼
set end of aList to (random number 100)
sort(aList, 1, -1) -- Sort items 1 thru -1 of a copyaList.▼
end repeat
return outputaList</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}}
<prelang applescript>"Original:9, {2810, 3917, 4120, 27, 7832, 1333, 1136, 8844, 1051, 6355, 1356, 2460, 5160, 8462, 4762, 2265, 072, 7574, 6676, 9385, 2286, 5486, 4487, 22, 5395}</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}}==
Nig
557

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/120735"