62 lines
2.4 KiB
AppleScript
62 lines
2.4 KiB
AppleScript
-- Based on the heap sort algorithm ny J.W.J. Williams.
|
|
on getMedian(theList, l, r)
|
|
script o
|
|
property lst : theList's items l thru r -- Copy of the range to be searched.
|
|
|
|
-- Sift a value down into the heap from a given root node.
|
|
on siftDown(siftV, root, endOfHeap)
|
|
set child to root * 2
|
|
repeat until (child comes after endOfHeap)
|
|
set childV to item child of my lst
|
|
if (child comes before endOfHeap) then
|
|
set child2 to child + 1
|
|
set child2V to item child2 of my lst
|
|
if (child2V > childV) then
|
|
set child to child2
|
|
set childV to child2V
|
|
end if
|
|
end if
|
|
|
|
if (childV > siftV) then
|
|
set item root of my lst to childV
|
|
set root to child
|
|
set child to root * 2
|
|
else
|
|
exit repeat
|
|
end if
|
|
end repeat
|
|
set item root of my lst to siftV
|
|
end siftDown
|
|
end script
|
|
|
|
set r to (r - l + 1)
|
|
-- Arrange the sort range into a "heap" with its "top" at the leftmost position.
|
|
repeat with i from (r + 1) div 2 to 1 by -1
|
|
tell o to siftDown(item i of its lst, i, r)
|
|
end repeat
|
|
|
|
-- Work the heap as if extracting the values that would come after the median when sorted.
|
|
repeat with endOfHeap from r to (r - (r + 1) div 2 + 2) by -1
|
|
tell o to siftDown(item endOfHeap of its lst, 1, endOfHeap - 1)
|
|
end repeat
|
|
-- Extract the median itself, now at the top of the heap.
|
|
set median to beginning of o's lst
|
|
-- If the range has an even number of items, also get the value that would come before the median
|
|
-- just obtained. By now it's either the second or third item in the heap, so no need to sift for it.
|
|
-- Get the average if it and the median.
|
|
if (r mod 2 is 0) then
|
|
set median2 to item 2 of o's lst
|
|
if ((r > 2) and (item 3 of o's lst > median2)) then set median2 to item 3 of o's lst
|
|
set median to (median + median2) / 2
|
|
end if
|
|
|
|
return median
|
|
end getMedian
|
|
|
|
-- Demo:
|
|
local testList
|
|
set testList to {}
|
|
repeat with i from 1 to 8
|
|
set end of testList to (random number 500) / 5
|
|
end repeat
|
|
return {|numbers|:testList, median:getMedian(testList, 1, (count testList))}
|