Calculate median in c

Question

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

User · Answer

My 5 cents  because it appears more straightforward simpler and sufficient for short lists    public static T Median lt T gt  this IEnumerable lt T gt  items        var i    int Math Ceiling  double  items Count   - 1    2       if  i  gt   0                var values   items ToList            values Sort            return values i              return default T       P S  using  higher median  as described by ShitalShah

User · Answer

Thanks Rafe  this takes into account the issues your replyers posted   public static double GetMedian double   sourceNumbers              Framework 2 0 version of this method  there is an easier way in F4                 if  sourceNumbers    null    sourceNumbers Length    0              throw new System Exception  Median of empty array not defined                make sure the list is sorted  but use a new array         double   sortedPNumbers    double   sourceNumbers Clone            Array Sort sortedPNumbers              get the median         int size   sortedPNumbers Length          int mid   size   2          double median    size   2    0     double sortedPNumbers mid      double sortedPNumbers mid     double sortedPNumbers mid - 1     2          return median

User · Answer

Here is the fastest unsafe implementation  same algorithm before  taken from this source       MethodImpl MethodImplOptions AggressiveInlining       private static unsafe void SwapElements int  p  int  q                int temp    p           p    q           q   temp             public static unsafe int Median int   arr  int n                int middle  ll  hh           int low   0  int high   n - 1  int median    low   high    2          fixed  int  arrptr   arr                        for                                    if  high  lt   low                      return arr median                    if  high    low   1                                        if  arr low   gt  arr high                           SwapElements arrptr   low  arrptr   high                       return arr median                                      middle    low   high    2                  if  arr middle   gt  arr high                       SwapElements arrptr   middle  arrptr   high                    if  arr low   gt  arr high                       SwapElements arrptr   low  arrptr   high                    if  arr middle   gt  arr low                       SwapElements arrptr   middle  arrptr   low                    SwapElements arrptr   middle  arrptr   low   1                    ll   low   1                  hh   high                  for                                            do ll    while  arr low   gt  arr ll                        do hh--  while  arr hh   gt  arr low                         if  hh  lt  ll                          break                       SwapElements arrptr   ll  arrptr   hh                                      SwapElements arrptr   low  arrptr   hh                    if  hh  lt   median                      low   ll                  if  hh  gt   median                      high   hh - 1

User · Answer

I have an histogram with the variable   group Here how I calculate my median     int   group   new int nbr        -- Fill the group with values---     sum all data in median int median   0  for  int i  0 i lt nbr i    median    group i       then divide by 2  median   median   2      find 50  first part  for  int i   0  i  lt  nbr  i         median -  group i      if  median  lt   0             median   i        break           median is the group index of median

User · Answer

Here s a generic version of Jason s answer           lt summary gt          Gets the median value from an array          lt  summary gt           lt typeparam name  T  gt The array type lt  typeparam gt           lt param name  sourceArray  gt The source array lt  param gt           lt param name  cloneArray  gt If it doesn t matter if the source array is sorted  you can pass false to improve performance lt  param gt           lt returns gt  lt  returns gt      public static T GetMedian lt T gt  T   sourceArray  bool cloneArray   true  where T   IComparable lt T gt                  Framework 2 0 version of this method  there is an easier way in F4                 if  sourceArray    null    sourceArray Length    0              throw new ArgumentException  Median of empty array not defined                make sure the list is sorted  but use a new array         T   sortedArray   cloneArray    T   sourceArray Clone     sourceArray          Array Sort sortedArray              get the median         int size   sortedArray Length          int mid   size   2          if  size   2    0              return sortedArray mid            dynamic value1   sortedArray mid           dynamic value2   sortedArray mid - 1           return  sortedArray mid    value2    0 5

User · Answer

Math NET is an opensource library that offers a method for calculating the Median  The nuget package is called MathNet Numerics   The usage is pretty simple   using MathNet Numerics Statistics   IEnumerable lt double gt  data  double median   data Median

User · Answer

Sometime in the future  This is I think as simple as it can get   using System  using System Collections Generic  using System Linq  using System Text  using System Threading Tasks   namespace Median       class Program               static void Main string   args                        var mediaValue   0 0              var items   new     1  2  3  4 5                var getLengthItems   items Length              Array Sort items               if  getLengthItems   2    0                                var firstValue   items  items Length   2  - 1                   var secondValue   items  items Length   2                    mediaValue    firstValue   secondValue    2 0                            if  getLengthItems   2    1                                mediaValue   items  items Length   2                              Console WriteLine mediaValue               Console WriteLine  Enter to Exit                 Console ReadKey

User · Answer

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        lt summary gt      Partitions the given list around a pivot element such that all elements on left of pivot are  lt   pivot     and the ones at thr right are  gt  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      lt  summary gt  private static int Partition lt T gt  this IList lt T gt  list  int start  int end  Random rnd   null  where T   IComparable lt T gt        if  rnd    null          list Swap end  rnd Next start  end 1         var pivot   list end       var lastLow   start - 1      for  var i   start  i  lt  end  i                  if  list i  CompareTo pivot   lt   0              list Swap i    lastLow             list Swap end    lastLow       return lastLow          lt summary gt      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      lt  summary gt  public static T NthOrderStatistic lt T gt  this IList lt T gt  list  int n  Random rnd   null  where T   IComparable lt T gt        return NthOrderStatistic list  n  0  list Count - 1  rnd     private static T NthOrderStatistic lt T gt  this IList lt T gt  list  int n  int start  int end  Random rnd  where T   IComparable lt T gt        while  true                var pivotIndex   list Partition start  end  rnd           if  pivotIndex    n              return list pivotIndex            if  n  lt  pivotIndex              end   pivotIndex - 1          else             start   pivotIndex   1           public static void Swap lt T gt  this IList lt T gt  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          lt summary gt      Note  specified list would be mutated in the process       lt  summary gt  public static T Median lt T gt  this IList lt T gt  list  where T   IComparable lt T gt        return list NthOrderStatistic  list Count - 1  2      public static double Median lt T gt  this IEnumerable lt T gt  sequence  Func lt T  double gt  getValue        var list   sequence Select getValue  ToList        var mid    list Count - 1    2      return list NthOrderStatistic mid       Few notes    This code replaces tail recursive code from the original version in book in to iterative loop  It also eliminates unnecessary extra check from original version when start  end  I ve provided two version of Median  one that accepts IEnumerable and then creates a list  If you use the version that accepts IList then keep in mind it modifies the order in list  Above methods calculates median or any i-order statistics in 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  The NthOrderStatistics method allows to pass random number generator which would be then used to choose random pivot during partition  This is generally not necessary unless you know your data has certain patterns so that last element won t be random enough or if somehow your code is exposed outside for targeted exploitation   Definition of median is clear if you have odd number of elements  It s just the element with index  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  For  net 4 5  you can add MethodImplOptions AggressiveInlining attribute on Swap lt T gt  method for slightly improved performance

User · Answer

CenterSpace s NMath library provides a function    double   values   new double arraySize   double median   NMathFunctions Median values     Optionally you can opt to use NaNMedian  if your array may contain null values  but you will need to convert the array to a vector   double median   NMathFunctions NaNMedian new DoubleVector values      CenterSpace s NMath Library isn t free  but many universities have licenses

User · Answer

decimal Median decimal   xs      Array Sort xs     return xs xs Length   2       Should do the trick   -- EDIT --  For those who want the full monty  here is the complete  short  pure solution  a non-empty input array is assumed    decimal Median decimal   xs      var ys   xs OrderBy x   gt  x  ToList      double mid    ys Count - 1    2 0    return  ys  int  mid     ys  int  mid   0 5      2

User · Answer

Below code works  but not very efficient way      static void Main String   args            int n   Convert ToInt32 Console ReadLine                         int   medList   new int n            for  int x   0  x  lt  n  x                medList x    int Parse Console ReadLine                sort the input array            Array Sort medList                       for  int x   0  x  lt  n  x                          double   newArr   new double x   1               for  int y   0  y  lt   x  y                    newArr y    medList y                Array Sort newArr               int curInd   x   1              if  curInd   2    0    even                               int mid    x   2   lt   0   0    newArr Length   2                   if  mid  gt  1  mid--                  double median    newArr mid    newArr mid 1     2                  Console WriteLine   0 F1    median                             else   odd                               int mid    x   2   lt   0   0    newArr Length   2                   double median   newArr mid                   Console WriteLine   0 F1    median

User · Answer

Is there a function in the  net Math library    No   It s not hard to write your own though  The naive algorithm sorts the array and picks the middle  or the average of the two middle  elements  However  this algorithm is O n log n  while its possible to solve this problem in O n  time  You want to look at selection algorithms to get such an algorithm

[c#] Calculate median in c#

Examples related to c#

Examples related to .net

Examples related to algorithm

Examples related to median