Averages/Median: Difference between revisions
→{{header|AppleScript}}: Added a heap sort based solution.
m (→{{header|AppleScript}}: Corrected "By iteration" solution, which was returning random results with even list counts. Tidied "Quickselect".) |
(→{{header|AppleScript}}: Added a heap sort based solution.) |
||
Line 432:
{{output}}
<pre>{|numbers|:{71.6, 44.8, 45.8, 28.6, 96.8, 98.4, 42.4, 97.8}, median:58.7}</pre>
===Partial heap sort===
<lang 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))}
</lang>
{{output}}
<lang applescript>{|numbers|:{28.0, 75.6, 21.4, 51.8, 79.6, 25.0, 95.4, 31.2}, median:41.5}</lang>
=={{header|Applesoft BASIC}}==
| |||