Ordenar conteo

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 18 de enero de 2019; las comprobaciones requieren 29 ediciones .

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. $norte$ ${\ estilo de visualización 0}$ $k-1$ $k \in \mathbb norte$

Un algoritmo simple

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]]C ${\displaystyle j\in \{0,...,k\))$ AC[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 ; } } }

Algoritmo de lista

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]C $j \en \{0, ..., k - 1\}$ AC[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;

Algoritmo Robusto

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. $k-1$ C[j]C[1]C[j - 1] ${\ estilo de visualización 0}$ $k-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];

Generalización a un rango de enteros arbitrario

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.

Análisis

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 . $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n)$ $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n+k)$

Algoritmo de clasificación de conteo cuadrático

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. $c_{1}$ $c_{2}$ $c = c_1 + c_2$ 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];

Análisis

Obviamente, la estimación de tiempo del algoritmo es , memoria . ${\ estilo de visualización \ Theta (n^{2})}$ $\Theta(n)$

Ejemplos de implementación

Componente Pascal

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 ;

Implementación en PascalABC.Net

constante n = 20 _ empezar var a := ArrRandomInteger ( n , 0 , 100 ) ; un . Imprimir ; var max := a . máximo ; var c := | 0 | * ( máx . + 1 ) ; para var i := 0 a a . Longitud - 1 hacer c [ un [ yo ]] += 1 ; var j := 0 ; para var i := 0 a max do para var k := 1 to c [ i ] hacer empezar un [ j ] := yo ; j += 1 ; fin ; un . Imprimir ; fin _

Implementación en Python

a = lista ( mapa ( int , input () . split ())) # leer la lista cnt = [ 0 ] * ( max ( a ) + 1 ) # generar una lista de ceros con la longitud del máximo elemento de la lista a para el artículo en un : cnt [ item ] += 1 # cuando encontramos un número en la lista, aumenta su valor en 1 # agregar número de veces de conteo al resultado resultado = [ num para num , contar en enumerar ( cnt ) para i en rango ( contar )] print ( resultado ) # imprime la lista ordenada

Véase también

Notas

↑ Kormen. Clasificación por conteo // Algoritmos: Un curso introductorio. - Williams, 2014. - S. 71. - 208 p. — ISBN 978-5-8459-1868-0 .
↑ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. & Stein, Clifford (2001), 8.2 Counting Sort, Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill , p. 168–170, ISBN 0-262-03293-7 .
↑ Látigo. Ordenar por contar // El arte de programar. - T. 3. - S. 77.
↑ Knuth, D.E. (1998), Sección 5.2, Clasificación por conteo, El arte de la programación informática , Volumen 3: Clasificación y búsqueda (2.ª ed.), Addison-Wesley, p. 75-80, ISBN 0-201-89685-0 .

Literatura

Levitin A. V. Capítulo 7. Compromiso espacio-temporal: Clasificación de conteo // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 331-339. — 576 pág. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capítulo 8 Clasificación en Tiempo Lineal // Algoritmos: Construcción y Análisis = Introducción a los Algoritmos. — 2ª edición. - M .: "Williams" , 2005. - S. 224 - 226. - ISBN 5-8459-0857-4 .

Enlaces

Visualizer1 es un subprograma de Java.
Visualizer2 es un subprograma de Java.

Algoritmos de clasificación
Teoría	Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio	burbuja Emocionante enanos Rápido Peine Clasificación par-impar bit a bit
Elección	Elección Piramidal Suave
Inserciones	Inserciones cáscara árbol
fusión	fusión
sin comparaciones	Contando bloquear
híbrido	introsorteo Timsort
Otro	topológico redes bitón
poco práctico	Bogosort Tipo de títere tortita lento