Averages/Median: Difference between revisions

[[Category:Sorting]]

Write a program to find the   [[wp:Median|median]]   value of a vector of floating-point numbers.

=={{header|11l}}==

{{trans|Python}}

V srtd = sorted(aray)

V alen = srtd.len

{{libheader|Action! Tool Kit}}

{{libheader|Action! Real Math}}

DEFINE PTR="CARD"

=={{header|Ada}}==

procedure FindMedian is

=={{header|ALGOL 68}}==

# Return the k-th smallest item in array x of length len #

=={{header|AntLang}}==

AntLang has a built-in median function.

=={{header|APL}}==

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.

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]}

=={{header|AppleScript}}==

===By iteration===

set med to medi(alist)

{{output}}

===Composing functionally===

{{Trans|JavaScript}}

{{Trans|Haskell}}

-- median :: [Num] -> Num

end uncons</syntaxhighlight>

{{Out}}

----

===Quickselect===

on getMedian(theList, l, r)

if (theList is {}) then return theList

<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===

on getMedian(theList, l, r)

script o

{{output}}

=={{header|Applesoft BASIC}}==

110 K = INT(L/2) : GOSUB 150

120 R = X(K)

300 REMSWAP

310 H = X(P1):X(P1) = X(P2)

L = 11 : GOSUB 100MEDIAN

? R</syntaxhighlight>Output:<pre>5.95</pre>

=={{header|Arturo}}==

arr2: [1 2 3 4 5 6]

=={{header|AutoHotkey}}==

Takes the lower of the middle two if length is even

MsgBox % median(seq, "`,") ; 4.1

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

BEGIN {

=={{header|BaCon}}==

DECLARE b[] = { 4.1, 7.2, 1.7, 9.3, 4.4, 3.2 } TYPE FLOATING

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

DIM vec1(10) AS SINGLE, vec2(11) AS SINGLE, n AS INTEGER

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

Sort% = FN_sortinit(0,0)

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.

begin decimals end int list med med1 med2 num number

. 0:?list

=={{header|C}}==

#include <stdlib.h>

===Quickselect algorithm===

Average O(n) time:

#include <stdlib.h>

#include <time.h>

Output:

median: 0.000473

<: 496010

=={{header|C sharp|C#}}==

using System.Linq;

=={{header|C++}}==

This function runs in linear time on average.

// inputs must be random-access iterators of doubles

Uses a GNU C++ policy-based data structure to compute median in O(log n) time.

{{libheader|gnu_pbds}}

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

=={{header|Clojure}}==

Simple:

(let [ns (sort ns)

cnt (count ns)

=={{header|COBOL}}==

Intrinsic function:

=={{header|Common Lisp}}==

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

"Select nth element in list, ordered by predicate, modifying list."

(do ((pivot (pop list))

=={{header|Crystal}}==

srtd = ary.sort

alen = srtd.size

=={{header|D}}==

T median(T)(T[] nums) pure nothrow {

=={{header|Delphi}}==

{$APPTYPE CONSOLE}

=={{header|E}}==

def sorted := list.sort()

def count := sorted.size()

}</syntaxhighlight>

# value: 2

=={{header|EasyLang}}==

#

subr partition

=={{header|EchoLisp}}==

(define (median L) ;; O(n log(n))

(set! L (vector-sort! < (list->vector L)))

=={{header|Elena}}==

ELENA 5.0 :

import system'math;

import extensions;

=={{header|Elixir}}==

{{trans|Erlang}}

def median([]), do: nil

def median(list) do

=={{header|Erlang}}==

-import(lists, [nth/2, sort/1]).

-compile(export_all).

=={{header|ERRE}}==

PROGRAM MEDIAN

v. Moreover it can search for the p median, not only the p=0.5 median.

>type median

function median (x, v: none, p)

=={{header|Euphoria}}==

atom min,k

-- Selection sort of half+1

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

=MEDIAN(A1:A10)

</syntaxhighlight>

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

=MEDIAN(

</syntaxhighlight>

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

23 11,5

21

=={{header|F Sharp|F#}}==

Median of Medians algorithm implementation

let rec splitToFives list =

match list with

=={{header|Factor}}==

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

IN: median

Usage:

5

( scratchpad ) 10 iota median .

=={{header|Forth}}==

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

: cell- -cell + ;

1- cells over + 2dup mid to midpoint

select midpoint @ ;</syntaxhighlight>

test 4 median . \ 2

{{works with|Fortran|90 and later}}

real :: a(7) = (/ 4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2 /), &

end program Median_Test</syntaxhighlight>

MEDIAN = FINDELEMENT(K + 1,A,N)

IF (MOD(N,2).EQ.0) MEDIAN = (FINDELEMENT(K,A,N) + MEDIAN)/2 </syntaxhighlight>

=={{header|FreeBASIC}}==

Sub quicksort(a() As Double, first As Integer, last As Integer)

=={{header|GAP}}==

local n, w;

w := SortedList(v);

===Sort===

Go built-in sort. O(n log n).

import (

Unfortunately in the case of median, k is n/2 so the algorithm is O(n^2). Still, it gives the idea of median by selection. Note that the partial selection sort does leave the k smallest values sorted, so in the case of an even number of elements, the two elements to average are available after a single call to sel().

import "fmt"

===Quickselect===

It doesn't take too much more code to implement a quickselect with random pivoting, which should run in expected time O(n). The qsel function here permutes elements of its parameter "a" in place. It leaves the slice somewhat more ordered, but unlike the sort and partial sort examples above, does not guarantee that element k-1 is in place. For the case of an even number of elements then, median must make two separate qsel() calls.

import (

=={{header|Groovy}}==

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

def s = col as SortedSet

if (s == null) return null

Test:

def sz = a.size()

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

nth :: Ord t => [t] -> Int -> t

Or {{libheader|hstats}}

3.0</syntaxhighlight>

=={{header|HicEst}}==

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

vec = RAN(1)

=={{header|Icon}} and {{header|Unicon}}==

A quick and dirty solution:

write(median(args))

end

=={{header|J}}==

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

median 1 9 2 4

3</syntaxhighlight>

The definition given in the addon script is:

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

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

median 1 9 2 4

2 4</syntaxhighlight>

Sorting:

public static double median(List<Double> list) {

Collections.sort(list);

Using priority queue (which sorts under the hood):

PriorityQueue<Double> pq = new PriorityQueue<Double>(list);

int n = list.size();

This version operates on objects rather than primitives and uses abstractions to operate on all of the standard numerics.

@FunctionalInterface

interface MedianFinder<T, R> extends Function<Collection<T>, R> {

===ES5===

if (ary.length == 0)

return null;

{{Trans|Haskell}}

'use strict';

{{Out}}

null,

4,

=={{header|jq}}==

length as $length

| sort as $s

else $s[$l2]

end

4.4

4.25</syntaxhighlight>

=={{header|Julia}}==

Julia has a built-in median() function

function median2(n)

s = sort(n)

=={{header|K}}==

med:{a:x@<x; i:(#a)%2; :[(#a)!2; a@i; {(+/x)%#x} a@i,i-1]}

v:10*6 _draw 0

An alternate solution which works in the oK implementation using the same dataset v from above and shows both numbers around the median point on even length datasets would be:

med:{a:x@<x; i:_(#a)%2

$[2!#a; a@i; |a@i,i-1]}

=={{header|Kotlin}}==

{{works with|Kotlin|1.0+}}

fun main(args: Array<String>) {

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

#a->sort

=={{header|Liberty BASIC}}==

dim a( 100), b( 100) ' assumes we will not have vectors of more terms...

=={{header|Lingo}}==

-- numlist = numlist.duplicate() -- if input list should not be altered

numlist.sort()

=={{header|LiveCode}}==

LC has median as a built-in function

returns 4.4, 4.25</syntaxhighlight>

To make our own, we need own own floor function first

if n < 0 then

return (trunc(n) - 1)

=={{header|LSL}}==

integer MAX_VALUE = 100;

default {

=={{header|Lua}}==

if type(numlist) ~= 'table' then return numlist end

table.sort(numlist)

=== Builtin ===

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

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

3.

=== 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 ] );

</syntaxhighlight>

For example:

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

3

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Built-in function:

Median[{1, 5, 3, 6, 4, 2}]</syntaxhighlight>

{{out}}

7/2</pre>

Custom function:

If[Mod[L,2]==0,

(t[[L/2]]+t[[L/2+1]])/2

]</syntaxhighlight>

Example of custom function:

mymedian[{1, 5, 3, 6, 4, 2}]</syntaxhighlight>

{{out}}

=={{header|MATLAB}}==

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

medianValue = median(setOfValues);

end</syntaxhighlight>

=={{header|Maxima}}==

median([41, 56, 72, 17, 93, 44, 32]); /* 44 */

median([41, 72, 17, 93, 44, 32]); /* 85/2 */</syntaxhighlight>

=={{header|MiniScript}}==

self.sort

m = floor(self.len/2)

=={{header|MUMPS}}==

;X is assumed to be a list of numbers separated by "^"

;I is a loop index

=={{header|Nanoquery}}==

{{trans|Python}}

def median(aray)

=={{header|NetRexx}}==

{{trans|Java}}

options replace format comments java crossref symbols nobinary

=={{header|NewLISP}}==

; oofoe 2012-01-25

=={{header|Nim}}==

{{trans|Python}}

proc median(xs: seq[float]): float =

=={{header|Oberon-2}}==

Oxford Oberon-2

MODULE Median;

IMPORT Out;

=={{header|Objeck}}==

use Structure;

=={{header|OCaml}}==

let median array =

let len = Array.length array in

=={{header|Octave}}==

Of course Octave has its own <tt>median</tt> 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.

if (numel(v) < 1)

y = NA;

=={{header|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)

=={{header|Oz}}==

fun {Median Xs}

Len = {Length Xs}

=={{header|PARI/GP}}==

Sorting solution.

vecsort(v)[#v\2]

};</syntaxhighlight>

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

if(#v<15, return(vecsort(v)[k]));

my(u=List(),pivot,left=List(),right=List());

=={{header|Pascal}}==

{{works with|Free_Pascal}}

type

=={{header|Perl}}==

{{trans|Python}}

my @a = sort {$a <=> $b} @_;

return ($a[$#a/2] + $a[@a/2]) / 2;

=={{header|Phix}}==

The obvious simple way:

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">median</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>

It is also possible to use the [[Quickselect_algorithm#Phix|quick_select]] routine for a small (20%) performance improvement,

which as suggested below may with luck be magnified by retaining any partially sorted results.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">medianq</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>

=={{header|Phixmonti}}==

def median /# l -- n #/

=={{header|PHP}}==

This solution uses the sorting method of finding the median.

function median($arr)

{

=={{header|Picat}}==

Lists = [

[1.121,10.3223,3.41,12.1,0.01],

=={{header|PicoLisp}}==

(let N (length Lst)

(if (bit? 1 N)

=={{header|PL/I}}==

n = dimension(A,1);

if iand(n,1) = 1 then /* an odd number of elements */

All statistical properties could easily be added to the output object.

function Measure-Data

{

}

</syntaxhighlight>

$statistics = Measure-Data 4, 5, 6, 7, 7, 7, 8, 1, 1, 1, 2, 3

$statistics

</pre>

Median only:

$statistics.Median

</syntaxhighlight>

=={{header|Processing}}==

float[] numbers = {3.1, 4.1, 5.9, 2.6, 5.3, 5.8};

println(median(numbers));

=={{header|Prolog}}==

length(L, Length),

I is Length div 2,

=={{header|Pure}}==

Inspired by the Haskell version.

when len = # x;

mid = len div 2;

=={{header|PureBasic}}==

If length = 0 : ProcedureReturn 0.0 : EndIf

SortArray(values(), #PB_Sort_Ascending)

=={{header|Python}}==

srtd = sorted(aray)

alen = len(srtd)

{{trans|Octave}}

if ( length(v) < 1 )

NA

=={{header|Racket}}==

(define (median numbers)

(define sorted (list->vector (sort (vector->list numbers) <)))

{{works with|Rakudo|2016.08}}

my @a = sort @_;

return (@a[(*-1) div 2] + @a[* div 2]) / 2;

<br>

In a slightly more compact way:

=={{header|REBOL}}==

median: func [

"Returns the midpoint value in a series of numbers; half the values are above, half are below."

=={{header|ReScript}}==

{

let float_compare = (a, b) => {

=={{header|REXX}}==

/* ══════════vector════════════ ══show vector═══ ════════show result═══════════ */

v= 1 9 2 4 ; say "vector" v; say 'median──────►' median(v); say

=={{header|Ring}}==

aList = [5,4,2,3]

see "medium : " + median(aList) + nl

=={{header|Ruby}}==

return nil if ary.empty?

mid, rem = ary.length.divmod(2)

Alternately:

srtd = aray.sort

alen = srtd.length

=={{header|Run BASIC}}==

mem$ = "CREATE TABLE med (x float)"

#mem execute(mem$)

Sorting, then obtaining the median element:

// sort in ascending order, panic on f64::NaN

xs.sort_by(|x,y| x.partial_cmp(y).unwrap() );

{{works with|Scala|2.8}} (See the Scala discussion on [[Mean]] for more information.)

import n._

val (lower, upper) = s.sortWith(_<_).splitAt(s.size / 2)

{{trans|Python}}

Using Rosetta Code's [[Bubble_Sort#Scheme|bubble-sort function]]

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

(list-ref (bubble-sort l >) (round (/ (length l) 2)))) 0.5))</syntaxhighlight>

Using [http://srfi.schemers.org/srfi-95/srfi-95.html SRFI-95]:

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

(list-ref (sort l less?) (round (/ (length l) 2)))) 0.5))</syntaxhighlight>

=={{header|Seed7}}==

include "float.s7i";

=={{header|SenseTalk}}==

SenseTalk has a built-in median function. This example also shows the implementation of a customMedian function that returns the same results.

put the median of [4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2, 6.6]

end customMedian</syntaxhighlight>

Output:

5

4.4

=={{header|Sidef}}==

var srtd = arry.sort;

var alen = srtd.length;

=={{header|Slate}}==

[

s isEmpty

].</syntaxhighlight>

inform: { 4.1 . 7.2 . 1.7 . 9.3 . 4.4 . 3.2 } median.</syntaxhighlight>

{{works with|GNU Smalltalk}}

median [

self size = 0

].</syntaxhighlight>

median displayNl.

{ 4.1 . 7.2 . 1.7 . 9.3 . 4.4 . 3.2 } asOrderedCollection

Use '''[https://www.stata.com/help.cgi?summarize summarize]''' to compute the median of a variable (as well as other basic statistics).

gen x=rbeta(0.2,1.3)

quietly summarize x, detail

Here is a straightforward implementation using '''[https://www.stata.com/help.cgi? sort]'''.

sort `1'

if mod(_N,2)==0 {

=={{header|Tcl}}==

set list [lsort -real $args]

set len [llength $list]

Using the built-in function:

=={{header|TI-89 BASIC}}==

=={{header|Ursala}}==

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

#import flo

median = fleq-<; @K30K31X eql?\~&rh div\2.+ plus@lzPrhPX</syntaxhighlight>

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

examples =

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

double a = *(double*) a_ref;

double b = *(double*) b_ref;

{{trans|Phix}}

Uses [[Quickselect_algorithm#VBA|quick select]].

Dim res As Double, tmp As Integer

Dim l As Integer, k As Integer

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

EOF Goto_Line(Cur_Line/2)

Reg_Copy(10, 1)</syntaxhighlight>

=={{header|Vlang}}==

println(median([3, 1, 4, 1])) // prints 2

println(median([3, 1, 4, 1, 5])) // prints 3

</pre>

If you use math.stats module the list parameter must be sorted

fn main() {

println(stats.median<int>([1, 1, 3, 4])) // prints 2

=={{header|Wortel}}==

; iterative

med1 &l @let {a @sort l s #a i @/s 2 ?{%%s 2 ~/ 2 +`-i 1 a `i a `i a}}

{{libheader|Wren-math}}

{{libheader|Wren-queue}}

import "/math" for Nums

import "/queue" for PriorityQueue

=={{header|Yabasic}}==

{{trans|Lua}}

return int(x + .05)

end sub

=={{header|zkl}}==

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

fcn median(xs){

( quickSelect(xs,n/2-1) + quickSelect(xs,n/2) )/2;

}</syntaxhighlight>

median(T( 5.1, 2.6, 8.8, 4.6, 4.1 )); //-->4.6</syntaxhighlight>

=={{header|Zoea}}==

program: median

case: 1

=={{header|zonnon}}==

module Averages;