En informática , el ordenamiento por conteo es un algoritmo para ordenar una colección de objetos según claves que son números enteros positivos pequeños ; es decir, es un algoritmo de ordenamiento de números enteros . Funciona contando el número de objetos que poseen valores de clave distintos y aplicando la suma de prefijos a esos conteos para determinar las posiciones de cada valor de clave en la secuencia de salida. Su tiempo de ejecución es lineal en el número de elementos y la diferencia entre el valor de clave máximo y el valor de clave mínimo, por lo que solo es adecuado para su uso directo en situaciones en las que la variación de claves no es significativamente mayor que el número de elementos. A menudo se utiliza como una subrutina en el ordenamiento por radix , otro algoritmo de ordenamiento, que puede manejar claves más grandes de manera más eficiente. [1] [2] [3]
El ordenamiento por conteo no es un ordenamiento por comparación ; utiliza valores clave como índices en una matriz y no se aplicará el límite inferior Ω ( n log n ) para el ordenamiento por comparación. [1] El ordenamiento por cubos se puede utilizar en lugar del ordenamiento por conteo, e implica un análisis de tiempo similar. Sin embargo, en comparación con el ordenamiento por conteo, el ordenamiento por cubos requiere listas enlazadas , matrices dinámicas o una gran cantidad de memoria preasignada para almacenar los conjuntos de elementos dentro de cada cubo, mientras que el ordenamiento por conteo almacena un solo número (el recuento de elementos) por cubo. [4]
En el caso más general, la entrada al método de ordenación por conteo consiste en una colección de n elementos, cada uno de los cuales tiene una clave entera no negativa cuyo valor máximo es como máximo k . [3] En algunas descripciones del método de ordenación por conteo, se supone que la entrada que se va a ordenar es simplemente una secuencia de enteros en sí misma, [1] pero esta simplificación no se adapta a muchas aplicaciones del método de ordenación por conteo. Por ejemplo, cuando se utiliza como una subrutina en el método de ordenación por radix , las claves para cada llamada al método de ordenación por conteo son dígitos individuales de claves de elementos más grandes; no sería suficiente devolver solo una lista ordenada de los dígitos de la clave, separados de los elementos.
En aplicaciones como la ordenación por base, se conocerá de antemano un límite para el valor máximo de la clave k y se puede suponer que forma parte de la entrada del algoritmo. Sin embargo, si el valor de k aún no se conoce, se puede calcular, como primer paso, mediante un bucle adicional sobre los datos para determinar el valor máximo de la clave.
La salida es una matriz de elementos ordenados por sus claves. Debido a su aplicación en la ordenación por radio, la ordenación por conteo debe ser una ordenación estable ; es decir, si dos elementos comparten la misma clave, su orden relativo en la matriz de salida y su orden relativo en la matriz de entrada deben coincidir. [1] [2]
En pseudocódigo, el algoritmo puede expresarse como:
función CountingSort(entrada, k ) contar ← matriz de k + 1 ceros salida ← matriz de la misma longitud que la entrada para i = 0 hasta longitud(entrada) - 1 hacer j = clave(entrada[ i ]) contar[ j ] = contar[ j ] + 1 para i = 1 a k hacer count[ i ] = count[ i ] + count[ i - 1] para i = longitud(entrada) - 1 hasta 0 hacer j = clave(entrada[ i ]) contar[ j ] = contar[ j ] - 1 salida[cuenta[ j ]] = entrada[ i ] salida de retorno
Aquí inputestá la matriz de entrada que se va a ordenar, keydevuelve la clave numérica de cada elemento en la matriz de entrada, countes una matriz auxiliar utilizada primero para almacenar los números de elementos con cada clave y luego (después del segundo bucle) para almacenar las posiciones donde se deben colocar los elementos con cada clave, kes el valor máximo de los valores de clave no negativos y outputes la matriz de salida ordenada.
En resumen, el algoritmo recorre los elementos del primer bucle y calcula un histograma del número de veces que aparece cada clave dentro de la inputcolección. Después, en el segundo bucle, realiza un cálculo de suma de prefijoscount para determinar, para cada clave, el rango de posiciones en el que deben colocarse los elementos que tienen esa clave; es decir, los elementos de la clave deben colocarse comenzando en la posición . Finalmente, en el tercer bucle, recorre nuevamente los elementos de , pero en orden inverso, moviendo cada elemento a su posición ordenada en la matriz. [1] [2] [3]count[]inputoutput
Aquí se conserva el orden relativo de los elementos con claves iguales, es decir, se trata de una clasificación estable .
Debido a que el algoritmo utiliza únicamente forbucles simples, sin recursión ni llamadas a subrutinas, es fácil de analizar. La inicialización de la matriz de conteo y el segundo bucle for que realiza una suma de prefijo en la matriz de conteo, cada uno itera como máximo k + 1 veces y, por lo tanto, toma O ( k ) tiempo. Los otros dos bucles for y la inicialización de la matriz de salida, cada uno toma O ( n ) tiempo. Por lo tanto, el tiempo para todo el algoritmo es la suma de los tiempos para estos pasos, O ( n + k ) . [1] [2]
Debido a que utiliza matrices de longitud k + 1 y n , el uso total de espacio del algoritmo también es O ( n + k ) . [1] Para instancias problemáticas en las que el valor máximo de la clave es significativamente menor que el número de elementos, la ordenación por conteo puede ser altamente eficiente en términos de espacio, ya que el único almacenamiento que utiliza además de sus matrices de entrada y salida es la matriz Count que utiliza espacio O ( k ) . [5]
Si cada elemento a ordenar es en sí mismo un entero, y también se usa como clave, entonces se pueden combinar el segundo y tercer bucle de ordenamiento por conteo; en el segundo bucle, en lugar de calcular la posición donde ise deben colocar los elementos con clave en la salida, simplemente se agregan Count[i]copias del número ia la salida.
Este algoritmo también puede utilizarse para eliminar claves duplicadas, reemplazando la Countmatriz por un vector de bits que almacena un onepara una clave que está presente en la entrada y un zeropara una clave que no está presente. Si además los elementos son las claves enteras en sí, tanto el segundo como el tercer bucle pueden omitirse por completo y el vector de bits servirá como salida, representando los valores como desplazamientos de las zeroentradas no duplicadas, sumadas al valor más bajo del rango. De este modo, las claves se ordenan y los duplicados se eliminan en esta variante simplemente colocándolos en la matriz de bits.
En el caso de datos en los que el tamaño máximo de la clave es significativamente menor que el número de elementos de datos, la ordenación por conteo se puede paralelizar dividiendo la entrada en submatrices de un tamaño aproximadamente igual, procesando cada submatriz en paralelo para generar una matriz de conteo separada para cada submatriz y luego fusionando las matrices de conteo. Cuando se utiliza como parte de un algoritmo de ordenación por radix paralelo, el tamaño de la clave (base de la representación por radix) debe elegirse para que coincida con el tamaño de las submatrices divididas. [6] La simplicidad del algoritmo de ordenación por conteo y su uso de la primitiva de suma de prefijo fácilmente paralelizable también lo hacen utilizable en algoritmos paralelos de grano más fino. [7]
Como se ha descrito, el ordenamiento por conteo no es un algoritmo in situ ; incluso sin tener en cuenta la matriz de conteo, necesita matrices de entrada y salida independientes. Es posible modificar el algoritmo para que coloque los elementos en orden ordenado dentro de la misma matriz que se le proporcionó como entrada, utilizando solo la matriz de conteo como almacenamiento auxiliar; sin embargo, la versión in situ modificada del ordenamiento por conteo no es estable. [3]
Aunque la ordenación por radix se remonta a mucho antes, la ordenación por conteo y su aplicación a la ordenación por radix fueron inventadas por Harold H. Seward en 1954. [1] [4] [8]
