Mediana y moda usando la ordenación por conteo

Posted on by Rudeus Greyrat

Dada una array no clasificada de tamaño n , encuentre la mediana y la moda usando la técnica de clasificación por conteo . Esto puede ser útil cuando los elementos de la array están en un rango limitado.

Ejemplos:

Input : array a[] = {1, 1, 1, 2, 7, 1}
Output : Mode = 1
         Median = 1
Note: Median is average of middle two numbers (1 and 1)

Input : array a[] = {9, 9, 9, 9, 9}
Output : Mode = 9
         Median = 9

Prerrequisitos: Clasificación de conteo , Mediana de la array , Moda ( elemento más frecuente en la array )

Entrada = [1, 4, 1, 2, 7, 1, 2, 5, 3, 6]

1. Array auxiliar (recuento) antes de sumar sus recuentos anteriores, c[]:
Índice: 0 1 2 3 4 5 6 7 8 9 10
recuento: 0 3 2 1 1 1 1 1 0 0 0

2. Moda = índice con valor máximo de cuenta.
Modo = 1 (para el ejemplo anterior)

3. La array de conteo se modifica de manera similar a como se hace al realizar la ordenación de conteo.
Índice: 0 1 2 3 4 5 6 7 8 9 10
cuenta: 0 3 5 6 7 8 9 10 10 10 10

4. La array de salida se calcula normalmente como en el tipo de recuento, b[]:
array de salida b[] = {1, 1, 1, 2, 2, 3, 4, 5, 6, 7}

5. Si el tamaño de la array b[] es impar, Mediana = b[n/2] De lo contrario,
Mediana = (b[(n-1)/2] + b[n/2])/2

6. Para el ejemplo anterior, el tamaño de b[] es par, por lo tanto, mediana = (b[4] + b[5])/2.
Mediana = (2 + 3)/2 = 2,5

Enfoque básico a seguir:
Suponiendo que el tamaño de la array de entrada es n :
Paso 1: Tome la array de conteo antes de sumar sus conteos anteriores en el siguiente índice.
Paso 2: El índice con el valor máximo almacenado es el modo de los datos dados.
Paso 3: en caso de que haya más de un índice con un valor máximo, todos son resultados para el modo, por lo que podemos tomar cualquiera.
Paso 4: almacene el valor en ese índice en una variable separada llamada modo.
Paso 5: Continúe con el procesamiento normal de la ordenación por conteo.
Paso 6: en la array resultante (ordenada), si n es impar, entonces mediana = elemento más central de la
array ordenada, y si n es incluso la mediana = promedio de los dos elementos más intermedios de la array ordenada.
Paso 7: almacene el resultado en una variable separada llamada mediana.

La siguiente es la implementación del problema discutido anteriormente:

    C++

    // C++ Program for Mode and
    // Median using Counting
    // Sort technique
    #include <bits/stdc++.h>
    using namespace std;
      
    // function that sort input array a[] and 
    // calculate mode and median using counting
    // sort.
    void printModeMedian(int a[], int n)
    {
        // The output array b[] will
        // have sorted array
        int b[n];
      
        // variable to store max of
        // input array which will 
        // to have size of count array
        int max = *max_element(a, a+n);
      
        // auxiliary(count) array to 
        // store count. Initialize
        // count array as 0. Size
        // of count array will be
        // equal to (max + 1).
        int t = max + 1;
        int count[t];
        for (int i = 0; i < t; i++)
            count[i] = 0;    
      
        // Store count of each element
        // of input array
        for (int i = 0; i < n; i++)
            count[a[i]]++;    
          
        // mode is the index with maximum count
        int mode = 0;
        int k = count[0];
        for (int i = 1; i < t; i++)
        {
            if (count[i] > k)
            {
                k = count[i];
                mode = i;
            }
        }    
      
        // Update count[] array with sum
        for (int i = 1; i < t; i++)
            count[i] = count[i] + count[i-1];
      
        // Sorted output array b[]
        // to calculate median
        for (int i = 0; i < n; i++)
        {
            b[count[a[i]]-1] = a[i];
            count[a[i]]--;
        }
          
        // Median according to odd and even 
        // array size respectively.
        float median;
        if (n % 2 != 0)
            median = b[n/2];
        else
            median = (b[(n-1)/2] + 
                      b[(n/2)])/2.0;
          
        // Output the result 
        cout << "median = " << median << endl;
        cout << "mode = " << mode;
    }
      
    // Driver program
    int main()
    {
        int a[] = { 1, 4, 1, 2, 7, 1, 2,  5, 3, 6 };
        int n = sizeof(a)/sizeof(a[0]);
        printModeMedian(a, n);
        return 0;
    }

    Java

    import java.util.Arrays;
      
    // Java Program for Mode and 
    // Median using Counting 
    // Sort technique 
    class GFG 
    {
    // function that sort input array a[] and 
    // calculate mode and median using counting 
    // sort. 
      
        static void printModeMedian(int a[], int n) 
        {
            // The output array b[] will 
            // have sorted array 
            int[] b = new int[n];
      
            // variable to store max of 
            // input array which will 
            // to have size of count array 
            int max = Arrays.stream(a).max().getAsInt();
      
            // auxiliary(count) array to 
            // store count. Initialize 
            // count array as 0. Size 
            // of count array will be 
            // equal to (max + 1). 
            int t = max + 1;
            int count[] = new int[t];
            for (int i = 0; i < t; i++)
            {
                count[i] = 0;
            }
      
            // Store count of each element 
            // of input array 
            for (int i = 0; i < n; i++)
            {
                count[a[i]]++;
            }
      
            // mode is the index with maximum count 
            int mode = 0;
            int k = count[0];
            for (int i = 1; i < t; i++) 
            {
                if (count[i] > k)
                {
                    k = count[i];
                    mode = i;
                }
            }
      
            // Update count[] array with sum 
            for (int i = 1; i < t; i++)
            {
                count[i] = count[i] + count[i - 1];
            }
      
            // Sorted output array b[] 
            // to calculate median 
            for (int i = 0; i < n; i++) 
            {
                b[count[a[i]] - 1] = a[i];
                count[a[i]]--;
            }
      
            // Median according to odd and even 
            // array size respectively. 
            float median;
            if (n % 2 != 0) 
            {
                median = b[n / 2];
            }
            else
            {
                median = (float) ((b[(n - 1) / 2]
                        + b[(n / 2)]) / 2.0);
            }
      
            // Output the result 
            System.out.println("median = " + median);
            System.out.println("mode = " + mode);
        }
      
    // Driver program 
    public static void main(String[] args)
    {
        int a[] = {1, 4, 1, 2, 7, 1, 2, 5, 3, 6};
        int n = a.length;
        printModeMedian(a, n);
      
    }
    }
      
    // This code is contributed by 29AjayKumar

    Python3

    # Python3 program for Mode and Median 
    # using Counting Sort technique 
      
    # Function that sort input array a[] and 
    # calculate mode and median using counting sort 
    def printModeMedian(a, n):
      
        # The output array b[] will 
        # have sorted array
        b = [0] * n 
      
        # Variable to store max of input array
        # which will to have size of count array 
        Max = max(a)
      
        # Auxiliary(count) array to store count.
        # Initialize count array as 0. Size of
        # count array will be equal to (max + 1).
        t = Max + 1
        count = [0] * t
      
        # Store count of each element 
        # of input array 
        for i in range(n):
            count[a[i]] += 1
      
        # Mode is the index with maximum count 
        mode = 0
        k = count[0]
          
        for i in range(1, t):
            if (count[i] > k):
                k = count[i]
                mode = i 
      
        # Update count[] array with sum
        for i in range(1, t):
            count[i] = count[i] + count[i - 1]
      
        # Sorted output array b[] 
        # to calculate median 
        for i in range(n):
            b[count[a[i]] - 1] = a[i]
            count[a[i]] -= 1
      
        # Median according to odd and even 
        # array size respectively.
        median = 0.0
        if (n % 2 != 0):
            median = b[n // 2]
        else:
            median = ((b[(n - 1) // 2] + 
                       b[n // 2]) / 2.0)
      
        # Output the result
        print("median =", median)
        print("mode =", mode)
      
    # Driver Code
    if __name__ == '__main__':
      
        arr = [ 1, 4, 1, 2, 7, 1, 2, 5, 3, 6]
        n = len(arr)
      
        printModeMedian(arr, n)
          
    # This code is contributed by himanshu77

    C#

    // C# Program for Mode and 
    // Median using Counting 
    // Sort technique 
    using System;
    using System.Linq;
      
    class GFG 
    {
        // function that sort input array a[] and 
        // calculate mode and median using counting 
        // sort. 
        static void printModeMedian(int []a, int n) 
        {
            // The output array b[] will 
            // have sorted array 
            int[] b = new int[n];
      
            // variable to store max of 
            // input array which will 
            // to have size of count array 
            int max = a.Max();
      
            // auxiliary(count) array to 
            // store count. Initialize 
            // count array as 0. Size 
            // of count array will be 
            // equal to (max + 1). 
            int t = max + 1;
            int []count = new int[t];
            for (int i = 0; i < t; i++)
            {
                count[i] = 0;
            }
      
            // Store count of each element 
            // of input array 
            for (int i = 0; i < n; i++)
            {
                count[a[i]]++;
            }
      
            // mode is the index with maximum count 
            int mode = 0;
            int k = count[0];
            for (int i = 1; i < t; i++) 
            {
                if (count[i] > k)
                {
                    k = count[i];
                    mode = i;
                }
            }
      
            // Update count[] array with sum 
            for (int i = 1; i < t; i++)
            {
                count[i] = count[i] + count[i - 1];
            }
      
            // Sorted output array b[] 
            // to calculate median 
            for (int i = 0; i < n; i++) 
            {
                b[count[a[i]] - 1] = a[i];
                count[a[i]]--;
            }
      
            // Median according to odd and even 
            // array size respectively. 
            float median;
            if (n % 2 != 0) 
            {
                median = b[n / 2];
            }
            else
            {
                median = (float) ((b[(n - 1) / 2] + 
                                   b[(n / 2)]) / 2.0);
            }
      
            // Output the result 
            Console.WriteLine("median = " + median);
            Console.WriteLine("mode = " + mode);
        }
      
    // Driver Code
    public static void Main(String[] args)
    {
        int []a = {1, 4, 1, 2, 7, 1, 2, 5, 3, 6};
        int n = a.Length;
        printModeMedian(a, n);
    }
    }
      
    // This code is contributed by Rajput-Ji

    PHP

    <?php
    // PHP Program for Mode and Median using 
    // Counting Sort technique
      
    // Function that sort input array a[] and 
    // calculate mode and median using counting
    // sort.
    function printModeMedian($a, $n)
    {
        // The output array b[] will
        // have sorted array
        $b[$n] = array();
      
        // variable to store max of input 
        // array which will to have size 
        // of count array
        $max = max($a);
      
        // auxiliary(count) array to store 
        // count. Initialize count array as 
        // 0. Size of count array will be
        // equal to (max + 1).
        $t = $max + 1;
        $count[$t] = array();
        for ($i = 0; $i < $t; $i++)
            $count[$i] = 0; 
      
        // Store count of each element
        // of input array
        for ($i = 0; $i < $n; $i++)
            $count[$a[$i]]++; 
          
        // mode is the index with maximum count
        $mode = 0;
        $k = $count[0];
        for ($i = 1; $i < $t; $i++)
        {
            if ($count[$i] > $k)
            {
                $k = $count[$i];
                $mode = $i;
            }
        } 
      
        // Update count[] array with sum
        for ($i = 1; $i < $t; $i++)
            $count[$i] = $count[$i] + $count[$i - 1];
      
        // Sorted output array b[]
        // to calculate median
        for ($i = 0; $i < $n; $i++)
        {
            $b[$count[$a[$i]] - 1] = $a[$i];
            $count[$a[$i]]--;
        }
          
        // Median according to odd and even 
        // array size respectively.
        $median;
        if ($n % 2 != 0)
            $median = $b[$n / 2];
        else
            $median = ($b[($n - 1) / 2] + 
                       $b[($n / 2)]) / 2.0;
          
        // Output the result 
        echo "median = ", $median, "\n" ;
        echo "mode = " , $mode;
    }
      
    // Driver Code
    $a = array( 1, 4, 1, 2, 7, 
                1, 2, 5, 3, 6 );
    $n = sizeof($a);
    printModeMedian($a, $n);
      
    // This code is contributed by jit_t
    ?>
    Producción:

    median = 2.5
mode = 1

Complejidad de tiempo = O(N + P), donde N es el tiempo para la array de entrada y P es el tiempo para la array de conteo.
Complejidad espacial = O(P), donde P es el tamaño de la array auxiliar.

Publicación traducida automáticamente

Artículo escrito por akanshgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *