Ordenar por conteo [1] ( ing. ordenar por contar [2] ; ordenar por contar [3] ing. ordenar por contar [4] ) es un algoritmo de clasificación que utiliza un rango de números de una matriz ordenada ( lista ) para contar los elementos coincidentes . El uso de la ordenación por conteo es útil solo cuando los números ordenados tienen (o se pueden asignar a) un rango de valores posibles que es lo suficientemente pequeño en comparación con el conjunto ordenado, por ejemplo, un millón de números naturales menores que 1000.
Supongamos que la matriz de entrada consta de números enteros en el rango de a , donde . Además, el algoritmo se generalizará para un rango de enteros arbitrario. Hay varias modificaciones del tipo de conteo, a continuación hay tres lineales y una cuadrática, que utiliza un enfoque diferente, pero tiene el mismo nombre.
Esta es la versión más simple del algoritmo. Cree una matriz auxiliar que C[0..k]consista en ceros, luego lea secuencialmente los elementos de la matriz de entrada , aumentando en uno Apara cada uno . Ahora es suficiente recorrer la matriz , para cada uno en la matriz , escriba secuencialmente el número j veces. A[i]C[A[i]]CAC[j]
Clasificación de conteo simple: para i = 0 a k C[yo] = 0; para i = 0 an - 1 C[A[i]] = C[A[i]] + 1; b = 0; para j = 0 a k para i = 0 a C[j] - 1 A[b] = j; segundo = segundo + 1;Implementación en C :
//matriz - puntero al principio de la matriz //n - tamaño de la matriz //k - número máximo en la matriz void countingSort ( int * array , int n , int k ) { int * c = ( int * ) malloc (( k + 1 ) * sizeof ( * array )); conjunto de memoria ( c , 0 , tamaño de ( * matriz ) * ( k + 1 )); para ( int yo = 0 ; yo < norte ; ++ yo ) { ++ c [ arreglo [ i ]]; } int b = 0 ; para ( int yo = 0 ; yo < k + 1 ; ++ yo ){ para ( int j = 0 ; j < c [ i ]; ++ j ) { arreglo [ b ++ ] = yo ; } } libre ( c ); }Implementación en C++ :
#incluir <vector> #incluir <tipo_rasgos> #incluye <algoritmo> template < typename std :: enable_if_t < std :: is_integral_v < T > , T >> void countingSort ( std :: vector < T > & array ) { T max = std :: max_element ( array .begin (), array .end ( ) ); conteo automático = std :: vector < T > ( max + 1 , T ( 0 )); para ( T elem : matriz ) ++ c [ elemento ]; Tb = 0 ; _ para ( tamaño_t i = 0 ; i < max + 1 ; ++ i ) { para ( T j = 0 ; j < cuenta [ i ]; ++ j ) { arreglo [ b ++ ] = yo ; } } }Esta variante ( clasificación de casilleros , clasificación por conteo ) se usa cuando la entrada es una matriz de estructuras de datos que deben clasificarse por claves ( key). Debe crear una matriz auxiliar C[0..k - 1], cada C[i]una contendrá más adelante una lista de elementos de la matriz de entrada. Luego lea secuencialmente los elementos del arreglo de entrada , agregando Acada uno a la lista . En conclusión, revise la matriz , para cada matriz , escriba secuencialmente los elementos de la lista . El algoritmo es estable . A[i]C[A[i].key]CAC[j]
ListCountingOrden para i = 0 a k - 1 C[i] = NULO; para i = 0 an - 1 C[A[i].clave].add(A[i]); b = 0; para j = 0 a k - 1 p = C[j]; mientras que p != NULL A[b] = p.datos; p = p.siguiente(); segundo = segundo + 1;En esta variante, además de la matriz de entrada, Ase requieren dos matrices auxiliares: C[0..k - 1]para el contador y B[0..n - 1]para la matriz ordenada. Primero, llene la matriz con Cceros, y para cada uno A[i]aumente C[A[i]]en 1. Luego, se cuenta la cantidad de elementos menores o iguales que . Para ello, cada , a partir de , se incrementa en . Por lo tanto, la última celda contendrá el número de elementos desde hasta existentes en la matriz de entrada. En el último paso del algoritmo, la matriz de entrada se lee desde el final, el valor se reduce en 1 y . El algoritmo es estable. C[j]C[1]C[j - 1]C[A[i]]B[C[A[i]]]A[i]
EstableRecuentoOrdenar para i = 0 a k - 1 C[yo] = 0; para i = 0 an - 1 C[A[i]] = C[A[i]] + 1; para j = 1 a k - 1 C[j] = C[j] + C[j - 1]; para i = n - 1 a 0 C[A[i]] = C[A[i]] - 1; B[C[A[i]]] = A[i];Surgen varias preguntas. ¿Qué pasa si el rango de valores (mínimo y máximo) no se conoce de antemano? ¿Qué pasa si el valor mínimo es mayor que cero o hay números negativos en los datos ordenados? La primera pregunta se puede resolver mediante una búsqueda lineal de min y max, que no afectará a las asintóticas del algoritmo. La segunda pregunta es algo más difícil. Si min es mayor que cero, entonces reste min de la matriz cuando trabaje con la matriz y agregue min cuando vuelva a escribir C. A[i]Si hay números negativos, debe Csumar A[i]cuando trabaje con una matriz |min|y restar cuando vuelva a escribir.
En los dos primeros algoritmos, los dos primeros bucles funcionan para y , respectivamente; ciclo doble para . En el tercer algoritmo, los ciclos toman , y , respectivamente. En total, los tres algoritmos tienen una complejidad de tiempo lineal . La memoria utilizada en los dos primeros algoritmos es , y en el tercero .
La ordenación por conteo también se conoce como un algoritmo ligeramente diferente. Utiliza una matriz de entrada Ay una matriz auxiliar Bpara el conjunto ordenado. En el algoritmo, para cada elemento de la matriz de entrada, A[i]cuente la cantidad de elementos menores que él y la cantidad de elementos iguales, pero antes ( ). asignar _ El algoritmo es estable. B[c]A[i]
CuadradoContandoOrdenar para i = 0 an - 1 c = 0; para j = 0 a i - 1 si A[j] <= A[i] c = c + 1; para j = i + 1 an - 1 si A[j] < A[i] c = c + 1; B[c] = A[i];Obviamente, la estimación de tiempo del algoritmo es , memoria .
Algoritmo sencillo.
PROCEDIMIENTO CountingSort ( VAR a : ARRAY OF INTEGER ; min , max : INTEGER ) ; VAR i , j , c : ENTERO ; b : PUNTERO A ARRAY DE ENTERO ; EMPIEZA A AFIRMAR ( min < = max ) ; NUEVO ( b , max - min + 1 ) ; FOR i := 0 TO LEN ( a ) - 1 DO INC ( b [ a [ i ] - min ]) END ; yo := 0 ; FOR j := min TO max DO c := b [ j - min ] ; MIENTRAS c > 0 HACER a [ i ] := j ; INC ( i ) ; DEC ( c ) END END END CountingSort ;Algoritmos de clasificación | |
---|---|
Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
Intercambio | |
Elección | |
Inserciones | |
fusión | |
sin comparaciones | |
híbrido | |
Otro | |
poco práctico |