Averages/Median: Difference between revisions
Content added Content deleted
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: | Line 432: | ||
{{output}} |
{{output}} |
||
<pre>{|numbers|:{71.6, 44.8, 45.8, 28.6, 96.8, 98.4, 42.4, 97.8}, median:58.7}</pre> |
<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}}== |
=={{header|Applesoft BASIC}}== |