How to calculate the median of an array?

Viewed 254701

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



    }
}
16 Answers

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;
Arrays.sort(numArray);
return (numArray[size/2] + numArray[(size-1)/2]) / 2;

You can find good explanation at https://www.youtube.com/watch?time_continue=23&v=VmogG01IjYc

The idea it to use 2 Heaps viz one max heap and mean heap.

class Heap {
private Queue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder());
private Queue<Integer> high = new PriorityQueue<>();

public void add(int number) {
    Queue<Integer> target = low.size() <= high.size() ? low : high;
    target.add(number);
    balance();
}

private void balance() {
    while(!low.isEmpty() && !high.isEmpty() && low.peek() > high.peek()) {
        Integer lowHead= low.poll();
        Integer highHead = high.poll();
        low.add(highHead);
        high.add(lowHead);
    }
}

public double median() {
    if(low.isEmpty() && high.isEmpty()) {
        throw new IllegalStateException("Heap is empty");
    } else {
        return low.size() == high.size() ? (low.peek() + high.peek()) / 2.0 : low.peek();
    }
}

}

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<BigDecimal>): BigDecimal? {
            if (values.size == 1) {
                return values.first()
            }
            if (values.size > 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
        }
    },

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 < 10)
    {
        Arrays.sort(array);
        return array[k];
    }
    int start = 0;
    int end = array.length - 1;
    int x, temp;
    int i, j;
    while (start < end)
    {
        x = array[k];
        i = start;
        j = end;
        do
        {
            while (array[i] < x)
                i++;
            while (x < array[j])
                j--;
            if (i <= j)
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        } while (i <= j);
        if (j < k)
            start = i;
        if (k < i)
            end = j;
    }
    return array[k];
}

And to find the median:

public int median(int[] array)
{
    int length = array.length;
    if ((length & 1) == 0) // even
        return (findKthSmallest(array, array.length / 2) + findKthSmallest(array, array.length / 2 + 1)) / 2;
    else // odd
        return findKthSmallest(array, array.length / 2);
}
public static int median(int[] arr) {
int median = 0;
java.util.Arrays.sort(arr);
        
for (int i=0;i<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;

}

package arrays;

public class Arraymidleelement {
    
    
    static public double middleArrayElement(int []  arr)
    {
     double  mid;
        if(arr.length%2==0)
        {
            mid=((double)arr[arr.length/2]+(double)arr[arr.length/2-1])/2;
            return mid;
        }
    
        
        return arr[arr.length/2];
        
        
        
    }
    public static void main(String[] args) {
        int arr[]= {1,2,3,4,5,6};
        
        System.out.println( middleArrayElement(arr));
        
    }
    

}
Related