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.
There are two approaches to this. One is to sort the elements, and then pick the one in the middle. Sorting would take at least O(n log n). The other solution is to use the selection algorithm to find the median in O(n) time.
C
<lang C>#include <stdio.h>
- include <stdlib.h>
typedef struct floatList {
float *list; int size;
} *FloatList;
int floatcmp( const void *a, const void *b) {
if (*(float *)a > *(float *)b) return 1; else if (*(float *)a < *(float *)b) return -1; else return 0;
}
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;
}</lang>
C++
This function runs in linear time on average. <lang cpp>#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;
}</lang>
Fortran
<lang fortran>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</lang>
Java
<lang java5>// Note: this function modifies the input list public static double median(List<Double> list){
Collections.sort(list);
if(list.size() % 2 == 0){
return (list.get(list.size() / 2) + list.get(list.size() / 2 - 1)) / 2;
}
return list.get((list.size()-1)/2);
}</lang>
OCaml
<lang ocaml>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;;</lang>
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. <lang octave>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))</lang>
Python
<lang 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)</lang>
Ruby
<lang 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</lang>
Smalltalk
<lang 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 ]
]
].</lang>
<lang smalltalk>{ 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.</lang>
Tcl
<lang 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</lang>