Hispanopedia Wiki
Articulo de referencia

Clasificación por conteo

O(n+k) , where k is the range of the non-negative key values."},"space":{"wt":" O(n+k) "}},"i":0}}]}"> En informática , el ordenamiento por conteo es un algoritmo para ordenar u...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , el ordenamiento por conteo es un algoritmo para ordenar una colección de objetos según claves que son enteros positivos pequeños ; es decir, es un algoritmo de ordenamiento de 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 la posición de cada valor de clave en la secuencia de salida. Su tiempo de ejecución es lineal con respecto al número de elementos y la diferencia entre el valor máximo y el mínimo de la clave, por lo que solo es adecuado para su uso directo en situaciones donde la variación en las claves no es significativamente mayor que el número de elementos. A menudo se utiliza como 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 un arreglo y el límite inferior Ω ( n log n ) para el ordenamiento por comparación no se aplica. [ 1 ] El ordenamiento por cubetas puede usarse 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 cubetas requiere listas enlazadas , arreglos dinámicos o una gran cantidad de memoria preasignada para almacenar los conjuntos de elementos dentro de cada cubeta, mientras que el ordenamiento por conteo almacena un solo número (el recuento de elementos) por cubeta. [ 4 ]

Supuestos de entrada y salida

En el caso más general, la entrada para el ordenamiento 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 ordenamiento por conteo, se supone que la entrada a ordenar es más simplemente una secuencia de enteros, [ 1 ] pero esta simplificación no se adapta a muchas aplicaciones del ordenamiento por conteo. Por ejemplo, cuando se usa como subrutina en el ordenamiento por radix , las claves para cada llamada al ordenamiento por conteo son dígitos individuales de las claves de elementos más grandes; no bastaría con devolver solo una lista ordenada de los dígitos de la clave, separados de los elementos.

En aplicaciones como la ordenación por radix, se conoce de antemano un límite para el valor máximo de la clave k , que puede considerarse parte de la entrada del algoritmo. Sin embargo, si el valor de k no se conoce previamente, puede calcularse, 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 los elementos ordenados por sus claves. Debido a su aplicación a la ordenación por radix, 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 ]

Pseudocódigo

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

función CountingSort(input, k ) es recuento ← matriz de k + 1 ceros salida ← matriz de la misma longitud que la entrada para i = 0 hasta length(input) - 1 hacer j = key(input[ i ]) recuento[ j ] = recuento[ 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 ]) recuento[ j ] = recuento[ j ] - 1 salida[contador[ j ]] = entrada[ i ] devolver salida

Donde inputes el array que se va a ordenar, keydevuelve la clave numérica de cada elemento en el array de entrada, countes un array auxiliar que se utiliza 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 el array de salida ordenado.

En resumen, el algoritmo itera sobre los elementos en el primer bucle, calculando 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 posición donde deben colocarse los elementos que tienen esa clave; es decir, elementos de clavei{\displaystyle i}debe colocarse comenzando en la posición . Finalmente, en el tercer bucle, vuelve a iterar sobre los elementos de , pero en orden inverso, moviendo cada elemento a su posición ordenada en el array. [ 1 ] [ 2 ] [ 3 ]count[i{\displaystyle i}]inputoutput

Aquí se conserva el orden relativo de los elementos con claves iguales; es decir, se trata de una ordenación estable .

Análisis de complejidad

Debido a que el algoritmo utiliza solo forbucles simples, sin recursión ni llamadas a subrutinas, su análisis es sencillo. La inicialización del arreglo de conteo y el segundo bucle for, que realiza una suma prefija sobre dicho arreglo, se ejecutan como máximo k + 1 veces y, por lo tanto, requieren un tiempo de O ( k ) . Los otros dos bucles for y la inicialización del arreglo de salida requieren un tiempo de O ( n ) cada uno . Por consiguiente, el tiempo total del algoritmo es la suma de los tiempos de 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 de problemas 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 cuanto a espacio, ya que el único almacenamiento que utiliza aparte de sus matrices de entrada y salida es la matriz Count que utiliza espacio O ( k ) . [ 5 ]

Algoritmos variantes

Si cada elemento a ordenar es un número entero y también se usa como clave, entonces se pueden combinar el segundo y el tercer bucle del algoritmo de ordenación 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 el Countarray con un vector de bits que almacena un valor onepara una clave presente en la entrada y otro zeropara una clave ausente. Si, además, los elementos son las propias claves enteras, se pueden omitir por completo el segundo y el tercer bucle, y el vector de bits servirá como salida, representando los valores como desplazamientos de las zeroentradas no presentes, sumados al valor mínimo del rango. De esta forma, en esta variante, las claves se ordenan y se eliminan los duplicados simplemente colocándolos en el array de bits.

Para 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 puede paralelizarse dividiendo la entrada en submatrices de tamaño aproximadamente igual, procesando cada submatriz en paralelo para generar una matriz de conteo separada para cada una, 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 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 prefijos fácilmente paralelizable también lo hacen utilizable en algoritmos paralelos de grano más fino. [ 7 ]

Como se ha descrito, el algoritmo de ordenación por conteo no es un algoritmo in situ ; incluso sin tener en cuenta el arreglo de conteo, necesita arreglos de entrada y salida separados. Es posible modificar el algoritmo para que coloque los elementos en orden ordenado dentro del mismo arreglo que se le proporcionó como entrada, utilizando únicamente el arreglo de conteo como almacenamiento auxiliar; sin embargo, la versión in situ modificada del algoritmo de ordenación por conteo no es estable. [ 3 ]

Historia

Aunque la clasificación por radix en sí se remonta a mucho más tiempo atrás, la clasificación por conteo y su aplicación a la clasificación por radix fueron inventadas por Harold H. Seward en 1954. [ 1 ] [ 4 ] [ 8 ]

Referencias

  1. 1 2 3 4 5 6 7 8 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "8.2 Ordenación por conteo", Introducción a los algoritmos (2.ª  ed.), MIT Press y McGraw-Hill , págs. 168–170 , ISBN  0-262-03293-7Véanse también las notas históricas de la página 181.
  2. 1 2 3 4 Edmonds, Jeff (2008), "5.2 Ordenación por conteo (una ordenación estable)", Cómo pensar sobre algoritmos , Cambridge University Press, págs. 72–75 , ISBN  978-0-521-84931-9.
  3. 1 2 3 4 Sedgewick, Robert ( 2003), "6.10 Conteo indexado por clave", Algoritmos en Java, Partes 1-4: Fundamentos, Estructuras de datos, Ordenación y Búsqueda (3.ª ed.), Addison-Wesley, págs. 312–314  .
  4. 1 2 Knuth, DE (1998), El arte de la programación informática , Volumen 3: Ordenación y búsqueda (2.ª ed.), Addison-Wesley, ISBN  0-201-89685-0. Sección 5.2, Clasificación por conteo, págs.  75–80, y notas históricas, pág.  170.
  5. ↑ Burris, David S.; Schember, Kurt (1980), "Clasificación de archivos secuenciales con almacenamiento auxiliar limitado", Actas de la 18.ª Conferencia Regional Anual del Sudeste , Nueva York, NY, EE. UU.: ACM, págs. 23–31 , doi : 10.1145/503838.503855 , ISBN  0897910141, S2CID 5670614 .
  6. ↑ Zagha, Marco; Blelloch, Guy E. (1991), "Radix sort for vector multiprocessors", Proceedings of Supercomputing '91, November 18-22, 1991, Albuquerque, NM, USA , IEEE Computer Society / ACM, pp. 712– 721, doi : 10.1145/125826.126164 , ISBN  0897914597.
  7. ↑ Reif, John H. (1985), "Un algoritmo paralelo óptimo para la ordenación de enteros", Actas del 26.º Simposio Anual sobre Fundamentos de la Informática (FOCS 1985) , págs. 496–504 , doi : 10.1109/SFCS.1985.9 , ISBN  0-8186-0644-4, S2CID 5694693 .
  8. ↑ Seward, HH (1954), "2.4.6 Clasificación interna mediante clasificación digital flotante", Clasificación de información en la aplicación de computadoras digitales electrónicas a operaciones comerciales (PDF) , Tesis de maestría, Informe R-232, Instituto Tecnológico de Massachusetts , Laboratorio de Computación Digital, págs . 25–28 .
  • Visualización HTML5 de ordenación por conteo
  • Applet de demostración de la Universidad de Cardiff. Archivado el 2 de junio de 2013 en Wayback Machine.
  • Kagel, Art S. (2 de junio de 2006), "ordenación por conteo", en Black, Paul E. (ed.), Diccionario de algoritmos y estructuras de datos , Instituto Nacional de Estándares y Tecnología de EE. UU. , consultado el 21 de abril de 2011..