How to calculate the median of an array

Question

I m trying to calculate the total  mean and median of an array thats populated by input received by a textfield  I ve managed to work out the total and the mean  I just can t get the median to work  I think the array needs to be sorted before I can do this  but I m not sure how to do this  Is this the problem  or is there another one that I didn t find  Here is my code   import java applet Applet  import java awt Graphics  import java awt    import java awt event     public class whileloopq extends Applet implements ActionListener       Label label      TextField input      int num      int index      int   numArray   new int 20       int sum      int total      double avg      int median         public void init                  label   new Label  Enter numbers            input   new TextField 5           add label           add input           input addActionListener this           index   0             public void actionPerformed  ActionEvent ev                int num   Integer parseInt input getText             numArray index    num          index            if  index    20          input setEnabled false               input setText              sum   0          for  int i   0  i  lt  numArray length  i                          sum    numArray i                     total   sum          avg   total   index           median   numArray numArray length 2              repaint                  public void paint  Graphics graf                   graf drawString  Total         Integer toString total   25  85           graf drawString  Average       Double toString avg   25  100           graf drawString  Median       Integer toString median   25  115

User · Answer

Arrays sort numArray   int middle     numArray length    2   if numArray length   2    0    int medianA   numArray middle    int medianB   numArray middle-1    median    medianA   medianB    2    else   median   numArray middle   1       EDIT  I initially had medianB setting to middle 1 in the even length arrays  this was wrong due to arrays starting count at 0   I have updated it to use middle-1 which is correct and should work properly for an array with an even length

User · Answer

Sorting the array is unnecessary and inefficient   There s a variation of the QuickSort  QuickSelect  algorithm which has an average run time of O n   if you sort first  you re down to O n log n    It actually finds the nth smallest item in a list  for a median  you just use n   half the list length   Let s call it quickNth  list  n   The concept is that to find the nth smallest  choose a  pivot  value    Exactly how you choose it isn t critical  if you know the data will be thoroughly random  you can take the first item on the list   Split the original list into three smaller lists   One with values smaller than the pivot  One with values equal to the pivot  And one with values greater than the pivot   You then have three cases   The  quot smaller quot  list has  gt   n items   In that case  you know that the nth smallest is in that list   Return quickNth smaller  n   The smaller list has  lt  n items  but the sum of the lengths of the smaller and equal lists have  gt   n items   In this case  the nth is equal to any item in the  quot equal quot  list  you re done  n is greater than the sum of the lengths of the smaller and equal lists   In that case  you can essentially skip over those two  and adjust n accordingly   Return quickNth greater  n - length smaller  - length equal     Done  If you re not sure that the data is thoroughly random  you need to be more sophisticated about choosing the pivot   Taking the median of the first value in the list  the last value in the list  and the one midway between the two works pretty well  If you re very unlucky with your choice of pivots  and you always choose the smallest or highest value as your pivot  this takes O n 2  time  that s bad   But  it s also very unlikely if you choose your pivot with a decent algorithm  Sample code  import java util     public class Utility                              param coll an ArrayList of Comparable objects       return the median of coll                              public static  lt T extends Number gt  double median ArrayList lt T gt  coll  Comparator lt T gt  comp          double result        int n   coll size   2               if  coll size     2    0      even number of items  find the middle two and average them          result    nth coll  n-1  comp  doubleValue     nth coll  n  comp  doubleValue      2 0        else                         odd number of items  return the one in the middle          result   nth coll  n  comp  doubleValue                    return result          median coll                                       param coll a collection of Comparable objects       param n  the position of the desired object  using the ordering defined on the list elements       return the nth smallest object                                public static  lt T gt  T nth ArrayList lt T gt  coll  int n  Comparator lt T gt  comp          T result  pivot        ArrayList lt T gt  underPivot   new ArrayList lt  gt     overPivot   new ArrayList lt  gt     equalPivot   new ArrayList lt  gt                     choosing a pivot is a whole topic in itself           this implementation uses the simple strategy of grabbing something from the middle of the ArrayList               pivot   coll get n 2                   split coll into 3 lists based on comparison with the pivot              for  T obj   coll             int order   comp compare obj  pivot                      if  order  lt  0            obj  lt  pivot             underPivot add obj            else if  order  gt  0       obj  gt  pivot             overPivot add obj            else                     obj   pivot             equalPivot add obj              for each obj in coll                 recurse on the appropriate list              if  n  lt  underPivot size             result   nth underPivot  n  comp         else if  n  lt  underPivot size     equalPivot size       equal to pivot  just return it          result   pivot        else     everything in underPivot and equalPivot is too small   Adjust n accordingly in the recursion           result   nth overPivot  n - underPivot size   - equalPivot size    comp                   return result          nth coll  n                 public static void main  String   args          Comparator lt Integer gt  comp   Comparator naturalOrder          Random rnd   new Random                 for  int size   1  size  lt   10  size               ArrayList lt Integer gt  coll   new ArrayList lt  gt  size            for  int i   0  i  lt  size  i                coll add rnd nextInt 100                    System out println  quot Median of  quot    coll toString      quot  is  quot    median coll  comp               for a range of possible input sizes         main args       Utility

User · Answer

And nobody paying attention when list contains only one element  list size    1   All your answers will crash with index out of bound exception  because integer division returns zero  1   2   0   Correct answer  in Kotlin    MEDIAN  MEDIAN              override fun calculate values  List lt BigDecimal gt    BigDecimal                if  values size    1                    return values first                             if  values size  gt  1                    val valuesSorted   values sorted                   val mid   valuesSorted size   2                 return if  valuesSorted size   2    0                        valuesSorted mid                    else                       AVERAGE calculate listOf valuesSorted mid - 1   valuesSorted mid                                                return null

User · Answer

If you want to use any external library here is Apache commons math library using you can calculate the Median  For more methods and use take look at the API documentation  import org apache commons math3                            calculate median public double getMedian double   values    Median median   new Median     double medianValue   median evaluate values    return medianValue               For more on evaluate method AbstractUnivariateStatistic evaluate   Update    Calculate in program     Generally  median is calculated using the following two formulas given here       If n is odd then Median  M    value of   n   1  2 th item term    If n is even then Median  M    value of    n  2 th item term     n  2   1 th item term   2   In your program you have numArray  first you need to sort array using Arrays sort    Arrays sort numArray   int middle   numArray length 2  int medianValue   0    declare variable  if  numArray length 2    1       medianValue   numArray middle   else    medianValue    numArray middle-1    numArray middle     2

User · Answer

The Arrays class in Java has a static sort function  which you can invoke with Arrays sort numArray    Arrays sort numArray   double median  if  numArray length   2    0      median     double numArray numArray length 2     double numArray numArray length 2 - 1   2  else     median    double  numArray numArray length 2

User · Answer

Arrays sort numArray   return  numArray size 2    numArray  size-1  2     2

User · Answer

public int   data  31  29  47  48  23  30  21           40  23  39  47  47  42  44  23  26  44  32  20  40    public double median                 Arrays sort this data           double result 0          int size this data length            if size 2  1                        result data   size-1  2  1               System out println   uneven size     result                     else                        int middle pair first index   size-1  2              result  data middle pair first index 1  data middle pair first index   2              System out println   Even size     result                      return result

User · Answer

You can find good explanation at https   www youtube com watch time continue 23 amp v VmogG01IjYc  The idea it to use 2 Heaps viz one max heap and mean heap   class Heap   private Queue lt Integer gt  low   new PriorityQueue lt  gt  Comparator reverseOrder     private Queue lt Integer gt  high   new PriorityQueue lt  gt      public void add int number        Queue lt Integer gt  target   low size    lt   high size     low   high      target add number       balance       private void balance         while  low isEmpty    amp  amp   high isEmpty    amp  amp  low peek    gt  high peek              Integer lowHead  low poll            Integer highHead   high poll            low add highHead           high add lowHead            public double median         if low isEmpty    amp  amp  high isEmpty              throw new IllegalStateException  Heap is empty          else           return low size      high size      low peek     high peek      2 0   low peek

User · Answer

As  Bruce-Feist mentions  for a large number of elements  I d avoid any solution involving sort if performance is something you are concerned about  A different approach than those suggested in the other answers is Hoare s algorithm to find the k-th smallest of element of n items  This algorithm runs in O n    public int findKthSmallest int   array  int k        if  array length  lt  10                Arrays sort array           return array k             int start   0      int end   array length - 1      int x  temp      int i  j      while  start  lt  end                x   array k           i   start          j   end          do                       while  array i   lt  x                  i                while  x  lt  array j                   j--              if  i  lt   j                                temp   array i                   array i    array j                   array j    temp                  i                    j--                          while  i  lt   j           if  j  lt  k              start   i          if  k  lt  i              end   j            return array k       And to find the median   public int median int   array        int length   array length      if   length  amp  1     0     even         return  findKthSmallest array  array length   2    findKthSmallest array  array length   2   1     2      else    odd         return findKthSmallest array  array length   2

User · Answer

I faced a similar problem yesterday  I wrote a method with Java generics in order to calculate the median value of every collection of Numbers  you can apply my method to collections of Doubles  Integers  Floats and returns a double  Please consider that my method creates another collection in order to not alter the original one  I provide also a test  have fun   -   public static  lt T extends Number  amp  Comparable lt T gt  gt  double median Collection lt T gt  numbers       if numbers isEmpty             throw new IllegalArgumentException  Cannot compute median on empty collection of numbers              List lt T gt  numbersList   new ArrayList lt  gt  numbers       Collections sort numbersList       int middle   numbersList size   2      if numbersList size     2    0           return 0 5    numbersList get middle  doubleValue     numbersList get middle-1  doubleValue           else           return numbersList get middle  doubleValue               JUnit test code snippet          Test of median method  of class Utils       Test public void testMedian         System out println  median        Double expResult   3 0      Double result   Utils median Arrays asList 3 0 2 0 1 0 9 0 13 0        assertEquals expResult  result       expResult   3 5      result   Utils median Arrays asList 3 0 2 0 1 0 9 0 4 0 13 0        assertEquals expResult  result       Usage example  consider the class name is Utils    List lt Integer gt  intValues         omitted init Set lt Float gt  floatValues         omitted init       double intListMedian   Utils median intValues   double floatSetMedian   Utils median floatValues     Note  my method works on collections  you can convert arrays of numbers to list of numbers as pointed here

User · Answer

Try sorting the array first  Then after it s sorted  if the array has an even amount of elements the mean of the middle two is the median  if it has a odd number  the middle element is the median

User · Answer

Use Arrays sort and then take the middle element  in case the number n of elements in the array is odd  or take the average of the two middle elements  in case n is even      public static long median long   l          Arrays sort l       int middle   l length   2      if  l length   2    0              long left   l middle - 1         long right   l middle         return  left   right    2            else             return l middle               Here are some examples      Test   public void evenTest           long   l             5  6  1  3  2            Assert assertEquals  3   4    2  median l            Test   public oddTest           long   l             5  1  3  2  4            Assert assertEquals 3  median l          And in case your input is a Collection  you might use Google Guava to do something like this   public static long median Collection lt Long gt  numbers      return median Longs toArray numbers       requires import com google common primitives Longs

User · Answer

I was looking at the same statistics problems  The approach you are thinking it is good and it will work   Answer to the sorting has been given    But in case you are interested in algorithm performance  I think there are a couple of algorithms that have better performance than just sorting the array  one  QuickSelect  is indicated by  bruce-feist s answer and is very well explained    Java implementation  https   discuss leetcode com topic 14611 java-quick-select    But there is a variation of this algorithm named median of medians  you can find a good explanation on this link   http   austinrochford com posts 2013-10-28-median-of-medians html  Java implementation of this   - https   stackoverflow com a 27719796 957979

User · Answer

public static int median int   arr    int median   0  java util Arrays sort arr            for  int i 0 i lt arr length i                       if  arr length   2    1            median   Math round arr arr length 2          else           median    arr  arr length 2     arr  arr length 2 -1   2          return median

User · Answer

Check out the Arrays sort methods   http   docs oracle com javase 6 docs api java util Arrays html  You should also really abstract finding the median into its own method  and just return the value to the calling method   This will make testing your code much easier

[java] How to calculate the median of an array?

Examples related to java

Examples related to arrays