java – How to calculate the median of an array?

java – How to calculate the median of an array?

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

Sorting the array is unnecessary and inefficient. Theres a variation of the QuickSort (QuickSelect) algorithm which has an average run time of O(n); if you sort first, youre 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. Lets call it quickNth (list, n).

The concept is that to find the nth smallest, choose a pivot value. (Exactly how you choose it isnt 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; youre 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 youre 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 youre 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; thats bad. But, its 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

java – How to calculate the median of an array?

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;
}
.......

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;

Leave a Reply

Your email address will not be published.