How to calculate the median of an array?

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:

  1. The "smaller" list has >= n items. In that case, you know that the nth smallest is in that list. Return quickNth(smaller, n).
  2. The smaller list has < n items, but the sum of the lengths of the smaller and equal lists have >= n items. In this case, the nth is equal to any item in the "equal" list; you're done.
  3. 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 <T extends Number> double median(ArrayList<T> coll, Comparator<T> 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 <T> T nth(ArrayList<T> coll, int n, Comparator<T> comp) {
      T result, pivot;
      ArrayList<T> underPivot = new ArrayList<>(), overPivot = new ArrayList<>(), equalPivot = new ArrayList<>();
      
      // 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 < 0)        // obj < pivot
            underPivot.add(obj);
         else if (order > 0)   // obj > pivot
            overPivot.add(obj);
         else                  // obj = pivot
            equalPivot.add(obj);
      } // for each obj in coll
      
      // recurse on the appropriate list
      
      if (n < underPivot.size())
         result = nth(underPivot, n, comp);
      else if (n < 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<Integer> comp = Comparator.naturalOrder();
      Random rnd = new Random();
      
      for (int size = 1; size <= 10; size++) {
         ArrayList<Integer> coll = new ArrayList<>(size);
         for (int i = 0; i < size; i++)
            coll.add(rnd.nextInt(100));
      
         System.out.println("Median of " + coll.toString() + " is " + median(coll, comp));
      } // for a range of possible input sizes
   } // main(args)
} // Utility

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;

Arrays.sort(numArray);
return (numArray[size/2] + numArray[(size-1)/2]) / 2;

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

Tags:

Java

Arrays