Sorting algorithms/Heapsort: Difference between revisions

=={{header|AppleScript}}==

<lang applescript>-- In-place binary heap sort.

-- Heap sort algorithm: J.R.J. Williams.

on heapSort(theList, l, r) -- Sort items l thru r of theList.

script o

-- The list index of each heap node's first child is calculated as l + (n - l) * c + 1,

-- 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

on hsrt(l, r)

-- 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

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)

-- Determine the higher-valued child of this root (if more than one).

set childValue to item child of my lst

if (child comes before endOfHeap) then

set child2 to child + 1

set child2Value to item child2 of my lst

if (child2Value > childValue) then

set child to child2

set childValue to child2Value

end if

end if

-- If the higher child value's greater than the one being sifted down, advance it to this node

-- and prepare to repeat the above with the node from which it came. Otherwise stop sifting.

if (childValue > siftValue) then

set item root of my lst to childValue

set root to child

set child to root * 2 - const

else

exit repeat

end if

end repeat

-- Insert the sifted-down value at the node reached.

set item root of my lst to siftValue

end siftDown

end script

set listLen to (count theList)

if (listLen > 1) then

-- 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}

-- Do the sort.

o's hsrt(l, r)

end if

return -- nothing

end heapSort

set aList to {}

repeat with i from 1 to 25

set end of aList to (random number 100)

end repeat

-- 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}}

<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}

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>