# 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
else if (order > 0)   // obj > pivot
else                  // obj = pivot
} // 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++)

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