¿Cómo calcular la mediana de una matriz?

10 minutos de lectura

Avatar de usuario de Will
Voluntad

Estoy tratando de calcular el total, la media y la mediana de una matriz que se completa con la entrada recibida por un campo de texto. Me las arreglé para calcular el total y la media, simplemente no puedo hacer que la mediana funcione. Creo que la matriz debe ordenarse antes de que pueda hacer esto, pero no estoy seguro de cómo hacerlo. ¿Es este el problema, o hay otro que no encontré? Aquí está mi código:

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



    }
}

avatar de usuario de lynnyi
lynnyi

La clase Arrays en Java tiene una función de clasificación estática, que puede invocar con 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];

  • Pienso que el else cláusula debe ser: median = (double) numArray[(numArray.length - 1)/2];

    – FBB

    25/06/2016 a las 19:42

  • @FBB dan el mismo resultado. Introducimos la cláusula else cuando la longitud es impar, por lo que es 2*k + 1 por algún entero k. la mitad es k + 0.5pero cuando se convierte en un número entero (porque es un índice de matriz), se convierte simplemente en k.

    – ivan

    28 de febrero de 2017 a las 12:53

  • ¿Y si la matriz contiene solo un elemento? Su código se bloqueará con una excepción fuera de límite.

    – Eldar Agalarov

    12 de noviembre de 2018 a las 13:58

  • @EldarAgalarov, ¿por qué debería fallar con una excepción fuera de límite si la matriz contiene solo un elemento? Una longitud de uno es impar, por lo que entra en el caso else, donde intenta acceder al elemento en numArray.length/2. Ya que numArray.length es uno, calcula el índice como 1/2 lo que da 0. Y 0 es un índice válido para una matriz de longitud uno.

    – Thomas Klager

    10 de febrero de 2020 a las 20:03

  • pienso median = (double) numArray[(int) Math.floor(numArray.length/2)]; es más correcto para la parte else.

    – Mohsen Emami

    14/11/2021 a las 20:01

Avatar de usuario de Bruce Feist
bruce feist

Ordenar la matriz es innecesario e ineficiente. Hay una variación de QuickSort (Selección rápida) algoritmo que tiene un tiempo de ejecución promedio de O(n); si ordena primero, está en O (n log n). En realidad, encuentra el enésimo elemento más pequeño de una lista; para una mediana, solo usa n = la mitad de la longitud de la lista. Llamémoslo quickNth (lista, n).

El concepto es que para encontrar el enésimo más pequeño, elija un valor de ‘pivote’. (Exactamente cómo lo elige no es crítico; si sabe que los datos serán completamente aleatorios, puede tomar el primer elemento de la lista).

Divide la lista original en tres listas más pequeñas:

  • Uno con valores más pequeños que el pivote.
  • Uno con valores iguales al pivote.
  • Y uno con valores mayores que el pivote.

Entonces tienes tres casos:

  1. La lista “más pequeña” tiene >= n elementos. En ese caso, sabes que el enésimo más pequeño está en esa lista. Devuelve quickNth(menor, n).
  2. La lista más pequeña tiene = n elementos. En este caso, el n es igual a cualquier elemento de la lista “igual”; ya terminaste
  3. n es mayor que la suma de las longitudes de las listas más pequeñas e iguales. En ese caso, esencialmente puede omitir esos dos y ajustar n en consecuencia. Devuelve quickNth(mayor, n – longitud(menor) – longitud(igual)).

Hecho.

Si no está seguro de que los datos sean completamente aleatorios, debe ser más sofisticado al elegir el pivote. Tomar la mediana del primer valor de la lista, el último valor de la lista y el punto medio entre los dos funciona bastante bien.

Si tiene muy mala suerte con su elección de pivotes, y siempre elige el valor más pequeño o más alto como su pivote, esto toma O (n ^ 2) tiempo; eso es malo. Pero, también es muy poco probable si elige su pivote con un algoritmo decente.

Código de muestra:

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

  • Buena respuesta, pero un enlace a una implementación lo habría mejorado.

    – Nicolás

    04/03/2017 a las 17:45

  • Excelente idea. Edité el original para vincularlo a un código de muestra que escribí, usando ArrayLists en lugar de matrices.

    -Bruce Feist

    5 de marzo de 2017 a las 16:25


  • El código de muestra no está disponible. ¿Podrías insertar el código en la respuesta?

    – bobasti

    24/06/2020 a las 22:00

  • lo he hecho; gracias por avisarme que habia un problema.

    -Bruce Feist

    25 de junio de 2020 a las 2:09

Avatar de usuario de Aniket Kulkarni
Aniket Kulkarni

Si desea utilizar cualquier biblioteca externa aquí es biblioteca de matemáticas de apache commons usando puedes calcular el Mediana.
Para más métodos y usos, echa un vistazo a la documentación de la API

import org.apache.commons.math3.*;
.....
......
........
//calculate median
public double getMedian(double[] values){
 Median median = new Median();
 double medianValue = median.evaluate(values);
 return medianValue;
}
.......

Actualizar

Calcular en programa

Generalmente, la mediana se calcula utilizando las siguientes dos fórmulas dado aquí

Si n es impar, entonces Mediana (M) = valor del ((n + 1)/2) término del elemento.
Si n es par entonces Mediana (M) = valor de [((n)/2)th item term + ((n)/2 + 1)th item term ]/2

En tu programa tienes numArrayprimero necesita ordenar la matriz usando Matrices#ordenar

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;

  • Cambiaría una línea. median = numArray[middle-1] + Math.abs(numArray[middle-1] - numArray[middle] )/2; para dos medios suman más que int max casos

    – Unú

    8 de diciembre de 2013 a las 4:26


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

Avatar de usuario de Walls
Paredes

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

EDITAR: Inicialmente tenía medianB ajuste a middle+1 en las matrices de longitud uniforme, esto estaba mal debido a que las matrices comenzaban a contar en 0. Lo actualicé para usar middle-1 lo cual es correcto y debería funcionar correctamente para una matriz con una longitud uniforme.

  • No, eso no es correcto: para una entrada como [5, 6, 7, 10]su fragmento de código calcula que la mediana es (7+10)/2 mientras que debería ser (6+7)/2.

    – Hbf

    19 mayo 2013 a las 16:15

  • @Hbf tenías razón, vi el problema con el cálculo con una matriz uniforme y lo solucioné. Cambiando middle+1 a middle-1 en la lógica “par” debería arreglar la lógica correctamente.

    – Paredes

    20 de mayo de 2013 a las 13:13

  • errmmm… al usar esto en Java para Android, su cálculo uniforme aún no es del todo correcto. Por ejemplo: numArray es 1,2,3,4,7,7 y su código devolvería “3.0”, mientras que debería ser “3.5”. Para abordar esto, agregue “d” después del “2” para que su línea se lea: mediana = (medianaA + medianaB) / 2d; Esto asegura que los valores no se reduzcan a 3.0 Por cierto, esto también estaría bien: mediana = ((doble)(medianaA + medianaB) / 2);

    – usuario1207504

    25 de julio de 2013 a las 8:58


  • falta el caso donde length == 1 también

    usuario1382306

    17/03/2014 a las 19:21

Avatar de usuario de Abhijit Gaikwad
Abhijit Gaikwad

Puedes encontrar una buena explicación en https://www.youtube.com/watch?time_continue=23&v=VmogG01IjYc

La idea es usar 2 montones, a saber, un montón máximo y un montón medio.

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

}

  • No, eso no es correcto: para una entrada como [5, 6, 7, 10]su fragmento de código calcula que la mediana es (7+10)/2 mientras que debería ser (6+7)/2.

    – Hbf

    19 mayo 2013 a las 16:15

  • @Hbf tenías razón, vi el problema con el cálculo con una matriz uniforme y lo solucioné. Cambiando middle+1 a middle-1 en la lógica “par” debería arreglar la lógica correctamente.

    – Paredes

    20 de mayo de 2013 a las 13:13

  • errmmm… al usar esto en Java para Android, su cálculo uniforme aún no es del todo correcto. Por ejemplo: numArray es 1,2,3,4,7,7 y su código devolvería “3.0”, mientras que debería ser “3.5”. Para abordar esto, agregue “d” después del “2” para que su línea se lea: mediana = (medianaA + medianaB) / 2d; Esto asegura que los valores no se reduzcan a 3.0 Por cierto, esto también estaría bien: mediana = ((doble)(medianaA + medianaB) / 2);

    – usuario1207504

    25 de julio de 2013 a las 8:58


  • falta el caso donde length == 1 también

    usuario1382306

    17/03/2014 a las 19:21

avatar de usuario de mjgpy3
mjgpy3

Intente ordenar la matriz primero. Luego, después de que se ordena, si la matriz tiene una cantidad par de elementos, la media de los dos del medio es la mediana, si tiene un número impar, el elemento del medio es la mediana.

¿Ha sido útil esta solución?