CODEWITHSUNDEEP
javaarrays
Will
Will

Reputation: 1507

How to calculate the median of an array?

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



    }
}

Upvotes: 61

Views: 297902

Answers (16)

lynnyi
lynnyi

Reputation: 1352

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

Upvotes: 106

Shyamlal Yadav
Shyamlal Yadav

Reputation: 1

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

}

Upvotes: 0

thiagosteps227
thiagosteps227

Reputation: 46

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;

}

Upvotes: 1

Bruce Feist
Bruce Feist

Reputation: 621

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

Upvotes: 41

O.Viv.
O.Viv.

Reputation: 33

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

Upvotes: 1

Eldar
Eldar

Reputation: 5227

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
        }
    },

Upvotes: 0

Abhijit Gaikwad
Abhijit Gaikwad

Reputation: 3162

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

}

Upvotes: 4

i_use_the_internet
i_use_the_internet

Reputation: 614

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

Upvotes: 5

cesaregb
cesaregb

Reputation: 765

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

Upvotes: 2

Fabiano Tarlao
Fabiano Tarlao

Reputation: 3232

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 <T extends Number & Comparable<T>> double median(Collection<T> numbers){
    if(numbers.isEmpty()){
        throw new IllegalArgumentException("Cannot compute median on empty collection of numbers");
    }
    List<T> numbersList = new ArrayList<>(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<Integer> intValues = ... //omitted init
Set<Float> 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

Upvotes: 1

N_E
N_E

Reputation: 787

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

Upvotes: 0

Aniket Kulkarni
Aniket Kulkarni

Reputation: 12983

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;

Upvotes: 12

Walls
Walls

Reputation: 4010

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.

Upvotes: 4

Hbf
Hbf

Reputation: 3114

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<Long> numbers)
{
  return median(Longs.toArray(numbers)); // requires import com.google.common.primitives.Longs;
}

Upvotes: 2

aglassman
aglassman

Reputation: 2653

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.

Upvotes: 0

mjgpy3
mjgpy3

Reputation: 8937

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.

Upvotes: 2

Related Questions