logo

TechCodeview

Ordenación por conteo: tutoriales sobre estructuras de datos y algoritmos

¿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.

Encontrar el elemento máximo en inputArray[]



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.

Inicializar countArray[]

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[] .

Mantener el recuento de cada elemento en countArray[]

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.

Almacene la suma acumulada en countArray[]

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]] – -.

5

Paso 6: Para yo = 6 ,

cómo inventó la escuela

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

Colocar inputArray[6] en su posición correcta en outputArray[]

Paso 7: Para i = 5 ,

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

Colocar inputArray[5] en su posición correcta en outputArray[]

Paso 8: Para yo = 4 ,

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

Colocar inputArray[4] en su posición correcta en outputArray[]

Paso 9: Para yo = 3 ,

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

Colocar inputArray[3] en su posición correcta en outputArray[]

Paso 10: Para yo = 2 ,

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

Colocar inputArray[2] en su posición correcta en outputArray[]

Paso 11: Para yo = 1 ,

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

Colocar inputArray[1] en su posición correcta en outputArray[]

Paso 12: Para yo = 0,

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

Colocar inputArray[0] en su posición correcta en outputArray[]

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>

tipo de columna de cambio de mysql 

>

>

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.