Clasificación de conteo

En informática, ordenar por conteo es un algoritmo para clasificar una colección de objetos según claves que son pequeños enteros positivos; es decir, es un algoritmo de clasificación de enteros. Funciona contando el número de objetos que poseen valores clave distintos y aplicando la suma de prefijos en esos recuentos para determinar las posiciones de cada valor 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 uso directo en situaciones donde la variación de claves no es significativamente mayor que el número de elementos. A menudo se usa como una subrutina en la clasificación radix, otro algoritmo de clasificación, que puede manejar claves más grandes de manera más eficiente.

La ordenación por conteo no es una ordenación por comparación; utiliza valores clave como índices en una matriz y el límite inferior Ω(n log n) para la clasificación de comparación no aplicar. La clasificación por cubetas se puede utilizar en lugar de la clasificación por conteo, e implica un análisis de tiempo similar. Sin embargo, en comparación con la ordenación por conteo, la ordenación por cubos requiere listas vinculadas, matrices dinámicas o una gran cantidad de memoria preasignada para contener los conjuntos de elementos dentro de cada cubo, mientras que la ordenación por conteo almacena un solo número (el conteo de elementos) por cubo..

Supuestos de entrada y salida

En el caso más general, la entrada para la ordenación por conteo consta de una colección de n elementos, cada uno de los cuales tiene un clave entera no negativa cuyo valor máximo es como mucho k. En algunas descripciones de clasificación por conteo, se supone que la entrada que se va a clasificar es más simplemente una secuencia de enteros en sí misma, pero esta simplificación no se adapta a muchas aplicaciones de clasificación por conteo. Por ejemplo, cuando se usa como una subrutina en la ordenación por base, las claves para cada llamada a la 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 clave, separados de los elementos.

En aplicaciones como la ordenación radix, un límite en el valor de clave máximo k se conocerá de antemano y puede se supone que es parte de la entrada al algoritmo. Sin embargo, si el valor de k aún no se conoce, puede calcularse, como primer paso, mediante un bucle adicional los datos para determinar el valor máximo de la clave.

La salida es una matriz de los elementos ordenados por sus claves. Debido a su aplicación a la clasificación radix, la clasificación por conteo debe ser una clasificació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.

Pseudocódigo

En pseudocódigo, el algoritmo se puede expresar como:

función CountingSort(input, k)

cuenta ← array de k + 1 ceros
producción ← array de la misma longitud que la entrada

 para i = 0 a longitud(input) - 1 do j = clave(input[i])
Conteo[jConteoj+ 1

 para i = 1 a k doConteo[iConteoi+ cuentai - 1]

 para i = longitud(input) - 1 abajo 0 do j = clave(input[i])
Conteo[jConteoj1
producción[contable[j]] = entrada [i]

 retorno Producto

Aquí input es la matriz de entrada que se ordenará, key devuelve la clave numérica de cada elemento en la matriz de entrada, count es una matriz auxiliar utilizada primero para almacenar el número de elementos con cada tecla, y luego (después del segundo bucle) para almacenar las posiciones donde se deben colocar los elementos con cada tecla, k es el valor máximo de los valores clave no negativos y output es la matriz de salida ordenada.

En resumen, los bucles de algoritmo sobre los elementos en el primer bucle, computando un histograma del número de veces que cada clave ocurre dentro del input colección. Después de eso en el segundo bucle, realiza una suma prefijo computación en count con el fin de determinar, para cada clave, el rango de posición donde se deben colocar los elementos con esa clave; es decir, los elementos clave ${displaystyle i}$ debe colocarse a partir de la posición count[${displaystyle i}$]. Finalmente, en el tercer lazo, se agita sobre los elementos de input de nuevo, pero en orden inverso, moviendo cada artículo en su posición ordenada en el output array.

Aquí se conserva el orden relativo de los elementos con claves iguales; es decir, este es un tipo estable.

Análisis de complejidad

Debido a que el algoritmo utiliza solo bucles for simples, sin recursividad ni llamadas a subrutinas, es fácil de analizar. La inicialización de la matriz de conteo y el segundo ciclo for que realiza una suma de prefijo en la matriz de conteo, cada iteración como máximo k + 1 veces y por lo tanto, tome O(k) tiempo. Los otros dos bucles for y la inicialización de la matriz de salida toman cada uno O(n) tiempo. Por lo tanto, el tiempo de todo el algoritmo es la suma de los tiempos de estos pasos, O(n + k).

Porque utiliza matrices de longitud k + 1 y n, el uso de espacio total del algoritmo también es O(n + k). Para las instancias problemáticas en las que el valor máximo de la clave es significativamente menor que la cantidad de elementos, la ordenación por conteo puede ser muy eficiente en cuanto al espacio, ya que el único almacenamiento que utiliza, además de sus matrices de entrada y salida, es la matriz Count, que utiliza el espacio O(k).

Algoritmos variantes

Si cada elemento a ordenar es en sí mismo un número entero, y también se usa como clave, entonces se pueden combinar el segundo y el tercer ciclo de ordenamiento por conteo; en el segundo bucle, en lugar de calcular la posición en la que deben colocarse los elementos con la clave i en la salida, simplemente agregue Count[i] copias del número i a la salida.

Este algoritmo también se puede usar para eliminar claves duplicadas, al reemplazar la matriz Count con un vector de bits que almacena un one para una clave que está presente en la entrada y un cero para una clave que no está presente. Si, además, los elementos son las propias claves enteras, tanto el segundo como el tercer bucle se pueden omitir por completo y el vector de bits servirá como salida, representando los valores como compensaciones de las entradas distintas de zero, añadidas a el valor más bajo del rango. Así, las claves se ordenan y los duplicados se eliminan en esta variante simplemente colocándolos en la matriz de bits.

Para los datos en los que el tamaño máximo de la clave es significativamente más pequeño que la cantidad de elementos de datos, la ordenación de conteo se puede paralelizar dividiendo la entrada en subarreglos de aproximadamente el mismo tamaño, procesando cada subarreglo en paralelo para generar un arreglo de conteo separado para cada uno. subarreglo, y luego fusionar los arreglos de conteo. Cuando se utiliza como parte de un algoritmo de clasificación de base paralelo, el tamaño de la clave (base de la representación de base) debe elegirse para que coincida con el tamaño de los subarreglos divididos. La simplicidad del algoritmo de clasificación de conteo y su uso de la primitiva de suma de prefijo fácilmente paralelizable también lo hacen utilizable en algoritmos paralelos más detallados.

Como se describe, la ordenación por conteo no es un algoritmo en el lugar; incluso sin tener en cuenta la matriz de conteo, necesita matrices de entrada y salida separadas. 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 de ordenación por conteo no es estable.

Historia

Aunque la clasificación de radix en sí es mucho más antigua, la clasificación por conteo y su aplicación a la clasificación radix fueron inventadas por Harold H. Seward en 1954.