Averages/Median

From Rosetta Code
(Redirected from Average/Median)
Jump to: navigation, search
Task
Averages/Median
You are encouraged to solve this task according to the task description, using any language you may know.
Write a program to find the median value of a vector of floating-point numbers. The program need not handle the case where the vector is empty, but must handle the case where there are an even number of elements. In that case, return the average of the two middle values.

There are several approaches to this. One is to sort the elements, and then pick the one(s) in the middle. Sorting would take at least O(n logn). Another would be to build a priority queue from the elements, and then extract half of the elements to get to the middle one(s). This would also take O(n logn). The best solution is to use the selection algorithm to find the median in O(n) time.

See also: Mean, Mode

Contents

[edit] Ada

with Ada.Text_IO, Ada.Float_Text_IO;
 
procedure FindMedian is
 
f: array(1..10) of float := ( 4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5 );
min_idx: integer;
min_val, median_val, swap: float;
 
begin
for i in f'range loop
min_idx := i;
min_val := f(i);
for j in i+1 .. f'last loop
if f(j) < min_val then
min_idx := j;
min_val := f(j);
end if;
end loop;
swap := f(i); f(i) := f(min_idx); f(min_idx) := swap;
end loop;
 
if f'length mod 2 /= 0 then
median_val := f( f'length/2+1 );
else
median_val := ( f(f'length/2) + f(f'length/2+1) ) / 2.0;
end if;
 
Ada.Text_IO.Put( "Median value: " );
Ada.Float_Text_IO.Put( median_val );
Ada.Text_IO.New_line;
end FindMedian;

[edit] APL

median←{v←⍵[⍋⍵]⋄.5×v[⌈¯1+.5×⍴v]+v[⌊.5×⍴v]} ⍝ Assumes ⎕IO←0

First, the input vector ⍵ is sorted with ⍵[⍋⍵] and the result placed in v. If the dimension ⍴v of v is odd, then both ⌈¯1+.5×⍴v and ⌊.5×⍴v give the index of the middle element. If ⍴v is even, ⌈¯1+.5×⍴v and ⌊.5×⍴v give the indices of the two middle-most elements. In either case, the average of the elements at these indices gives the median.

Note that the index origin ⎕IO is assumed zero. To set it to zero use:
⎕IO←0

If you prefer an index origin of 1, use this code instead:

 
⎕IO←1
median←{v←⍵[⍋⍵] ⋄ 0.5×v[⌈0.5×⍴v]+v[⌊1+0.5×⍴v]}
 

This code was tested with ngn/apl and Dyalog 12.1. You can try this function online with ngn/apl. Note that ngn/apl currently only supports index origin 0. Examples:

median 1 5 3 6 4 2
3.5

median 1 5 3 2 4
3

median 4.4 2.3 ¯1.7 7.5 6.6 0.0 1.9 8.2 9.3 4.5
4.45

median 4.1 4 1.2 6.235 7868.33
4.1

median 4.1 5.6 7.2 1.7 9.3 4.4 3.2
4.4

median 4.1 7.2 1.7 9.3 4.4 3.2
4.25

Caveats: To keep it simple, no input validation is done. If you input a vector with zero elements (e.g., ⍳0), you get an INDEX ERROR. If you input a vector with 1 element, you get a RANK ERROR. Only (rank 1) numeric vectors of dimension 2 or more are supported. If you input a (rank 2 or more) matrix, you get a RANK ERROR. If you input a string (vector of chars), you get a DOMAIN ERROR:

median ⍳0
INDEX ERROR

median 66.6
RANK ERROR

median (2 2)⍴⍳4 ⍝ 2x2 matrix
RANK ERROR

median 'HELLO'
DOMAIN ERROR

[edit] AppleScript

set alist to {1,2,3,4,5,6,7,8}
set med to medi(alist)
 
on medi(alist)
 
set temp to {}
set lcount to count every item of alist
if lcount is equal to 2 then
return (item (random number from 1 to 2) of alist)
else if lcount is less than 2 then
return item 1 of alist
else --if lcount is greater than 2
set min to findmin(alist)
set max to findmax(alist)
repeat with x from 1 to lcount
if x is not equal to min and x is not equal to max then set end of temp to item x of alist
end repeat
set med to medi(temp)
end if
return med
 
end medi
 
on findmin(alist)
 
set min to 1
set alength to count every item of alist
repeat with x from 1 to alength
if item x of alist is less than item min of alist then set min to x
end repeat
return min
 
end findmin
 
on findmax(alist)
 
set max to 1
set alength to count every item of alist
repeat with x from 1 to alength
if item x of alist is greater than item max of alist then set max to x
end repeat
return max
 
end findmax

[edit] Applesoft BASIC

 100 REMMEDIAN
110 K = INT(L/2) : GOSUB 150
120 R = X(K)
130 IF L - 2 * INT (L / 2) THEN R = (R + X(K + 1)) / 2
140 RETURN
 
150 REMQUICK SELECT
160 LT = 0:RT = L - 1
170 FOR J = LT TO RT STEP 0
180 PT = X(K)
190 P1 = K:P2 = RT: GOSUB 300
200 P = LT
210 FOR I = P TO RT - 1
220 IF X(I) < PT THEN P1 = I:P2 = P: GOSUB 300:P = P + 1
230 NEXT I
240 P1 = RT:P2 = P: GOSUB 300
250 IF P = K THEN RETURN
260 IF P < K THEN LT = P + 1
270 IF P > = K THEN RT = P - 1
280 NEXT J
290 RETURN
 
300 REMSWAP
310 H = X(P1):X(P1) = X(P2)
320 X(P2) = H: RETURN
Example:
X(0)=4.4 : X(1)=2.3 : X(2)=-1.7 : X(3)=7.5 : X(4)=6.6 : X(5)=0.0 : X(6)=1.9 : X(7)=8.2 : X(8)=9.3 : X(9)=4.5 : X(10)=-11.7
L = 11 : GOSUB 100MEDIAN
? R
Output:
5.95

[edit] AutoHotkey

Takes the lower of the middle two if length is even

seq = 4.1, 7.2, 1.7, 9.3, 4.4, 3.2, 5
MsgBox % median(seq, "`,") ; 4.1
 
median(seq, delimiter)
{
Sort, seq, ND%delimiter%
StringSplit, seq, seq, % delimiter
median := Floor(seq0 / 2)
Return seq%median%
}

[edit] AWK

AWK arrays can be passed as parameters, but not returned, so they are usually global.

#!/usr/bin/awk -f
 
BEGIN {
d[1] = 3.0
d[2] = 4.0
d[3] = 1.0
d[4] = -8.4
d[5] = 7.2
d[6] = 4.0
d[7] = 1.0
d[8] = 1.2
showD("Before: ")
gnomeSortD()
showD("Sorted: ")
printf "Median: %f\n", medianD()
exit
}
 
function medianD( len, mid) {
len = length(d)
mid = int(len/2) + 1
if (len % 2) return d[mid]
else return (d[mid] + d[mid-1]) / 2.0
}
 
function gnomeSortD( i) {
for (i = 2; i <= length(d); i++) {
if (d[i] < d[i-1]) gnomeSortBackD(i)
}
}
 
function gnomeSortBackD(i, t) {
for (; i > 1 && d[i] < d[i-1]; i--) {
t = d[i]
d[i] = d[i-1]
d[i-1] = t
}
}
 
function showD(p, i) {
printf p
for (i = 1; i <= length(d); i++) {
printf d[i] " "
}
print ""
}
 

Example output:

Before: 3 4 1 -8.4 7.2 4 1 1.2 
Sorted: -8.4 1 1 1.2 3 4 4 7.2 
Median: 2.100000

[edit] BASIC

Works with: FreeBASIC
Works with: PowerBASIC
Works with: QB64
Works with: QBasic
Works with: Visual Basic

This uses the Quicksort function described at Quicksort#BASIC, with arr()'s type changed to SINGLE.

Note that in order to truly work with the Windows versions of PowerBASIC, the module-level code must be contained inside FUNCTION PBMAIN. Similarly, in order to work under Visual Basic, the same module-level code must be contained with Sub Main.

DECLARE FUNCTION median! (vector() AS SINGLE)
 
DIM vec1(10) AS SINGLE, vec2(11) AS SINGLE, n AS INTEGER
 
RANDOMIZE TIMER
 
FOR n = 0 TO 10
vec1(n) = RND * 100
vec2(n) = RND * 100
NEXT
vec2(11) = RND * 100
 
PRINT median(vec1())
PRINT median(vec2())
 
FUNCTION median! (vector() AS SINGLE)
DIM lb AS INTEGER, ub AS INTEGER, L0 AS INTEGER
lb = LBOUND(vector)
ub = UBOUND(vector)
REDIM v(lb TO ub) AS SINGLE
FOR L0 = lb TO ub
v(L0) = vector(L0)
NEXT
quicksort v(), lb, ub
IF ((ub - lb + 1) MOD 2) THEN
median = v((ub + lb) / 2)
ELSE
median = (v(INT((ub + lb) / 2)) + v(INT((ub + lb) / 2) + 1)) / 2
END IF
END FUNCTION

See also: BBC BASIC, Liberty BASIC, PureBasic, TI-83 BASIC, TI-89 BASIC.

[edit] BBC BASIC

      INSTALL @lib$+"SORTLIB"
Sort% = FN_sortinit(0,0)
 
DIM a(6), b(5)
a() = 4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2
b() = 4.1, 7.2, 1.7, 9.3, 4.4, 3.2
 
PRINT "Median of a() is " ; FNmedian(a())
PRINT "Median of b() is " ; FNmedian(b())
END
 
DEF FNmedian(a())
LOCAL C%
C% = DIM(a(),1) + 1
CALL Sort%, a(0)
= (a(C% DIV 2) + a((C%-1) DIV 2)) / 2
 

Output:

Median of a() is 4.4
Median of b() is 4.25

[edit] Bracmat

Bracmat has no floating point numbers, so we have to parse floating point numbers as strings and convert them to rational numbers. Each number is packaged in a little list and these lists are accumulated in a sum. Bracmat keeps sums sorted, so the median is the term in the middle of the list, or the average of the two terms in the middle of the list.

(median=
begin decimals end int list med med1 med2 num number
. 0:?list
& whl
' ( @( !arg
 :  ?
((%@:~" ":~",") ?:?number)
((" "|",") ?arg|:?arg)
)
& @( !number
 : ( #?int "." [?begin #?decimals [?end
& !int+!decimals*10^(!begin+-1*!end):?num
| ?num
)
)
& (!num.)+!list:?list
)
& !list:?+[?end
& (  !end*1/2:~/
& !list:?+[!(=1/2*!end+-1)+(?med1.)+(?med2.)+?
& !med1*1/2+!med2*1/2:?med
| !list:?+[(div$(1/2*!end,1))+(?med.)+?
)
& !med
);


 median$" 4.1 4 1.2 6.235 7868.33"      
 41/10

 median$"4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5"
 89/20

 median$"1, 5, 3, 2, 4"
 3

 median$"1, 5, 3, 6, 4, 2"
 7/2

[edit] C

#include <stdio.h>
#include <stdlib.h>
 
typedef struct floatList {
float *list;
int size;
} *FloatList;
 
int floatcmp( const void *a, const void *b) {
if (*(const float *)a < *(const float *)b) return -1;
else return *(const float *)a > *(const float *)b;
}
 
float median( FloatList fl )
{
qsort( fl->list, fl->size, sizeof(float), floatcmp);
return 0.5 * ( fl->list[fl->size/2] + fl->list[(fl->size-1)/2]);
}
 
int main()
{
static float floats1[] = { 5.1, 2.6, 6.2, 8.8, 4.6, 4.1 };
static struct floatList flist1 = { floats1, sizeof(floats1)/sizeof(float) };
 
static float floats2[] = { 5.1, 2.6, 8.8, 4.6, 4.1 };
static struct floatList flist2 = { floats2, sizeof(floats2)/sizeof(float) };
 
printf("flist1 median is %7.2f\n", median(&flist1)); /* 4.85 */
printf("flist2 median is %7.2f\n", median(&flist2)); /* 4.60 */
return 0;
}

[edit] Quickselect algorithm

Average O(n) time:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX_ELEMENTS 1000000
 
/* Return the k-th smallest item in array x of length len */
double quick_select(int k, double *x, int len)
{
inline void swap(int a, int b)
{
double t = x[a];
x[a] = x[b], x[b] = t;
}
 
int left = 0, right = len - 1;
int pos, i;
double pivot;
 
while (left < right)
{
pivot = x[k];
swap(k, right);
for (i = pos = left; i < right; i++)
{
if (x[i] < pivot)
{
swap(i, pos);
pos++;
}
}
swap(right, pos);
if (pos == k) break;
if (pos < k) left = pos + 1;
else right = pos - 1;
}
return x[k];
}
 
int main(void)
{
int i, length;
double *x, median;
 
/* Initialize random length double array with random doubles */
srandom(time(0));
length = random() % MAX_ELEMENTS;
x = malloc(sizeof(double) * length);
for (i = 0; i < length; i++)
{
// shifted by RAND_MAX for negative values
// divide by a random number for floating point
x[i] = (double)(random() - RAND_MAX / 2) / (random() + 1); // + 1 to not divide by 0
}
 
 
if (length % 2 == 0) // Even number of elements, median is average of middle two
{
median = (quick_select(length / 2, x, length) + quick_select(length / 2 - 1, x, length / 2)) / 2;
}
else // select middle element
{
median = quick_select(length / 2, x, length);
}
 
 
/* Sanity testing of median */
int less = 0, more = 0, eq = 0;
for (i = 0; i < length; i++)
{
if (x[i] < median) less ++;
else if (x[i] > median) more ++;
else eq ++;
}
printf("length: %d\nmedian: %lf\n<: %d\n>: %d\n=: %d\n", length, median, less, more, eq);
 
free(x);
return 0;
}
 

Output:

length: 992021
median: 0.000473
<: 496010
>: 496010
=: 1

[edit] C++

This function runs in linear time on average.

#include <algorithm>
 
// inputs must be random-access iterators of doubles
// Note: this function modifies the input range
template <typename Iterator>
double median(Iterator begin, Iterator end) {
// this is middle for odd-length, and "upper-middle" for even length
Iterator middle = begin + (end - begin) / 2;
 
// This function runs in O(n) on average, according to the standard
std::nth_element(begin, middle, end);
 
if ((end - begin) % 2 != 0) { // odd length
return *middle;
} else { // even length
// the "lower middle" is the max of the lower half
Iterator lower_middle = std::max_element(begin, middle);
return (*middle + *lower_middle) / 2.0;
}
}
 
#include <iostream>
 
int main() {
double a[] = {4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2};
double b[] = {4.1, 7.2, 1.7, 9.3, 4.4, 3.2};
 
std::cout << median(a+0, a + sizeof(a)/sizeof(a[0])) << std::endl; // 4.4
std::cout << median(b+0, b + sizeof(b)/sizeof(b[0])) << std::endl; // 4.25
 
return 0;
}

[edit] C#

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Parallel;
namespace Test {
class Program {
static void Main(string[] args) {
/*
* We Use Linq To Determine The Median
* It could be done ofcourse the Normal way
*/

List<double> myList = new List<double>() { 1, 5, 3, 6, 4, 2 };
 
var query = from numbers in myList //select the numbers
orderby numbers ascending
select numbers;
 
if (myList.Count % 2 == 0) { //we know its even
int element = myList.Count / 2; ;
double median = (double)((query.ElementAt(element - 1) + query.ElementAt(element))/2);
Console.WriteLine(median);
} else {
//we know its odd
double element = (double)myList.Count / 2;
element = Math.Round(element, MidpointRounding.AwayFromZero);
double median = (double)query.ElementAt((int)(element - 1));
Console.WriteLine(median);
}
Console.ReadLine();
}
}
}

[edit] Clojure

Simple:

(defn median [ns]
(let [ns (sort ns)
cnt (count ns)
mid (bit-shift-right cnt 1)]
(if (odd? cnt)
(nth ns mid)
(/ (+ (nth ns mid) (nth ns (dec mid))) 2))))

[edit] COBOL

Intrinsic function:

FUNCTION MEDIAN(some-table (ALL))

[edit] Common Lisp

The recursive partitioning solution, without the median of medians optimization.

((defun select-nth (n list predicate)
"Select nth element in list, ordered by predicate, modifying list."
(do ((pivot (pop list))
(ln 0) (left '())
(rn 0) (right '()))
((endp list)
(cond
((< n ln) (select-nth n left predicate))
((eql n ln) pivot)
((< n (+ ln rn 1)) (select-nth (- n ln 1) right predicate))
(t (error "n out of range."))))
(if (funcall predicate (first list) pivot)
(psetf list (cdr list)
(cdr list) left
left list
ln (1+ ln))
(psetf list (cdr list)
(cdr list) right
right list
rn (1+ rn)))))
 
(defun median (list predicate)
(select-nth (floor (length list) 2) list predicate))

[edit] D

import std.stdio, std.algorithm;
 
T median(T)(T[] nums) pure nothrow {
nums.sort();
if (nums.length & 1)
return nums[$ / 2];
else
return (nums[$ / 2 - 1] + nums[$ / 2]) / 2.0;
}
 
void main() {
auto a1 = [5.1, 2.6, 6.2, 8.8, 4.6, 4.1];
writeln("Even median: ", a1.median);
 
auto a2 = [5.1, 2.6, 8.8, 4.6, 4.1];
writeln("Odd median: ", a2.median);
}
Output:
Even median: 4.85
Odd median:  4.6

[edit] Delphi

program AveragesMedian;
 
{$APPTYPE CONSOLE}
 
uses Generics.Collections, Types;
 
function Median(aArray: TDoubleDynArray): Double;
var
lMiddleIndex: Integer;
begin
TArray.Sort<Double>(aArray);
 
lMiddleIndex := Length(aArray) div 2;
if Odd(Length(aArray)) then
Result := aArray[lMiddleIndex]
else
Result := (aArray[lMiddleIndex - 1] + aArray[lMiddleIndex]) / 2;
end;
 
begin
Writeln(Median(TDoubleDynArray.Create(4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2)));
Writeln(Median(TDoubleDynArray.Create(4.1, 7.2, 1.7, 9.3, 4.4, 3.2)));
end.

[edit] E

TODO: Use the selection algorithm, whatever that is

def median(list) {
def sorted := list.sort()
def count := sorted.size()
def mid1 := count // 2
def mid2 := (count - 1) // 2
if (mid1 == mid2) { # avoid inexact division
return sorted[mid1]
} else {
return (sorted[mid1] + sorted[mid2]) / 2
}
}
? median([1,9,2])
# value: 2
 
? median([1,9,2,4])
# value: 3.0

[edit] Elena

#define system.
#define system'routines.
#define extensions.
#define extensions'math.
 
#symbol median = (:anArray)
[
#var aSorted := arrayControl sort:(anArray~indexable array).
 
#var aLen := aSorted length.
^ aLen =>
0 ? [ nil ]
 ! [
#var aMiddleIndex := aLen / 2.
^ (modulus:aLen:2) =>
0 ? [ (aSorted@(aMiddleIndex - 1) + aSorted@aMiddleIndex) / 2 ]
 ! [ aSorted@aMiddleIndex ].
].
].
 
#symbol program =
[
consoleEx writeLine:(median:(4.1r, 5.6r, 7.2r, 1.7r, 9.3r, 4.4r, 3.2r)).
consoleEx writeLine:(median:(4.1r, 7.2r, 1.7r, 9.3r, 4.4r, 3.2r)).
].

[edit] Erlang

-module(median).
-import(lists, [nth/2, sort/1]).
-compile(export_all).
 
median(Unsorted) ->
Sorted = sort(Unsorted),
Length = length(Sorted),
Mid = Length div 2,
Rem = Length rem 2,
(nth(Mid+Rem, Sorted) + nth(Mid+1, Sorted)) / 2.

[edit] Euler Math Toolbox

The following function does much more than computing the median. It can handle a matrix of x values row by row. Then it can handle multiplicities in the vector v. Moreover it can search for the p median, not only the p=0.5 median.

 
>type median
function median (x, v: none, p)
 
## Default for v : none
## Default for p : 0.5
 
m=rows(x);
if m>1 then
y=zeros(m,1);
loop 1 to m;
y[#]=median(x[#],v,p);
end;
return y;
else
if v<>none then
{xs,i}=sort(x); vsh=v[i];
n=cols(xs);
ns=sum(vsh);
i=1+p*(ns-1); i0=floor(i);
vs=cumsum(vsh);
loop 1 to n
if vs[#]>i0 then
return xs[#];
elseif vs[#]+1>i0 then
k=#+1;
repeat;
if vsh[k]>0 or k>n then break; endif;
k=k+1;
end;
return (1-(i-i0))*xs[#]+(i-i0)*xs[k]+0;
endif;
end;
return xs[n];
else
xs=sort(x);
n=cols(x);
i=1+p*(n-1); i0=floor(i);
if i0==n then return xs[n]; endif;
return (i-i0)*xs[i+1]+(1-(i-i0))*xs[i];
endif;
endif;
endfunction
>median(1:10)
5.5
>median(1:9)
5
>median(1:10,p=0.2)
2.8
>0.2*10+0.8*1
2.8
 

[edit] Euphoria

function median(sequence s)
atom min,k
-- Selection sort of half+1
for i = 1 to length(s)/2+1 do
min = s[i]
k = 0
for j = i+1 to length(s) do
if s[j] < min then
min = s[j]
k = j
end if
end for
if k then
s[k] = s[i]
s[i] = min
end if
end for
if remainder(length(s),2) = 0 then
return (s[$/2]+s[$/2+1])/2
else
return s[$/2+1]
end if
end function
 
? median({ 4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5 })

Output:

4.45

[edit] Excel

Assuming the values are entered in the A column, type into any cell which will not be part of the list :

 
=MEDIAN(A1:A10)
 

Assuming 10 values will be entered, alternatively, you can just type

 
=MEDIAN(
 

and then select the start and end cells, not necessarily in the same row or column.

The output for the first expression, for any 10 numbers is

 
23 11,5
21
12
3
19
7
23
11
9
0
 

[edit] F#

Median of Medians algorithm implementation

 
let rec splitToFives list =
match list with
| a::b::c::d::e::tail ->
([a;b;c;d;e])::(splitToFives tail)
| [] -> []
| _ ->
let left = 5 - List.length (list)
let last = List.append list (List.init left (fun _ -> System.Double.PositiveInfinity) )
in [last]
 
let medianFromFives =
List.map ( fun (i:float list) ->
List.nth (List.sort i) 2 )
 
let start l =
let rec magicFives list k =
if List.length(list) <= 10 then
List.nth (List.sort list) (k-1)
else
let s = splitToFives list
let M = medianFromFives s
let m = magicFives M (int(System.Math.Ceiling((float(List.length M))/2.)))
let (ll,lg) = List.partition ( fun i -> i < m ) list
let (le,lg) = List.partition ( fun i -> i = m ) lg
in
if (List.length ll >= k) then
magicFives ll k
else if (List.length ll + List.length le >= k ) then m
else
magicFives lg (k-(List.length ll)-(List.length le))
in
let len = List.length l in
if (len % 2 = 1) then
magicFives l ((len+1)/2)
else
let a = magicFives l (len/2)
let b = magicFives l ((len/2)+1)
in (a+b)/2.
 
 
let z = [1.;5.;2.;8.;7.;2.]
start z
let z' = [1.;5.;2.;8.;7.]
start z'

 

[edit] Factor

The quicksort-style solution, with random pivoting. Takes the lesser of the two medians for even sequences.

USING: arrays kernel locals math math.functions random sequences ;
IN: median
 
: pivot ( seq -- pivot ) random ;
 
: split ( seq pivot -- {lt,eq,gt} )
[ [ < ] curry partition ] keep
[ = ] curry partition
3array ;
 
DEFER: nth-in-order
:: nth-in-order-recur ( seq ind -- elt )
seq dup pivot split
dup [ length ] map 0 [ + ] accumulate nip
dup [ ind <= [ 1 ] [ 0 ] if ] map sum 1 -
[ swap nth ] curry bi@
ind swap -
nth-in-order ;
 
: nth-in-order ( seq ind -- elt )
dup 0 =
[ drop first ]
[ nth-in-order-recur ]
if ;
 
: median ( seq -- median )
dup length 1 - 2 / floor nth-in-order ;

Usage:

( scratchpad ) 11 iota median .
5
( scratchpad ) 10 iota median .
4

[edit] Forth

This uses the O(n) algorithm derived from quicksort.

-1 cells constant -cell
: cell- -cell + ;
 
defer lessthan ( a@ b@ -- ? ) ' < is lessthan
 
: mid ( l r -- mid ) over - 2/ -cell and + ;
 
: exch ( addr1 addr2 -- ) dup @ >r over @ swap ! r> swap ! ;
 
: part ( l r -- l r r2 l2 )
2dup mid @ >r ( r: pivot )
2dup begin
swap begin dup @ r@ lessthan while cell+ repeat
swap begin r@ over @ lessthan while cell- repeat
2dup <= if 2dup exch >r cell+ r> cell- then
2dup > until r> drop ;
 
0 value midpoint
 
: select ( l r -- )
begin 2dup < while
part
dup midpoint >= if nip nip ( l l2 ) else
over midpoint <= if drop rot drop swap ( r2 r ) else
2drop 2drop exit then then
repeat 2drop ;
 
: median ( array len -- m )
1- cells over + 2dup mid to midpoint
select midpoint @ ;
create test 4 , 2 , 1 , 3 , 5 ,
 
test 4 median . \ 2
test 5 median . \ 3

[edit] Fortran

Works with: Fortran version 90 and later
program Median_Test
 
real :: a(7) = (/ 4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2 /), &
b(6) = (/ 4.1, 7.2, 1.7, 9.3, 4.4, 3.2 /)
 
print *, median(a)
print *, median(b)
 
contains
 
function median(a, found)
real, dimension(:), intent(in) :: a
! the optional found argument can be used to check
! if the function returned a valid value; we need this
! just if we suspect our "vector" can be "empty"
logical, optional, intent(out) :: found
real :: median
 
integer :: l
real, dimension(size(a,1)) :: ac
 
if ( size(a,1) < 1 ) then
if ( present(found) ) found = .false.
else
ac = a
! this is not an intrinsic: peek a sort algo from
! Category:Sorting, fixing it to work with real if
! it uses integer instead.
call sort(ac)
 
l = size(a,1)
if ( mod(l, 2) == 0 ) then
median = (ac(l/2+1) + ac(l/2))/2.0
else
median = ac(l/2+1)
end if
 
if ( present(found) ) found = .true.
end if
 
end function median
 
end program Median_Test

[edit] GAP

Median := function(v) 
local n, w;
w := SortedList(v);
n := Length(v);
return (w[QuoInt(n + 1, 2)] + w[QuoInt(n, 2) + 1]) / 2;
end;
 
a := [41, 56, 72, 17, 93, 44, 32];
b := [41, 72, 17, 93, 44, 32];
 
Median(a);
# 44
Median(b);
# 85/2

[edit] Go

package main
 
import (
"fmt"
"sort"
)
 
func main() {
fmt.Println(median([]float64{3, 1, 4, 1})) // prints 2
fmt.Println(median([]float64{3, 1, 4, 1, 5})) // prints 3
}
 
func median(a []float64) float64 {
sort.Float64s(a)
half := len(a) / 2
m := a[half]
if len(a)%2 == 0 {
m = (m + a[half-1]) / 2
}
return m
}

[edit] Groovy

Solution (brute force sorting, with arithmetic averaging of dual midpoints (even sizes)):

def median(Iterable col) {
def s = col as SortedSet
if (s == null) return null
if (s.empty) return 0
def n = s.size()
def m = n.intdiv(2)
def l = s.collect { it }
n%2 == 1 ? l[m] : (l[m] + l[m-1])/2
}

Test:

def a = [4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5]
def sz = a.size()
 
(0..sz).each {
println """${median(a[0..<(sz-it)])} == median(${a[0..<(sz-it)]})
${median(a[it..<sz])} == median(${a[it..<sz]})"""

}

Output:

4.45 == median([4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5])
4.45 == median([4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5])
4.4 == median([4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3])
4.5 == median([2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5])
3.35 == median([4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2])
5.55 == median([-1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5])
2.3 == median([4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9])
6.6 == median([7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5])
3.35 == median([4.4, 2.3, -1.7, 7.5, 6.6, 0.0])
5.55 == median([6.6, 0.0, 1.9, 8.2, 9.3, 4.5])
4.4 == median([4.4, 2.3, -1.7, 7.5, 6.6])
4.5 == median([0.0, 1.9, 8.2, 9.3, 4.5])
3.35 == median([4.4, 2.3, -1.7, 7.5])
6.35 == median([1.9, 8.2, 9.3, 4.5])
2.3 == median([4.4, 2.3, -1.7])
8.2 == median([8.2, 9.3, 4.5])
3.35 == median([4.4, 2.3])
6.9 == median([9.3, 4.5])
4.4 == median([4.4])
4.5 == median([4.5])
0 == median([])
0 == median([])

[edit] Haskell

This uses a quick select algorithm and runs in expected O(n) time.

 
median xs | null xs = Nothing
| odd len = Just $ xs !! mid
| even len = Just $ meanMedian
where len = length xs
mid = len `div` 2
meanMedian = (xs !! mid + xs !! (mid+1)) / 2
median :: Fractional a => [a] -> Maybe a
 


Or
Library: hstats
> Math.Statistics.median [1,9,2,4]
3.0

[edit] HicEst

If the input has an even number of elements, median is the mean of the middle two values:

REAL :: n=10, vec(n)
 
vec = RAN(1)
SORT(Vector=vec, Sorted=vec) ! in-place Merge-Sort
 
IF( MOD(n,2) ) THEN ! odd n
median = vec( CEILING(n/2) )
ELSE
median = ( vec(n/2) + vec(n/2 + 1) ) / 2
ENDIF

[edit] Icon and Unicon

A quick and dirty solution:

procedure main(args)
write(median(args))
end
 
procedure median(A)
A := sort(A)
n := *A
return if n % 2 = 1 then A[n/2+1]
else (A[n/2]+A[n/2+1])/2.0 | 0 # 0 if empty list
end

Sample outputs:

->am 3 1 4 1 5 9 7 6 3
4
->am 3 1 4 1 5 9 7 6
4.5
->

[edit] J

The verb median is available from the stats/base addon and returns the mean of the two middle values for an even number of elements:

  require 'stats/base'
median 1 9 2 4
3

The definition given in the addon script is:

midpt=: -:@<:@#
median=: -:@(+/)@((<. , >.)@midpt { /:~)

If, for an even number of elements, both values were desired when those two values are distinct, then the following implementation would suffice:

   median=: ~.@(<. , >.)@midpt { /:~
median 1 9 2 4
2 4

[edit] Java

Works with: Java version 1.5+

Sorting:

// Note: this function modifies the input list
public static double median(List<Double> list){
Collections.sort(list);
return (list.get(list.size() / 2) + list.get((list.size() - 1) / 2)) / 2;
}
Works with: Java version 1.5+

Using priority queue (which sorts under the hood):

public static double median2(List<Double> list){
PriorityQueue<Double> pq = new PriorityQueue<Double>(list);
int n = list.size();
for (int i = 0; i < (n-1)/2; i++)
pq.poll(); // discard first half
if (n % 2 != 0) // odd length
return pq.poll();
else
return (pq.poll() + pq.poll()) / 2.0;
}

[edit] JavaScript

function median(ary) {
if (ary.length == 0)
return null;
ary.sort(function (a,b){return a - b})
var mid = Math.floor(ary.length / 2);
if ((ary.length % 2) == 1) // length is odd
return ary[mid];
else
return (ary[mid - 1] + ary[mid]) / 2;
}
 
median([]); // null
median([5,3,4]); // 4
median([5,4,2,3]); // 3.5
median([3,4,1,-8.4,7.2,4,1,1.2]); // 2.1

[edit] Julia

Julia has a built-in median() function

 
function median2(n)
s = sort(n)
len = length(n)
len%2 == 0 && return (s[ifloor(len/2)+1] + s[ifloor(len/2)])/2
return s[ifloor(len/2)+1]
end
a = [4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2]
b = [4.1, 7.2, 1.7, 9.3, 4.4, 3.2]
@assert median(a) == median2(a)
@assert median(b) == median2(b)

[edit] Lasso

can't use Lasso's built in median method because that takes 3 values, not an array of indeterminate length

Lasso's built in function is "median( value_1, value_2, value_3 )"

define median_ext(a::array) => {
#a->sort
 
if(#a->size % 2) => {
// odd numbered element array, pick middle
return #a->get(#a->size / 2 + 1)
 
else
// even number elements in array
return (#a->get(#a->size / 2) + #a->get(#a->size / 2 + 1)) / 2.0
}
}
 
median_ext(array(3,2,7,6)) // 4.5
median_ext(array(3,2,9,7,6)) // 6

[edit] Liberty BASIC

 
dim a( 100), b( 100) ' assumes we will not have vectors of more terms...
 
a$ ="4.1,5.6,7.2,1.7,9.3,4.4,3.2"
print "Median is "; median( a$) ' 4.4 7 terms
print
a$ ="4.1,7.2,1.7,9.3,4.4,3.2"
print "Median is "; median( a$) ' 4.25 6 terms
print
a$ ="4.1,4,1.2,6.235,7868.33" ' 4.1
print "Median of "; a$; " is "; median( a$)
print
a$ ="1,5,3,2,4" ' 3
print "Median of "; a$; " is "; median( a$)
print
a$ ="1,5,3,6,4,2" ' 3.5
print "Median of "; a$; " is "; median( a$)
print
a$ ="4.4,2.3,-1.7,7.5,6.6,0.0,1.9,8.2,9.3,4.5" ' 4.45
print "Median of "; a$; " is "; median( a$)
 
end
 
function median( a$)
i =1
do
v$ =word$( a$, i, ",")
if v$ ="" then exit do
print v$,
a( i) =val( v$)
i =i +1
loop until 0
print
 
sort a(), 1, i -1
 
for j =1 to i -1
print a( j),
next j
print
 
middle =( i -1) /2
intmiddle =int( middle)
if middle <>intmiddle then median= a( 1 +intmiddle) else median =( a( intmiddle) +a( intmiddle +1)) /2
end function
 
 4.1 5.6 7.2 1.7 9.3 4.4 3.2
Median is 4.4

4.1 7.2 1.7 9.3 4.4 3.2
Median is 4.25

4.1 4 1.2 6.235 7868.33
Median of 4.1,4,1.2,6.235,7868.33 is 4.1

1 5 3 2 4
Median of 1,5,3,2,4 is 3

1 5 3 6 4 2
Median of 1,5,3,6,4,2 is 3.5

4.4 2.3 -1.7 7.5 6.6 0.0 1.9 8.2 9.3 4.5
Median of 4.4,2.3,-1.7,7.5,6.6,0.0,1.9,8.2,9.3,4.5 is 4.45

[edit] LSL

integer MAX_ELEMENTS = 10;
integer MAX_VALUE = 100;
default {
state_entry() {
list lst = [];
integer x = 0;
for(x=0 ; x<MAX_ELEMENTS ; x++) {
lst += llFrand(MAX_VALUE);
}
llOwnerSay("lst=["+llList2CSV(lst)+"]");
llOwnerSay("Geometric Mean: "+(string)llListStatistics(LIST_STAT_GEOMETRIC_MEAN, lst));
llOwnerSay(" Max: "+(string)llListStatistics(LIST_STAT_MAX, lst));
llOwnerSay(" Mean: "+(string)llListStatistics(LIST_STAT_MEAN, lst));
llOwnerSay(" Median: "+(string)llListStatistics(LIST_STAT_MEDIAN, lst));
llOwnerSay(" Min: "+(string)llListStatistics(LIST_STAT_MIN, lst));
llOwnerSay(" Num Count: "+(string)llListStatistics(LIST_STAT_NUM_COUNT, lst));
llOwnerSay(" Range: "+(string)llListStatistics(LIST_STAT_RANGE, lst));
llOwnerSay(" Std Dev: "+(string)llListStatistics(LIST_STAT_STD_DEV, lst));
llOwnerSay(" Sum: "+(string)llListStatistics(LIST_STAT_SUM, lst));
llOwnerSay(" Sum Squares: "+(string)llListStatistics(LIST_STAT_SUM_SQUARES, lst));
}
}

Output:

lst=[23.815209, 85.890704, 10.811144, 31.522696, 54.619416, 12.211729, 42.964463, 87.367889, 7.106129, 18.711078]
Geometric Mean:    27.325070
           Max:    87.367889
          Mean:    37.502046
        Median:    27.668953
           Min:     7.106129
     Num Count:    10.000000
         Range:    80.261761
       Std Dev:    29.819840
           Sum:   375.020458
   Sum Squares: 22067.040048

[edit] Lua

function median (numlist)
if type(numlist) ~= 'table' then return numlist end
table.sort(numlist)
if #numlist %2 == 0 then return (numlist[#numlist/2] + numlist[#numlist/2+1]) / 2 end
return numlist[math.ceil(#numlist/2)]
end
 
print(median({4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2}))
print(median({4.1, 7.2, 1.7, 9.3, 4.4, 3.2}))

[edit] Maple

[edit] Builtin

This works for numeric lists or arrays, and is designed for large data sets.

 
> Statistics:-Median( [ 1, 5, 3, 2, 4 ] );
3.
 
> Statistics:-Median( [ 1, 5, 3, 6, 2, 4 ] );
3.50000000000000
 

[edit] Using a sort

This solution can handle exact numeric inputs. Instead of inputting a container of some kind, it simply finds the median of its arguments.

 
median1 := proc()
local L := sort( [ args ] );
( L[ iquo( 1 + nargs, 2 ) ] + L[ 1 + iquo( nargs, 2 ) ] ) / 2
end proc:
 

For example:

 
> median1( 1, 5, 3, 2, 4 ); # 3
3
 
> median1( 1, 5, 3, 6, 4, 2 ); # 7/2
7/2
 

[edit] Mathematica

Built-in function:

Median[{1, 5, 3, 2, 4}]
Median[{1, 5, 3, 6, 4, 2}]
Output:
3
7/2

Custom function:

mymedian[x_List]:=Module[{t=Sort[x],L=Length[x]},
If[Mod[L,2]==0,
(t[[L/2]]+t[[L/2+1]])/2
,
t[[(L+1)/2]]
]
]

Example of custom function:

mymedian[{1, 5, 3, 2, 4}]
mymedian[{1, 5, 3, 6, 4, 2}]
Output:
3
7/2

[edit] MATLAB

If the input has an even number of elements, function returns the mean of the middle two values:

function medianValue = findmedian(setOfValues)    
medianValue = median(setOfValues);
end

[edit] Maxima

/* built-in */
median([41, 56, 72, 17, 93, 44, 32]); /* 44 */
median([41, 72, 17, 93, 44, 32]); /* 85/2 */

[edit] MUMPS

MEDIAN(X)
 ;X is assumed to be a list of numbers separated by "^"
 ;I is a loop index
 ;L is the length of X
 ;Y is a new array
QUIT:'$DATA(X) "No data"
QUIT:X="" "Empty Set"
NEW I,ODD,L,Y
SET L=$LENGTH(X,"^"),ODD=L#2,I=1
 ;The values in the vector are used as indices for a new array Y, which sorts them
FOR QUIT:I>L SET Y($PIECE(X,"^",I))=1,I=I+1
 ;Go to the median index, or the lesser of the middle if there is an even number of elements
SET J="" FOR I=1:1:$SELECT(ODD:L\2+1,'ODD:L/2) SET J=$ORDER(Y(J))
QUIT $SELECT(ODD:J,'ODD:(J+$ORDER(Y(J)))/2)
 
USER>W $$MEDIAN^ROSETTA("-1.3^2.43^3.14^17^2E-3")
3.14
USER>W $$MEDIAN^ROSETTA("-1.3^2.43^3.14^17^2E-3^4")
3.57
USER>W $$MEDIAN^ROSETTA("")
Empty Set
USER>W $$MEDIAN^ROSETTA
No data

[edit] NetRexx

Translation of: Java
/* NetRexx */
options replace format comments java crossref symbols nobinary
 
class RAvgMedian00 public
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method median(lvector = java.util.List) public static returns Rexx
cvector = ArrayList(lvector) -- make a copy of input to ensure it's contents are preserved
Collections.sort(cvector, RAvgMedian00.RexxComparator())
kVal = ((Rexx cvector.get(cvector.size() % 2)) + (Rexx cvector.get((cvector.size() - 1) % 2))) / 2
return kVal
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method median(rvector = Rexx[]) public static returns Rexx
return median(ArrayList(Arrays.asList(rvector)))
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method show_median(lvector = java.util.List) public static returns Rexx
mVal = median(lvector)
say 'Meadian:' mVal.format(10, 6, 3, 6, 's')', Vector:' (Rexx lvector).space(0)
return mVal
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method show_median(rvector = Rexx[]) public static returns Rexx
return show_median(ArrayList(Arrays.asList(rvector)))
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method run_samples() public static
show_median([Rexx 10.0]) -- 10.0
show_median([Rexx 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0]) -- 5.5
show_median([Rexx 9, 8, 7, 6, 5, 4, 3, 2, 1]) -- 5.0
show_median([Rexx 1.0, 9, 2.0, 4.0]) -- 3.0
show_median([Rexx 3.0, 1, 4, 1.0, 5.0, 9, 7.0, 6.0]) -- 4.5
show_median([Rexx 3, 4, 1, -8.4, 7.2, 4, 1, 1.2]) -- 2.1
show_median([Rexx -1.2345678e+99, 2.3e+700]) -- 1.15e+700
show_median([Rexx 4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2]) -- 4.4
show_median([Rexx 4.1, 7.2, 1.7, 9.3, 4.4, 3.2]) -- 4.25
show_median([Rexx 28.207, 74.916, 51.695, 72.486, 51.118, 3.241, 73.807]) -- 51.695
show_median([Rexx 27.984, 89.172, 0.250, 66.316, 41.805, 60.043]) -- 50.924
show_median([Rexx 5.1, 2.6, 6.2, 8.8, 4.6, 4.1]) -- 4.85
show_median([Rexx 5.1, 2.6, 8.8, 4.6, 4.1]) -- 4.6
show_median([Rexx 4.4, 2.3, -1.7, 7.5, 6.6, 0.0, 1.9, 8.2, 9.3, 4.5]) -- 4.45
show_median([Rexx 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0.11]) -- 3.0
show_median([Rexx 10, 20, 30, 40, 50, -100, 4.7, -11e+2]) -- 15.0
show_median([Rexx 9.3, -2.0, 4.0, 7.3, 8.1, 4.1, -6.3, 4.2, -1.0, -8.4]) -- 4.05
show_median([Rexx 8.3, -3.6, 5.7, 2.3, 9.3, 5.4, -2.3, 6.3, 9.9]) -- 5.7
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method main(args = String[]) public static
run_samples()
return
 
-- =============================================================================
class RAvgMedian00.RexxComparator implements Comparator
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method compare(i1=Object, i2=Object) public returns int
i = Rexx i1
j = Rexx i2
 
if i < j then return -1
if i > j then return +1
else return 0
 

Output:

Meadian:         10.000000     , Vector: [10.0]
Meadian:          5.500000     , Vector: [10.0,9.0,8.0,7.0,6.0,5.0,4.0,3.0,2.0,1.0]
Meadian:          5.000000     , Vector: [9,8,7,6,5,4,3,2,1]
Meadian:          3.000000     , Vector: [1.0,9,2.0,4.0]
Meadian:          4.500000     , Vector: [3.0,1,4,1.0,5.0,9,7.0,6.0]
Meadian:          2.100000     , Vector: [3,4,1,-8.4,7.2,4,1,1.2]
Meadian:          1.150000E+700, Vector: [-1.2345678E+99,2.3e+700]
Meadian:          4.400000     , Vector: [4.1,5.6,7.2,1.7,9.3,4.4,3.2]
Meadian:          4.250000     , Vector: [4.1,7.2,1.7,9.3,4.4,3.2]
Meadian:         51.695000     , Vector: [28.207,74.916,51.695,72.486,51.118,3.241,73.807]
Meadian:         50.924000     , Vector: [27.984,89.172,0.250,66.316,41.805,60.043]
Meadian:          4.850000     , Vector: [5.1,2.6,6.2,8.8,4.6,4.1]
Meadian:          4.600000     , Vector: [5.1,2.6,8.8,4.6,4.1]
Meadian:          4.450000     , Vector: [4.4,2.3,-1.7,7.5,6.6,0.0,1.9,8.2,9.3,4.5]
Meadian:          3.000000     , Vector: [10,9,8,7,6,5,4,3,2,1,0,0,0,0,0.11]
Meadian:         15.000000     , Vector: [10,20,30,40,50,-100,4.7,-1100]
Meadian:          4.050000     , Vector: [9.3,-2.0,4.0,7.3,8.1,4.1,-6.3,4.2,-1.0,-8.4]
Meadian:          5.700000     , Vector: [8.3,-3.6,5.7,2.3,9.3,5.4,-2.3,6.3,9.9]

[edit] NewLISP

; median.lsp
; oofoe 2012-01-25
 
(define (median lst)
(sort lst) ; Sorts in place.
(if (empty? lst)
nil
(letn ((n (length lst))
(h (/ (- n 1) 2)))
(if (zero? (mod n 2))
(div (add (lst h) (lst (+ h 1))) 2)
(lst h))
)))
 
 
(define (test lst) (println lst " -> " (median lst)))
 
(test '())
(test '(5 3 4))
(test '(5 4 2 3))
(test '(3 4 1 -8.4 7.2 4 1 1.2))
 
(exit)

Sample output:

() -> nil
(5 3 4) -> 4
(5 4 2 3) -> 3.5
(3 4 1 -8.4 7.2 4 1 1.2) -> 2.1

[edit] Nimrod

Translation of: Python
import algorithm, strutils
 
proc median(xs): float =
var ys = xs
sort(ys, system.cmp[float])
0.5 * (ys[ys.high div 2] + ys[ys.len div 2])
 
var a = @[4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2]
echo formatFloat(median(a), precision = 0)
a = @[4.1, 7.2, 1.7, 9.3, 4.4, 3.2]
echo formatFloat(median(a), precision = 0)

[edit] Oberon-2

Oxford Oberon-2

 
MODULE Median;
IMPORT Out;
CONST
MAXSIZE = 100;
 
PROCEDURE Partition(VAR a: ARRAY OF REAL; left, right: INTEGER): INTEGER;
VAR
pValue,aux: REAL;
store,i,pivot: INTEGER;
BEGIN
pivot := right;
pValue := a[pivot];
aux := a[right];a[right] := a[pivot];a[pivot] := aux; (* a[pivot] <-> a[right] *)
store := left;
FOR i := left TO right -1 DO
IF a[i] <= pValue THEN
aux := a[store];a[store] := a[i];a[i]:=aux;
INC(store)
END
END;
aux := a[right];a[right] := a[store]; a[store] := aux;
RETURN store
END Partition;
 
(* QuickSelect algorithm *)
PROCEDURE Select(a: ARRAY OF REAL; left,right,k: INTEGER;VAR r: REAL);
VAR
pIndex, pDist : INTEGER;
BEGIN
IF left = right THEN r := a[left]; RETURN END;
pIndex := Partition(a,left,right);
pDist := pIndex - left + 1;
IF pDist = k THEN
r := a[pIndex];RETURN
ELSIF k < pDist THEN
Select(a,left, pIndex - 1, k, r)
ELSE
Select(a,pIndex + 1, right, k - pDist, r)
END
END Select;
 
PROCEDURE Median(a: ARRAY OF REAL;left,right: INTEGER): REAL;
VAR
idx,len : INTEGER;
r1,r2 : REAL;
BEGIN
len := right - left + 1;
idx := len DIV 2 + 1;
r1 := 0.0;r2 := 0.0;
Select(a,left,right,idx,r1);
IF ODD(len) THEN RETURN r1 END;
Select(a,left,right,idx - 1,r2);
RETURN (r1 + r2) / 2;
END Median;
 
 
VAR
ary: ARRAY MAXSIZE OF REAL;
r: REAL;
BEGIN
r := 0.0;
Out.Fixed(Median(ary,0,0),4,2);Out.Ln; (* empty *)
ary[0] := 5;
ary[1] := 3;
ary[2] := 4;
Out.Fixed(Median(ary,0,2),4,2);Out.Ln;
ary[0] := 5;
ary[1] := 4;
ary[2] := 2;
ary[3] := 3;
Out.Fixed(Median(ary,0,3),4,2);Out.Ln;
ary[0] := 3;
ary[1] := 4;
ary[2] := 1;
ary[3] := -8.4;
ary[4] := 7.2;
ary[5] := 4;
ary[6] := 1;
ary[7] := 1.2;
Out.Fixed(Median(ary,0,7),4,2);Out.Ln;
END Median.
 

Output:

0.00
4.00
3.50
2.10

[edit] Objeck

 
use Structure;
 
bundle Default {
class Median {
function : Main(args : String[]) ~ Nil {
numbers := FloatVector->New([4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2]);
DoMedian(numbers)->PrintLine();
 
numbers := FloatVector->New([4.1, 7.2, 1.7, 9.3, 4.4, 3.2]);
DoMedian(numbers)->PrintLine();
}
 
function : native : DoMedian(numbers : FloatVector) ~ Float {
if(numbers->Size() = 0) {
return 0.0;
}
else if(numbers->Size() = 1) {
return numbers->Get(0);
};
 
numbers->Sort();
 
i := numbers->Size() / 2;
if(numbers->Size() % 2 = 0) {
return (numbers->Get(i - 1) + numbers->Get(i)) / 2.0;
};
 
return numbers->Get(i);
}
}
}
 

[edit] OCaml

(* note: this modifies the input array *)
let median array =
let len = Array.length array in
Array.sort compare array;
(array.((len-1)/2) +. array.(len/2)) /. 2.0;;
 
let a = [|4.1; 5.6; 7.2; 1.7; 9.3; 4.4; 3.2|];;
median a;;
let a = [|4.1; 7.2; 1.7; 9.3; 4.4; 3.2|];;
median a;;

[edit] Octave

Of course Octave has its own median function we can use to check our implementation. The Octave's median function, however, does not handle the case you pass in a void vector.

function y = median2(v)
if (numel(v) < 1)
y = NA;
else
sv = sort(v);
l = numel(v);
if ( mod(l, 2) == 0 )
y = (sv(floor(l/2)+1) + sv(floor(l/2)))/2;
else
y = sv(floor(l/2)+1);
endif
endif
endfunction
 
a = [4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2];
b = [4.1, 7.2, 1.7, 9.3, 4.4, 3.2];
 
disp(median2(a)) % 4.4
disp(median(a))
disp(median2(b)) % 4.25
disp(median(b))

[edit] ooRexx

 
call testMedian .array~of(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
call testMedian .array~of(10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, .11)
call testMedian .array~of(10, 20, 30, 40, 50, -100, 4.7, -11e2)
call testMedian .array~new
 
::routine testMedian
use arg numbers
say "numbers =" numbers~toString("l", ", ")
say "median =" median(numbers)
say
 
::routine median
use arg numbers
 
if numbers~isempty then return 0
-- make a copy so the sort does not alter the
-- original set. This also means this will
-- work with lists and queues as well
numbers = numbers~makearray
 
-- sort and return the middle element
numbers~sortWith(.numbercomparator~new)
size = numbers~items
-- this handles the odd value too
return numbers[size%2 + size//2]
 
 
-- a custom comparator that sorts strings as numeric values rather than
-- strings
::class numberComparator subclass comparator
::method compare
use strict arg left, right
-- perform the comparison on the names. By subtracting
-- the two and returning the sign, we give the expected
-- results for the compares
return (left - right)~sign
 

[edit] Oz

declare
fun {Median Xs}
Len = {Length Xs}
Mid = Len div 2 + 1 %% 1-based index
Sorted = {Sort Xs Value.'<'}
in
if {IsOdd Len} then {Nth Sorted Mid}
else ({Nth Sorted Mid} + {Nth Sorted Mid-1}) / 2.0
end
end
in
{Show {Median [4.1 5.6 7.2 1.7 9.3 4.4 3.2]}}
{Show {Median [4.1 7.2 1.7 9.3 4.4 3.2]}}

[edit] PARI/GP

Sorting solution.

median(v)={
vecsort(v)[#v\2]
};

Linear-time solution, mostly proof-of-concept but perhaps suitable for large lists.

BFPRT(v,k=#v\2)={
if(#v<15, return(vecsort(v)[k]));
my(u=List(),pivot,left=List(),right=List());
forstep(i=1,#v-4,5,
listput(u,BFPRT([v[i],v[i+1],v[i+2],v[i+3],v[i+4]]))
);
pivot=BFPRT(Vec(u));
u=0;
for(i=1,#v,
if(v[i]<pivot,
listput(left,v[i])
,
listput(right,v[i])
)
);
if(k>#left,
BFPRT(right, k-#left)
,
BFPRT(left, k)
)
};

[edit] Pascal

Works with: Free_Pascal
Program AveragesMedian(output);
 
type
TDoubleArray = array of double;
 
procedure bubbleSort(var list: TDoubleArray);
var
i, j, n: integer;
t: double;
begin
n := length(list);
for i := n downto 2 do
for j := 0 to i - 1 do
if list[j] > list[j + 1] then
begin
t := list[j];
list[j] := list[j + 1];
list[j + 1] := t;
end;
end;
 
function Median(aArray: TDoubleArray): double;
var
lMiddleIndex: integer;
begin
bubbleSort(aArray);
lMiddleIndex := (high(aArray) - low(aArray)) div 2;
if Odd(Length(aArray)) then
Median := aArray[lMiddleIndex + 1]
else
Median := (aArray[lMiddleIndex + 1] + aArray[lMiddleIndex]) / 2;
end;
 
var
A: TDoubleArray;
i: integer;
 
begin
randomize;
setlength(A, 7);
for i := low(A) to high(A) do
begin
A[i] := 100 * random;
write (A[i]:7:3, ' ');
end;
writeln;
writeln('Median: ', Median(A):7:3);
 
setlength(A, 6);
for i := low(A) to high(A) do
begin
A[i] := 100 * random;
write (A[i]:7:3, ' ');
end;
writeln;
writeln('Median: ', Median(A):7:3);
end.

Output:

% ./Median
 28.207  74.916  51.695  72.486  51.118   3.241  73.807 
Median:  51.695
 27.984  89.172   0.250  66.316  41.805  60.043 
Median:  50.924

[edit] Perl

Translation of: Python
sub median {
my @a = sort {$a <=> $b} @_;
return ($a[$#a/2] + $a[@a/2]) / 2;
}

[edit] Perl 6

Works with: Rakudo version #22 "Thousand Oaks"
sub median {
my @a = sort @_;
return (@a[@a.end / 2] + @a[@a / 2]) / 2;
}

In a slightly more compact way:

sub median { 2 R/ [+] @_.sort[@_.end / 2, @_ / 2] }

[edit] PHP

This solution uses the sorting method of finding the median.

 
function median($arr)
{
sort($arr);
$count = count($arr); //count the number of values in array
$middleval = floor(($count-1)/2); // find the middle value, or the lowest middle value
if ($count % 2) { // odd number, middle is the median
$median = $arr[$middleval];
} else { // even number, calculate avg of 2 medians
$low = $arr[$middleval];
$high = $arr[$middleval+1];
$median = (($low+$high)/2);
}
return $median;
}
 
echo median(array(4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2)) . "\n"; // 4.4
echo median(array(4.1, 7.2, 1.7, 9.3, 4.4, 3.2)) . "\n"; // 4.25
 

[edit] PicoLisp

(de median (Lst)
(let N (length Lst)
(if (bit? 1 N)
(get (sort Lst) (/ (inc N) 2))
(setq Lst (nth (sort Lst) (/ N 2)))
(/ (+ (car Lst) (cadr Lst)) 2) ) ) )
 
(scl 2)
(prinl (round (median (1.0 2.0 3.0))))
(prinl (round (median (1.0 2.0 3.0 4.0))))
(prinl (round (median (5.1 2.6 6.2 8.8 4.6 4.1))))
(prinl (round (median (5.1 2.6 8.8 4.6 4.1))))

Output:

2.00
2.50
4.85
4.60

[edit] PL/I

call sort(A);
n = dimension(A,1);
if iand(n,1) = 1 then /* an odd number of elements */
median = A(n/2);
else /* an even number of elements */
median = (a(n/2) + a(trunc(n/2)+1) )/2;

[edit] Prolog

median(L, Z) :-
length(L, Length),
I is Length div 2,
Rem is Length rem 2,
msort(L, S),
maplist(sumlist, [[I, Rem], [I, 1]], Mid),
maplist(nth1, Mid, [S, S], X),
sumlist(X, Y),
Z is Y/2.

[edit] Pure

Inspired by the Haskell version.

median x = (/(2-rem)) $ foldl1 (+) $ take (2-rem) $ drop (mid-(1-rem)) $ sort (<=) x
when len = # x;
mid = len div 2;
rem = len mod 2;
end;
Output:
> median [1, 3, 5];
3.0
> median [1, 2, 3, 4];
2.5

[edit] PureBasic

Procedure.d median(Array values.d(1), length.i)
If length = 0 : ProcedureReturn 0.0 : EndIf
SortArray(values(), #PB_Sort_Ascending)
If length % 2
ProcedureReturn values(length / 2)
EndIf
ProcedureReturn 0.5 * (values(length / 2 - 1) + values(length / 2))
EndProcedure
 
Procedure.i readArray(Array values.d(1))
Protected length.i, i.i
Read.i length
ReDim values(length - 1)
For i = 0 To length - 1
Read.d values(i)
Next
ProcedureReturn i
EndProcedure
 
Dim floats.d(0)
Restore array1
length.i = readArray(floats())
Debug median(floats(), length)
Restore array2
length.i = readArray(floats())
Debug median(floats(), length)
 
DataSection
array1:
Data.i 7
Data.d 4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2
array2:
Data.i 6
Data.d 4.1, 7.2, 1.7, 9.3, 4.4, 3.2
EndDataSection

[edit] Python

def median(aray):
srtd = sorted(aray)
alen = len(srtd)
return 0.5*( srtd[(alen-1)//2] + srtd[alen//2])
 
a = (4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2)
print a, median(a)
a = (4.1, 7.2, 1.7, 9.3, 4.4, 3.2)
print a, median(a)

[edit] R

R has its built-in median function.

Translation of: Octave
omedian <- function(v) {
if ( length(v) < 1 )
NA
else {
sv <- sort(v)
l <- length(sv)
if ( l %% 2 == 0 )
(sv[floor(l/2)+1] + sv[floor(l/2)])/2
else
sv[floor(l/2)+1]
}
}
 
a <- c(4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2)
b <- c(4.1, 7.2, 1.7, 9.3, 4.4, 3.2)
 
print(median(a)) # 4.4
print(omedian(a))
print(median(b)) # 4.25
print(omedian(b))

[edit] Racket

#lang racket
(define (median numbers)
(define sorted (list->vector (sort (vector->list numbers) <)))
(define count (vector-length numbers))
(if (zero? count)
#f
(/ (+ (vector-ref sorted (floor (/ (sub1 count) 2)))
(vector-ref sorted (floor (/ count 2))))
2)))
 
(median '#(5 3 4)) ;; 4
(median '#()) ;; #f
(median '#(5 4 2 3)) ;; 7/2
(median '#(3 4 1 -8.4 7.2 4 1 1.2)) ;; 2.1

[edit] REBOL

 
median: func [
"Returns the midpoint value in a series of numbers; half the values are above, half are below."
block [any-block!]
/local len mid
][
if empty? block [return none]
block: sort copy block
len: length? block
mid: to integer! len / 2
either odd? len [
pick block add 1 mid
][
(block/:mid) + (pick block add 1 mid) / 2
]
]
 


[edit] REXX

/*REXX program finds the  median  of a vector (& displays vector,median)*/
 
/*────────vector────────── ───show vector─── ───────show result─────────*/
v='1 9 2 4'  ; say 'vector=' v; say 'median=' median(v); say
v='3 1 4 1 5 9 7 6'  ; say 'vector= 'v; say 'median=' median(v); say
v='3 4 1 -8.4 7.2 4 1 1.2'; say 'vector= 'v; say 'median=' median(v); say
v='-1.2345678e99 2.3e+700'; say 'vector= 'v; say 'median=' median(v); say
 
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────MEDIAN subroutine───────────────────*/
median: procedure; parse arg x
call makeArray x /*make into scalar array (faster)*/
call Esort /*(ESORT is an overkill for this)*/
m=@.0%2 /*  % is REXX integer division.*/
n=m+1
if @.0//2==1 then return @.n /*(odd?) // is REXX modulus.*/
return (@.m+@.n)/2 /*process an even-element vector.*/
/*──────────────────────────────────MAKEARRAY subroutine────────────────*/
makeArray: procedure expose @.; parse arg v; @.0=words(v) /*make array*/
do j=1 for @.0; @.j=word(v,j); end /*j*/
return
/*──────────────────────────────────ESORT subroutine────────────────────*/
Esort: procedure expose @.; h=@.0 /*@.0 = # entries.*/
do while h>1; h=h%2 /*cut entries by ½.*/
do i=1 for @.0-h; j=i; k=h+i
do while @.k<@.j
parse value @.j @.k with @.k @.j /*swap two values. */
if h>=j then leave
j=j-h; k=k-h
end /*while @.k<@.j*/
end /*i*/
end /*while h>l*/
return /*exchange sort is finished.*/

output

vector= 1 9 2 4
medium= 3

vector= 3 1 4 1 5 9 7 6
medium= 4.5

vector= 3 4 1 -8.4 7.2 4 1 1.2
medium= 2.1

vector= -1.2345678e99 2.3e+700
medium= 1.15000000E+700

[edit] Ruby

def median(ary)
return nil if ary.empty?
mid, rem = ary.length.divmod(2)
if rem == 0
ary.sort[mid-1,2].inject(:+) / 2.0
else
ary.sort[mid]
end
end
 
p median([]) # => nil
p median([5,3,4]) # => 4
p median([5,4,2,3]) # => 3.5
p median([3,4,1,-8.4,7.2,4,1,1.2]) # => 2.1

Alternately:

def median(aray)
srtd = aray.sort
alen = srtd.length
(srtd[(alen-1)/2] + srtd[alen/2]) / 2.0
end

[edit] Scala

Works with: Scala version 2.8
(See the Scala discussion on Mean for more information.)
def median[T](s: Seq[T])(implicit n: Fractional[T]) = {
import n._
val (lower, upper) = s.sortWith(_<_).splitAt(s.size / 2)
if (s.size % 2 == 0) (lower.last + upper.head) / fromInt(2) else upper.head
}

This isn't really optimal. The methods splitAt and last are O(n/2) on many sequences, and then there's the lower bound imposed by the sort. Finally, we call size two times, and it can be O(n).

[edit] Scheme

Translation of: Python

Using Rosetta Code's bubble-sort function

(define (median l)
(* (+ (list-ref (bubble-sort l >) (round (/ (- (length l) 1) 2)))
(list-ref (bubble-sort l >) (round (/ (length l) 2)))) 0.5))

Using SRFI-95:

(define (median l)
(* (+ (list-ref (sort l less?) (round (/ (- (length l) 1) 2)))
(list-ref (sort l less?) (round (/ (length l) 2)))) 0.5))

[edit] Seed7

$ include "seed7_05.s7i";
include "float.s7i";
 
const type: floatList is array float;
 
const func float: median (in floatList: floats) is func
result
var float: median is 0.0;
local
var floatList: sortedFloats is 0 times 0.0;
begin
sortedFloats := sort(floats);
if odd(length(sortedFloats)) then
median := sortedFloats[succ(length(sortedFloats)) div 2];
else
median := 0.5 * (sortedFloats[length(sortedFloats) div 2] +
sortedFloats[succ(length(sortedFloats) div 2)]);
end if;
end func;
 
const proc: main is func
local
const floatList: flist1 is [] (5.1, 2.6, 6.2, 8.8, 4.6, 4.1);
const floatList: flist2 is [] (5.1, 2.6, 8.8, 4.6, 4.1);
begin
writeln("flist1 median is " <& median(flist1) digits 2 lpad 7); # 4.85
writeln("flist2 median is " <& median(flist2) digits 2 lpad 7); # 4.60
end func;

[edit] Slate

s@(Sequence traits) median
[
s isEmpty
ifTrue: [Nil]
ifFalse:
[| sorted |
sorted: s sort.
sorted length `cache isEven
ifTrue: [(sorted middle + (sorted at: sorted indexMiddle - 1)) / 2]
ifFalse: [sorted middle]]
].
inform: { 4.1 . 5.6 . 7.2 . 1.7 . 9.3 . 4.4 . 3.2 } median.
inform: { 4.1 . 7.2 . 1.7 . 9.3 . 4.4 . 3.2 } median.

[edit] Smalltalk

Works with: GNU Smalltalk
OrderedCollection extend [
median [
self size = 0
ifFalse: [ |s l|
l := self size.
s := self asSortedCollection.
(l rem: 2) = 0
ifTrue: [ ^ ((s at: (l//2 + 1)) + (s at: (l//2))) / 2 ]
ifFalse: [ ^ s at: (l//2 + 1) ]
]
ifTrue: [ ^nil ]
]
].
{ 4.1 . 5.6 . 7.2 . 1.7 . 9.3 . 4.4 . 3.2 } asOrderedCollection
median displayNl.
{ 4.1 . 7.2 . 1.7 . 9.3 . 4.4 . 3.2 } asOrderedCollection
median displayNl.

[edit] Tcl

proc median args {
set list [lsort -real $args]
set len [llength $list]
# Odd number of elements
if {$len & 1} {
return [lindex $list [expr {($len-1)/2}]]
}
# Even number of elements
set idx2 [expr {$len/2}]
set idx1 [expr {$idx2-1}]
return [expr {
([lindex $list $idx1] + [lindex $list $idx2])/2.0
}]
}
 
puts [median 3.0 4.0 1.0 -8.4 7.2 4.0 1.0 1.2]; # --> 2.1

[edit] TI-83 BASIC

Using the built-in function:

median({1.1, 2.5, 0.3241})



[edit] TI-89 BASIC

median({3, 4, 1, -8.4, 7.2, 4, 1, 1})

[edit] Ursala

the simple way (sort first and then look in the middle)

#import std
#import flo
 
median = fleq-<; @K30K31X eql?\~&rh div\2.+ plus@lzPrhPX

test program, once with an odd length and once with an even length vector

#cast %eW
 
examples =
 
median~~ (
<9.3,-2.0,4.0,7.3,8.1,4.1,-6.3,4.2,-1.0,-8.4>,
<8.3,-3.6,5.7,2.3,9.3,5.4,-2.3,6.3,9.9>)

output:

(4.050000e+00,5.700000e+00)

[edit] Vala

Requires --pkg posix -X -lm compilation flags in order to use POSIX qsort, and to have access to math library.

int compare_numbers(void* a_ref, void* b_ref) {
double a = *(double*) a_ref;
double b = *(double*) b_ref;
return a > b ? 1 : a < b ? -1 : 0;
}
 
double median(double[] elements) {
double[] clone = elements;
Posix.qsort(clone, clone.length, sizeof(double), compare_numbers);
double middle = clone.length / 2.0;
int first = (int) Math.floor(middle);
int second = (int) Math.ceil(middle);
return (clone[first] + clone[second]) / 2;
}
void main() {
double[] array1 = {2, 4, 6, 1, 7, 3, 5};
double[] array2 = {2, 4, 6, 1, 7, 3, 5, 8};
print(@"$(median(array1)) $(median(array2))\n");
}

[edit] Vedit macro language

This is a simple implementation for positive integers using sorting. The data is stored in current edit buffer in ascii representation. The values must be right justified.

The result is returned in text register @10. In case of even number of items, the lower middle value is returned.

Sort(0, File_Size, NOCOLLATE+NORESTORE)
EOF Goto_Line(Cur_Line/2)
Reg_Copy(10, 1)

[edit] Wortel

@let {
 ; iterative
med1 &l @let {a @sort l s #a i @/s 2 ?{%%s 2 ~/ 2 +`-i 1 a `i a `i a}}
 
 ; tacit
med2 ^(\~/2 @sum @(^(\&![#~f #~c] \~/2 \~-1 #) @` @id) @sort)
 
[[
 !med1 [4 2 5 2 1]
 !med1 [4 5 2 1]
 !med2 [4 2 5 2 1]
 !med2 [4 5 2 1]
]]
}
Returns:
[2 3 2 3]

[edit] zkl

Using the Quickselect algorithm#zkl for O(n) time:

var quickSelect=Import("quickSelect").qselect;
 
fcn median(xs){
n:=xs.len();
if (n.isOdd) return(quickSelect(xs,n/2));
( quickSelect(xs,n/2-1) + quickSelect(xs,n/2) )/2;
}
median(T( 5.1, 2.6, 6.2, 8.8, 4.6, 4.1 )); //-->4.85
median(T( 5.1, 2.6, 8.8, 4.6, 4.1 )); //-->4.6
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox