Averages/Median: Difference between revisions

Content added Content deleted
No edit summary
m (→‎{{header|AppleScript}}: Corrected "By iteration" solution, which was returning random results with even list counts. Tidied "Quickselect".)
Line 191: Line 191:


=={{header|AppleScript}}==
=={{header|AppleScript}}==


===By iteration===
===By iteration===
<lang AppleScript>set alist to {1, 2, 3, 4, 5, 6, 7, 8}
<lang applescript>set alist to {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0}
set med to medi(alist)
set med to medi(alist)


Line 200: Line 198:
set temp to {}
set temp to {}
set lcount to count every item of alist
set lcount to count alist
if lcount is equal to 2 then
if lcount is equal to 2 then
return (item (random number from 1 to 2) of alist)
return ((item 1 of alist) + (item 2 of alist)) / 2
else if lcount is less than 2 then
else if lcount is less than 2 then
return item 1 of alist
return item 1 of alist
Line 238: Line 236:
end findmax</lang>
end findmax</lang>

{{output}}
<lang applescript>3.5</lang>


===Composing functionally===
===Composing functionally===
Line 355: Line 356:


===Quickselect===
===Quickselect===
<lang applescript>-- Return the median value of items l thru r of a list of numbers.
<lang AppleScript>on getMedian(theList)
on getMedian(theList, l, r)
if (theList is {}) then return theList
if (theList is {}) then return theList
-- A local "owner" for the potentially long AppleScript list. Speeds up references to its items and properties.
script o
script o
property lst : theList
property lst : theList's items l thru r -- Copy of the range to be searched.
end script
end script
-- But since sorting's involved, use another list containing the same items.
set o's lst to o's lst's items
set listLength to (count theList)
set rangeLength to (r - l + 1)
set m to (listLength + 1) div 2 -- The central position in the list or the leftmost of two.
set m to (rangeLength + 1) div 2 -- Central position in the range copy, or the leftmost of two.
set {l, r} to {1, rangeLength} -- Outer partition indices.
⚫
set previousR to r -- Reminder of previous r.
-- The initial search process is an iterative quickselect: ie. a partial, iterative quicksort (algorithm by Tony Hoare) with subpartitioning only occurring in partitions containing m.
⚫
repeat -- quickselect repeat
-- It stops when the partition traversal indices cross at m, which means that slot m now contains the median value or the leftmost of two.
-- If the number of items in the list is even, a straight sweep is then done for the lowest value partitioned to the right of m and the two results are averaged.
set l to 1
set r to listLength
⚫
set previousR to listLength
⚫
repeat -- quickselect iteration.
set pivot to o's lst's item ((l + r) div 2)
set pivot to o's lst's item ((l + r) div 2)
set i to l
set i to l
set j to r
set j to r
repeat until (i > j) -- Partitioning repeat.
repeat until (i > j)
set leftValue to o's lst's item i
set lv to o's lst's item i
repeat while (leftValue < pivot)
repeat while (lv < pivot)
set i to i + 1
set i to i + 1
set leftValue to o's lst's item i
set lv to o's lst's item i
end repeat
end repeat
set rightValue to o's lst's item j
set rv to o's lst's item j
repeat while (rightValue > pivot)
repeat while (rv > pivot)
set j to j - 1
set j to j - 1
set rightValue to o's lst's item j
set rv to o's lst's item j
end repeat
end repeat
if (i > j) then
if (i > j) then
else
else
set o's lst's item i to rightValue
set o's lst's item i to rv
set o's lst's item j to leftValue
set o's lst's item j to lv
set i to i + 1
set i to i + 1
set j to j - 1
set j to j - 1
Line 400: Line 394:
end repeat
end repeat
-- Check where the partitioning indices have ended up in relation to m.
-- If i and j have crossed at m, item m's the median value.
-- Otherwise reset to partition the partition containing m.
if (j < m) then
if (j < m) then
-- If they crossed at m, it now contains the median value or the leftmost of two, so finish the quickselect.
if (i > m) then exit repeat
if (i > m) then exit repeat
-- Otherwise they crossed to the left of m. Prepare to subpartition the right partition.
set l to i
set l to i
else
else
-- They crossed to the right of m. Prepare to subpartition the left, but keep a note of the current right boundary in case it's needed below.
set previousR to r
set previousR to r
set r to j
set r to j
end if
end if
end repeat -- quickselect.
end repeat
set median to item m of o's lst
set median to item m of o's lst
-- If the list contains an even number of items, find the lowest value to the right of the one just obtained and average the two.
-- If the range has an even number of items, find the lowest value to the right of m and average it
-- with the median just obtained. We only need to search to the end of the range just partitioned —
⚫
if (listLength mod 2 is 0) then
⚫
-- unless that's where m is, in which case to end of the most recent extent beyond that (if any).
⚫
set median2 to item (m + 1) of o's lst
⚫
if (rangeLength mod 2 is 0) then
⚫
-- It's only necessary to search to the end of the current partition — unless that's m itself, in which case to end of the most recent partition to its right (if any).
⚫
set median2 to item i of o's lst
if (r = m) then set r to previousR
if (r = m) then set r to previousR
repeat with i from (m + 2) to r
repeat with i from (i + 1) to r
set thisValue to item i of o's lst
set v to item i of o's lst
if (thisValue < median2) then set median2 to thisValue
if (v < median2) then set median2 to v
end repeat
end repeat
set median to (median + median2) / 2
set median to (median + median2) / 2
Line 430: Line 423:


-- Demo:
-- Demo:
local testList
set testList to {}
set testList to {}
repeat with i from 1 to 8
repeat with i from 1 to 8
set end of my testList to (random number 500) / 5
set end of testList to (random number 500) / 5
end repeat
end repeat
⚫
return {|numbers|:testList, median:getMedian(testList, 1, (count testList))}</lang>

set m to getMedian(testList)
⚫
return {|numbers|:testList, median:m}</lang>


{{output}}
{{output}}
Retrieved from "https://rosettacode.org/wiki/Averages/Median"