¿Qué es la clasificación por conteo?

Ordenar contando es un no basado en comparación Algoritmo de clasificación que funciona bien cuando hay un rango limitado de valores de entrada. Es particularmente eficiente cuando el rango de valores de entrada es pequeño en comparación con la cantidad de elementos a ordenar. La idea básica detrás Ordenar contando es contar el frecuencia de cada elemento distinto en la matriz de entrada y usar esa información para colocar los elementos en sus posiciones ordenadas correctas.

¿Cómo funciona el algoritmo de clasificación por conteo?

Paso 1 :

• Descubra el máximo elemento de la matriz dada.

Paso 2:

• Inicializar un contarmatriz[] de longitud máx+1 con todos los elementos como 0 . Esta matriz se utilizará para almacenar las apariciones de los elementos de la matriz de entrada.

Paso 3:

• En el contarmatriz[] , almacena el recuento de cada elemento único de la matriz de entrada en sus respectivos índices.
• Por ejemplo: El recuento de elementos. 2 en la matriz de entrada es 2. entonces, tienda 2 en el índice 2 en el contarmatriz[] . De manera similar, el recuento de elementos 5 en la matriz de entrada es 1 , por lo tanto almacenar 1 en el índice 5 en el contarmatriz[] .

Etapa 4:

• Guarde el suma acumulada o suma de prefijo de los elementos del contarmatriz[] haciendo contarArray[i] = contarArray[i – 1] + contarArray[i]. Esto ayudará a colocar los elementos de la matriz de entrada en el índice correcto en la matriz de salida.

Paso 5:

• Iterar desde el final de la matriz de entrada y debido a que atravesar la matriz de entrada desde el final conserva el orden de los elementos iguales, lo que eventualmente hace que este algoritmo de clasificación estable .

• Actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[i]] – 1] = matrizdeentrada[i] .
• Además, actualiza countArray[entradaArray[i]] = matrizContar[matrizEntrada[i]] – -.

Paso 6: Para yo = 6 ,

Actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[6]] – 1] = matrizdeentrada[6]
Además, actualiza countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

Paso 7: Para i = 5 ,

Actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[5]] – 1] = matrizdeentrada[5]
Además, actualiza countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

Paso 8: Para yo = 4 ,

Actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[4]] – 1] = matrizdeentrada[4]
Además, actualiza countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

Paso 9: Para yo = 3 ,

Actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[3]] – 1] = matrizdeentrada[3]
Además, actualiza countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

Paso 10: Para yo = 2 ,

Actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[2]] – 1] = matrizdeentrada[2]
Además, actualiza countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

Paso 11: Para yo = 1 ,

Actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[1]] – 1] = matrizdeentrada[1]
Además, actualiza countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Paso 12: Para yo = 0,

Actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[0]] – 1] = matrizdeentrada[0]
Además, actualiza countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Algoritmo de clasificación de conteo:

• Declarar una matriz auxiliar contarmatriz[] de tamaño máx(matriz de entrada[])+1 e inicializarlo con 0 .
• matriz transversal matriz de entrada[] y mapear cada elemento de matriz de entrada[] como índice de contarmatriz[] matriz, es decir, ejecutar countArray[inputArray[i]]++ para 0 <= yo < norte .
• Calcule la suma del prefijo en cada índice de la matriz matriz de entrada [].
• Crear una matriz matriz de salida[] de tamaño norte .
• matriz transversal matriz de entrada[] desde el final y actualizar matrizdesalida[matrizdecuenta[matrizdeentrada[i]] – 1] = matrizdeentrada[i] . Además, actualiza countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

A continuación se muestra la implementación del algoritmo anterior:

Java

import> java.util.Arrays;> public> class> CountSort {> > public> static> int> [] countSort(> int> [] inputArray) {> > int> N = inputArray.length;> > int> M => 0> ;> > for> (> int> i => 0> ; i M = Math.max(M, inputArray[i]); } int[] countArray = new int[M + 1]; for (int i = 0; i countArray[inputArray[i]]++; } for (int i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } int[] outputArray = new int[N]; for (int i = N - 1; i>= 0; i--) { matriz de salida[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } devolver matriz de salida; } public static void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9}; int[] matrizSalida = countSort(matrizentrada); for (int i = 0; i System.out.print(outputArray[i] + ' '); } } }>

C#

using> System;> using> System.Collections.Generic;> class> GFG> {> > static> List <> int> >ContarOrdenar(Lista <> int> >matriz de entrada)> > {> > int> N = inputArray.Count;> > // Finding the maximum element of the array inputArray[].> > int> M = 0;> > for> (> int> i = 0; i M = Math.Max(M, inputArray[i]); // Initializing countArray[] with 0 List countArray = nueva lista (nuevo int[M + 1]); // Mapeando cada elemento de inputArray[] como un índice // de la matriz countArray[] for (int i = 0; i countArray[inputArray[i]]++; // Calculando la suma del prefijo en cada índice // de la matriz countArray [] para (int i = 1; i <= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List matriz de salida = nueva lista (nuevo int[N]); for (int i = N - 1; i>= 0; i--) { arraysalida[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } devolver matriz de salida; } // Código del controlador static void Main() { // Lista de matriz de entrada inputArray = nueva lista { 4, 3, 12, 1, 5, 5, 3, 9 }; // Lista de matriz de salida matrizdesalida = CountSort(matrizdeentrada); for (int i = 0; i Console.Write(outputArray[i] + ' '); Console.WriteLine(); } }>

JavaScript

function> countSort(inputArray) {> > const N = inputArray.length;> > // Finding the maximum element of inputArray> > let M = 0;> > for> (let i = 0; i M = Math.max(M, inputArray[i]); } // Initializing countArray with 0 const countArray = new Array(M + 1).fill(0); // Mapping each element of inputArray as an index of countArray for (let i = 0; i countArray[inputArray[i]]++; } // Calculating prefix sum at every index of countArray for (let i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } // Creating outputArray from countArray const outputArray = new Array(N); for (let i = N - 1; i>= 0; i--) { matriz de salida[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } devolver matriz de salida; } // Código del controlador const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Ordenar la matriz de entrada const outputArray = countSort(inputArray); // Imprimiendo la matriz ordenada console.log(outputArray.join(' ')); //Este código es aportado por Utkarsh>

C++14

#include> using> namespace> std;> vector <> int> >contarOrdenar(vector <> int> >& matriz de entrada)> {> > int> N = inputArray.size();> > // Finding the maximum element of array inputArray[].> > int> M = 0;> > for> (> int> i = 0; i M = max(M, inputArray[i]); // Initializing countArray[] with 0 vector contarArray(M + 1, 0); // Mapeando cada elemento de inputArray[] como un índice // de la matriz countArray[] for (int i = 0; i countArray[inputArray[i]]++; // Calculando la suma del prefijo en cada índice // de la matriz countArray [] para (int i = 1; i <= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector matriz de salida(N); for (int i = N - 1; i>= 0; i--) { arraysalida[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } devolver matriz de salida; } // Código del controlador int main() { // Vector de matriz de entrada matriz de entrada = { 4, 3, 12, 1, 5, 5, 3, 9 }; // vector de matriz de salida matrizdesalida = countSort(matrizdeentrada); para (int i = 0; i cout < < outputArray[i] < < ' '; return 0; }>

Python3

def> count_sort(input_array):> > # Finding the maximum element of input_array.> > M> => max> (input_array)> > # Initializing count_array with 0> > count_array> => [> 0> ]> *> (M> +> 1> )> > # Mapping each element of input_array as an index of count_array> > for> num> in> input_array:> > count_array[num]> +> => 1> > # Calculating prefix sum at every index of count_array> > for> i> in> range> (> 1> , M> +> 1> ):> > count_array[i]> +> => count_array[i> -> 1> ]> > # Creating output_array from count_array> > output_array> => [> 0> ]> *> len> (input_array)> > for> i> in> range> (> len> (input_array)> -> 1> ,> -> 1> ,> -> 1> ):> > output_array[count_array[input_array[i]]> -> 1> ]> => input_array[i]> > count_array[input_array[i]]> -> => 1> > return> output_array> # Driver code> if> __name__> => => '__main__'> :> > # Input array> > input_array> => [> 4> ,> 3> ,> 12> ,> 1> ,> 5> ,> 5> ,> 3> ,> 9> ]> > # Output array> > output_array> => count_sort(input_array)> > for> num> in> output_array:> > print> (num, end> => ' '> )>

Producción

1 3 3 4 5 5 9 12 

Análisis de complejidad del ordenamiento por conteo:

• Complejidad del tiempo : O(N+M), donde norte y METRO son del tamaño de matriz de entrada[] y contarmatriz[] respectivamente.
  • Peor de los casos: O(N+M).
  • Caso promedio: O (N+M).
  • Mejor caso: O(N+M).
• Espacio Auxiliar: O(N+M), donde norte y METRO son el espacio ocupado por matriz de salida[] y contarmatriz[] respectivamente.

Ventaja de la clasificación por conteo:

• La clasificación por conteo generalmente funciona más rápido que todos los algoritmos de clasificación basados ​​en comparación, como la clasificación por combinación y la clasificación rápida, si el rango de entrada es del orden del número de entradas.
• La clasificación por conteo es fácil de codificar
• La clasificación por conteo es una algoritmo estable .

Desventaja de ordenar por conteo:

• La ordenación por conteo no funciona con valores decimales.
• La ordenación por conteo es ineficiente si el rango de valores a ordenar es muy grande.
• La clasificación por conteo no es una Clasificación in situ algoritmo, utiliza espacio adicional para ordenar los elementos de la matriz.