Rosetta Code

Averages/Median: Difference between revisions

Page Discussion

Averages/Median (view source)

Revision as of 14:11, 22 August 2021

951 bytes removed ,  2 years ago
m
→‎{{header|AppleScript}}: Corrected "By iteration" solution, which was returning random results with even list counts. Tidied "Quickselect".
No edit summary
m (→‎{{header|AppleScript}}: Corrected "By iteration" solution, which was returning random results with even list counts. Tidied "Quickselect".)
Line 191:
 
=={{header|AppleScript}}==
 
 
===By iteration===
<lang AppleScriptapplescript>set alist to {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0}
set med to medi(alist)
 
Line 200 ⟶ 198:
set temp to {}
set lcount to count every item of alist
if lcount is equal to 2 then
return ((item (random1 numberof fromalist) 1+ to(item 2) of alist)) / 2
else if lcount is less than 2 then
return item 1 of alist
Line 238 ⟶ 236:
end findmax</lang>
 
{{output}}
<lang applescript>3.5</lang>
 
===Composing functionally===
Line 355 ⟶ 356:
 
===Quickselect===
<lang applescript>-- Return the median value of items l thru r of a list of numbers.
<lang AppleScript>on getMedian(theList, l, r)
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
property lst : theList's items l thru r -- Copy of the range to be searched.
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 listLengthrangeLength to (countr theList- l + 1)
set m to (listLengthrangeLength + 1) div 2 -- The centralCentral position in the listrange copy, or the leftmost of two.
set {l, r} to {1, rangeLength} -- Outer partition indices.
set previousR to listLengthr -- 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 iteration.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 i to l
set j to r
repeat until (i > j) -- Partitioning repeat.
set leftValuelv to o's lst's item i
repeat while (leftValuelv < pivot)
set i to i + 1
set leftValuelv to o's lst's item i
end repeat
set rightValuerv to o's lst's item j
repeat while (rightValuerv > pivot)
set j to j - 1
set rightValuerv to o's lst's item j
end repeat
if (i > j) then
else
set o's lst's item i to rightValuerv
set o's lst's item j to leftValuelv
set i to i + 1
set j to j - 1
Line 400 ⟶ 394:
end repeat
-- CheckIf wherei theand partitioning indicesj have endedcrossed upat inm, relation toitem m's the median value.
-- Otherwise reset to partition the partition containing m.
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
-- Otherwise they crossed to the left of m. Prepare to subpartition the right partition.
set l to i
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 r to j
end if
end repeat -- quickselect.
set median to item m of o's lst
-- If the listrange containshas an even number of items, find the lowest value to the right of the one just obtainedm and average the two.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▼
-- It's only necessary to search to the end of the current partition — unless that's where m itselfis, in which case to end of the most recent partitionextent tobeyond its rightthat (if any).▼
set median2 to item (m + 1) of o's lst▼
▲ if (listLengthrangeLength 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 (m + 1)i of o's lst
if (r = m) then set r to previousR
repeat with i from (mi + 21) to r
set thisValuev to item i of o's lst
if (thisValuev < median2) then set median2 to thisValuev
end repeat
set median to (median + median2) / 2
Line 430 ⟶ 423:
 
-- Demo:
local testList
set testList to {}
repeat with i from 1 to 8
set end of my testList to (random number 500) / 5
end repeat
return {|numbers|:testList, median:mgetMedian(testList, 1, (count testList))}</lang>▼
 
set m to getMedian(testList)
▲return {|numbers|:testList, median:m}</lang>
 
{{output}}
Nig
557

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/115705"