I need to write function that will accept array of decimals and it will find the median.
Is there a function in the .net Math library?
Looks like other answers are using sorting. That's not optimal from performance point of view because it takes O(n logn)
time. It is possible to calculate median in O(n)
time instead. The generalized version of this problem is known as "n-order statistics" which means finding an element K in a set such that we have n elements smaller or equal to K and rest are larger or equal K. So 0th order statistic would be minimal element in the set (Note: Some literature use index from 1 to N instead of 0 to N-1). Median is simply (Count-1)/2
-order statistic.
Below is the code adopted from Introduction to Algorithms by Cormen et al, 3rd Edition.
/// <summary>
/// Partitions the given list around a pivot element such that all elements on left of pivot are <= pivot
/// and the ones at thr right are > pivot. This method can be used for sorting, N-order statistics such as
/// as median finding algorithms.
/// Pivot is selected ranodmly if random number generator is supplied else its selected as last element in the list.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 171
/// </summary>
private static int Partition<T>(this IList<T> list, int start, int end, Random rnd = null) where T : IComparable<T>
{
if (rnd != null)
list.Swap(end, rnd.Next(start, end+1));
var pivot = list[end];
var lastLow = start - 1;
for (var i = start; i < end; i++)
{
if (list[i].CompareTo(pivot) <= 0)
list.Swap(i, ++lastLow);
}
list.Swap(end, ++lastLow);
return lastLow;
}
/// <summary>
/// Returns Nth smallest element from the list. Here n starts from 0 so that n=0 returns minimum, n=1 returns 2nd smallest element etc.
/// Note: specified list would be mutated in the process.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 216
/// </summary>
public static T NthOrderStatistic<T>(this IList<T> list, int n, Random rnd = null) where T : IComparable<T>
{
return NthOrderStatistic(list, n, 0, list.Count - 1, rnd);
}
private static T NthOrderStatistic<T>(this IList<T> list, int n, int start, int end, Random rnd) where T : IComparable<T>
{
while (true)
{
var pivotIndex = list.Partition(start, end, rnd);
if (pivotIndex == n)
return list[pivotIndex];
if (n < pivotIndex)
end = pivotIndex - 1;
else
start = pivotIndex + 1;
}
}
public static void Swap<T>(this IList<T> list, int i, int j)
{
if (i==j) //This check is not required but Partition function may make many calls so its for perf reason
return;
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
/// <summary>
/// Note: specified list would be mutated in the process.
/// </summary>
public static T Median<T>(this IList<T> list) where T : IComparable<T>
{
return list.NthOrderStatistic((list.Count - 1)/2);
}
public static double Median<T>(this IEnumerable<T> sequence, Func<T, double> getValue)
{
var list = sequence.Select(getValue).ToList();
var mid = (list.Count - 1) / 2;
return list.NthOrderStatistic(mid);
}
Few notes:
O(n)
expected time. If you want O(n)
worse case time then there is technique to use median-of-median. While this would improve worse case performance, it degrades average case because constant in O(n)
is now larger. However if you would be calculating median mostly on very large data then its worth to look at.(Count-1)/2
in sorted array. But when you even number of element (Count-1)/2
is not an integer anymore and you have two medians: Lower median Math.Floor((Count-1)/2)
and Math.Ceiling((Count-1)/2)
. Some textbooks use lower median as "standard" while others propose to use average of two. This question becomes particularly critical for set of 2 elements. Above code returns lower median. If you wanted instead average of lower and upper then you need to call above code twice. In that case make sure to measure performance for your data to decide if you should use above code VS just straight sorting.MethodImplOptions.AggressiveInlining
attribute on Swap<T>
method for slightly improved performance.