Ordenación de números enteros

En informática , la ordenación de números enteros es el problema algorítmico de ordenar una colección de valores de datos mediante claves enteras . Los algoritmos diseñados para la ordenación de números enteros también se pueden aplicar a menudo a problemas de ordenación en los que las claves son números de punto flotante , números racionales o cadenas de texto. ^[1] La capacidad de realizar aritmética de números enteros en las claves permite que los algoritmos de ordenación de números enteros sean más rápidos que los algoritmos de ordenación por comparación en muchos casos, dependiendo de los detalles de qué operaciones están permitidas en el modelo de computación y qué tan grandes son los números enteros que se ordenarán.

Los algoritmos de ordenamiento de números enteros, como el ordenamiento por casillero , el ordenamiento por conteo y el ordenamiento por radix , se utilizan ampliamente y son prácticos. No se cree que otros algoritmos de ordenamiento de números enteros con límites de tiempo más pequeños en el peor de los casos sean prácticos para arquitecturas informáticas con 64 bits por palabra o menos. Se conocen muchos de estos algoritmos, cuyo rendimiento depende de una combinación de la cantidad de elementos a ordenar, la cantidad de bits por clave y la cantidad de bits por palabra de la computadora que realiza el algoritmo de ordenamiento.

Los límites de tiempo para los algoritmos de ordenamiento de números enteros dependen típicamente de tres parámetros: el número n de valores de datos que se ordenarán, la magnitud K de la clave más grande posible que se ordenará y el número w de bits que se pueden representar en una sola palabra de máquina del ordenador en el que se ejecutará el algoritmo. Normalmente, se supone que w ≥ log ₂ (max( n , K )) ; es decir, que las palabras de máquina son lo suficientemente grandes como para representar un índice en la secuencia de datos de entrada, y también lo suficientemente grandes como para representar una sola clave. ^[2]

Los algoritmos de ordenamiento de números enteros suelen estar diseñados para funcionar en los modelos de computación de máquina de punteros o de máquina de acceso aleatorio . La principal diferencia entre estos dos modelos es cómo se puede direccionar la memoria. La máquina de acceso aleatorio permite que cualquier valor almacenado en un registro se utilice como dirección de operaciones de lectura y escritura de memoria, con un coste unitario por operación. Esta capacidad permite que determinadas operaciones complejas sobre datos se implementen rápidamente mediante búsquedas en tablas. Por el contrario, en el modelo de máquina de punteros, las operaciones de lectura y escritura utilizan direcciones almacenadas en punteros, y no se permite realizar operaciones aritméticas sobre estos punteros. En ambos modelos, se pueden sumar valores de datos, y también se pueden realizar operaciones booleanas bit a bit y operaciones de desplazamiento binario sobre ellos, en tiempo unitario por operación. Sin embargo, los distintos algoritmos de ordenamiento de números enteros hacen suposiciones diferentes sobre si la multiplicación de números enteros también está permitida como una operación de tiempo unitario. ^[3] También se han considerado otros modelos de computación más especializados, como la máquina de acceso aleatorio paralela . ^[4]

Andersson, Miltersen y Thorup (1999) demostraron que, en algunos casos, las multiplicaciones o las búsquedas en tablas que requieren algunos algoritmos de ordenamiento de números enteros se pueden reemplazar por operaciones personalizadas que se pueden implementar con mayor facilidad en hardware, pero que no suelen estar disponibles en computadoras de uso general. Thorup (2003) mejoró este punto al mostrar cómo reemplazar estas operaciones especiales por las instrucciones de manipulación de campos de bits que ya están disponibles en los procesadores Pentium .

En los modelos de memoria externa de computación , ningún algoritmo de ordenamiento de números enteros conocido es más rápido que el ordenamiento por comparación. Los investigadores han demostrado que, en estos modelos, las clases restringidas de algoritmos que están limitadas en la forma en que manipulan sus claves no pueden ser más rápidas que el ordenamiento por comparación, ^[5] y que un algoritmo de ordenamiento de números enteros que sea más rápido que el ordenamiento por comparación implicaría la falsedad de una conjetura estándar en la codificación de redes . ^[6]

Una cola de prioridad es una estructura de datos para mantener una colección de elementos con prioridades numéricas, que tiene operaciones para buscar y eliminar el elemento con el valor de prioridad mínimo. Las colas de prioridad basadas en comparación, como el montón binario, toman un tiempo logarítmico por actualización, pero otras estructuras, como el árbol de van Emde Boas o la cola de cubos, pueden ser más rápidas para entradas cuyas prioridades son números enteros pequeños. Estas estructuras de datos se pueden utilizar en el algoritmo de ordenación por selección , que ordena una colección de elementos buscando y eliminando repetidamente el elemento más pequeño de la colección y devolviendo los elementos en el orden en que se encontraron. Se puede utilizar una cola de prioridad para mantener la colección de elementos en este algoritmo, y el tiempo para este algoritmo en una colección de n elementos puede estar limitado por el tiempo para inicializar la cola de prioridad y luego realizar n operaciones de búsqueda y eliminación. Por ejemplo, el uso de un montón binario como una cola de prioridad en la ordenación por selección conduce al algoritmo de ordenación por montón , un algoritmo de ordenación por comparación que toma O ( n log n ) tiempo. En cambio, el uso de una ordenación por selección con una cola de cubos proporciona una forma de ordenación por casillero , y el uso de árboles de van Emde Boas u otras colas de prioridad de enteros conduce a otros algoritmos rápidos de ordenación de enteros. ^[7]

En lugar de utilizar una cola de prioridad de enteros en un algoritmo de ordenamiento, es posible ir en la otra dirección y utilizar algoritmos de ordenamiento de enteros como subrutinas dentro de una estructura de datos de cola de prioridad de enteros. Thorup (2007) utilizó esta idea para demostrar que, si es posible realizar un ordenamiento de enteros en un tiempo T ( n ) por clave, entonces el mismo límite de tiempo se aplica al tiempo por operación de inserción o eliminación en una estructura de datos de cola de prioridad. La reducción de Thorup es complicada y supone la disponibilidad de operaciones de multiplicación rápida o búsquedas en tablas, pero también proporciona una cola de prioridad alternativa que utiliza solo operaciones de suma y booleanas con un tiempo T ( n ) + T (log n ) + T (log log n ) + ... por operación, como máximo multiplicando el tiempo por un logaritmo iterado . ^[7]

Los algoritmos clásicos de ordenamiento de números enteros de ordenamiento por casillero , ordenamiento por conteo y ordenamiento por radix son ampliamente utilizados y prácticos. ^[8] Gran parte de la investigación posterior sobre algoritmos de ordenamiento de números enteros se ha centrado menos en la practicidad y más en mejoras teóricas en su análisis del peor de los casos , y no se cree que los algoritmos que surgen de esta línea de investigación sean prácticos para las arquitecturas informáticas actuales de 64 bits , aunque los experimentos han demostrado que algunos de estos métodos pueden ser una mejora en el ordenamiento por radix para datos con 128 o más bits por clave. ^{[9] Además, para grandes conjuntos de datos, los} patrones de acceso a memoria casi aleatorios de muchos algoritmos de ordenamiento de números enteros pueden perjudicarlos en comparación con los algoritmos de ordenamiento por comparación que se han diseñado teniendo en cuenta la jerarquía de memoria . ^[10]

La ordenación de enteros proporciona uno de los seis puntos de referencia del conjunto de puntos de referencia de matemáticas discretas de sistemas informáticos de alta productividad de DARPA , ^[11] y uno de los once puntos de referencia del conjunto de puntos de referencia paralelos de NAS .

La ordenación por casillero o por conteo puede ordenar n elementos de datos que tienen claves en el rango de 0 a K − 1 en el tiempo O ( n + K ) . En la ordenación por casillero (a menudo llamada ordenación por cubo), los punteros a los elementos de datos se distribuyen a una tabla de cubos, representados como tipos de datos de colección como listas enlazadas , utilizando las claves como índices en la tabla. Luego, todos los cubos se concatenan juntos para formar la lista de salida. ^[12] La ordenación por conteo utiliza una tabla de contadores en lugar de una tabla de cubos, para determinar el número de elementos con cada clave. Luego, se utiliza un cálculo de suma de prefijo para determinar el rango de posiciones en la salida ordenada en la que se deben colocar los valores con cada clave. Finalmente, en un segundo paso sobre la entrada, cada elemento se mueve a la posición de su clave en la matriz de salida. ^[13] Ambos algoritmos implican sólo bucles simples sobre los datos de entrada (que toman tiempo O ( n ) ) y sobre el conjunto de claves posibles (que toman tiempo O ( K ) ), dando su límite de tiempo general O ( n + K ) .

El ordenamiento por radix es un algoritmo de ordenamiento que funciona para claves más grandes que el ordenamiento por casillero o el ordenamiento por conteo, al realizar múltiples pasadas sobre los datos. Cada pasada ordena la entrada utilizando solo una parte de las claves, mediante un algoritmo de ordenamiento diferente (como el ordenamiento por casillero o el ordenamiento por conteo) que es adecuado solo para claves pequeñas. Para dividir las claves en partes, el algoritmo de ordenamiento por radix calcula la notación posicional para cada clave, de acuerdo con algún radix elegido ; luego, la parte de la clave utilizada para el i -ésimo paso del algoritmo es el i -ésimo dígito en la notación posicional para la clave completa, comenzando desde el dígito menos significativo y progresando hasta el más significativo. Para que este algoritmo funcione correctamente, el algoritmo de ordenamiento utilizado en cada pasada sobre los datos debe ser estable : los elementos con dígitos iguales no deben cambiar de posición entre sí. Para una mayor eficiencia, el radix debe elegirse para que esté cerca del número de elementos de datos, n . Además, el uso de una potencia de dos cerca de n como base permite calcular rápidamente las claves para cada pasada utilizando únicamente operaciones rápidas de desplazamiento binario y máscara. Con estas opciones, y con el ordenamiento por casillero o el ordenamiento por conteo como algoritmo base, el algoritmo de ordenamiento por base puede ordenar n elementos de datos que tienen claves en el rango de 0 a K − 1 en tiempo O ( n log _n K ) . ^[14]

Se han desarrollado muchos algoritmos de ordenamiento de números enteros cuyo análisis teórico demuestra que se comportan mejor que el ordenamiento por comparación, el ordenamiento por casillero o el ordenamiento por radix para combinaciones suficientemente grandes de los parámetros que definen el número de elementos a ordenar, el rango de claves y el tamaño de la palabra de máquina. El algoritmo que tenga el mejor rendimiento depende de los valores de estos parámetros. Sin embargo, a pesar de sus ventajas teóricas, estos algoritmos no suponen una mejora para los rangos típicos de estos parámetros que surgen en los problemas prácticos de ordenamiento. ^[9]

Un árbol de Van Emde Boas puede utilizarse como cola de prioridad para ordenar un conjunto de n claves, cada una en el rango de 0 a K − 1 , en tiempo O ( n log log K ) . Esta es una mejora teórica sobre la ordenación por radix cuando K es suficientemente grande. Sin embargo, para utilizar un árbol de Van Emde Boas, se necesita una memoria directamente direccionable de K palabras, o se necesita simularlo utilizando una tabla hash , reduciendo el espacio a lineal pero haciendo que el algoritmo sea aleatorio. Otra cola de prioridad con un rendimiento similar (incluida la necesidad de aleatorización en forma de tablas hash) es el trie Y-fast de Willard (1983).

Kirkpatrick y Reisch (1984) desarrollaron una técnica más sofisticada con un sabor similar y con un mejor rendimiento teórico. Observaron que cada paso de la ordenación por radix puede interpretarse como una técnica de reducción de rango que, en tiempo lineal, reduce el tamaño máximo de la clave por un factor de  n ; en cambio, su técnica reduce el tamaño de la clave a la raíz cuadrada de su valor anterior (reduciendo a la mitad el número de bits necesarios para representar una clave), nuevamente en tiempo lineal. Al igual que en la ordenación por radix, interpretan las claves como números de base b de dos dígitos para una base b que es aproximadamente √ K . Luego, agrupan los elementos que se ordenarán en contenedores según sus dígitos altos, en tiempo lineal, utilizando una memoria de dirección directa grande pero no inicializada o una tabla hash. Cada contenedor tiene un representante, el elemento en el contenedor con la clave más grande; luego ordenan la lista de elementos utilizando como claves los dígitos altos para los representantes y los dígitos bajos para los no representantes. Al agrupar nuevamente los elementos de esta lista en contenedores, cada contenedor puede colocarse en orden ordenado y, al extraer los representantes de la lista ordenada, los contenedores pueden concatenarse entre sí para formar un orden ordenado. De este modo, en tiempo lineal, el problema de ordenación se reduce a otro problema de ordenación recursiva en el que las claves son mucho más pequeñas, la raíz cuadrada de su magnitud anterior. Repetir esta reducción de rango hasta que las claves sean lo suficientemente pequeñas para ordenar por contenedores conduce a un algoritmo con un tiempo de ejecución de O( n log log _n K ) .

Un algoritmo aleatorio complicado de Han y Thorup (2002) en el modelo de computación Word RAM permite reducir aún más estos límites de tiempo, a O( n √ log log K ) .

Se dice que un algoritmo de ordenamiento de números enteros no es conservador si requiere un tamaño de palabra w que sea significativamente mayor que log max( n , K ) . ^[15] Como caso extremo, si w ≥ K , y todas las claves son distintas, entonces el conjunto de claves se puede ordenar en tiempo lineal representándolo como un vector de bits , con un bit 1 en la posición i cuando i es una de las claves de entrada, y luego eliminando repetidamente el bit menos significativo. ^[16]

El algoritmo de ordenamiento empaquetado no conservador de Albers y Hagerup (1997) utiliza una subrutina, basada en la red de ordenamiento bitónico de Ken Batcher , para fusionar dos secuencias ordenadas de claves que son cada una lo suficientemente cortas como para ser empaquetadas en una sola palabra de máquina. La entrada al algoritmo de ordenamiento empaquetado, una secuencia de elementos almacenados uno por palabra, se transforma en una forma empaquetada, una secuencia de palabras que contiene cada una múltiples elementos en orden ordenado, utilizando esta subrutina repetidamente para duplicar el número de elementos empaquetados en cada palabra. Una vez que la secuencia está en forma empaquetada, Albers y Hagerup utilizan una forma de ordenamiento por fusión para ordenarla; cuando se están fusionando dos secuencias para formar una sola secuencia más larga, la misma subrutina de ordenamiento bitónico se puede utilizar para extraer repetidamente palabras empaquetadas que consisten en los elementos restantes más pequeños de las dos secuencias. Este algoritmo gana suficiente aceleración de su representación empaquetada para ordenar su entrada en tiempo lineal siempre que sea posible que una sola palabra contenga Ω(log n log log n ) claves; es decir, cuando log K log n log log n ≤ cw para alguna constante c > 0 .

La ordenación por casillero, la ordenación por conteo, la ordenación por radix y la ordenación por árbol de Van Emde Boas funcionan mejor cuando el tamaño de la clave es pequeño; para claves lo suficientemente grandes, se vuelven más lentos que los algoritmos de ordenación por comparación. Sin embargo, cuando el tamaño de la clave o el tamaño de la palabra es muy grande en relación con el número de elementos (o equivalentemente, cuando el número de elementos es pequeño), puede ser posible nuevamente ordenar rápidamente, utilizando diferentes algoritmos que aprovechen el paralelismo inherente a la capacidad de realizar operaciones aritméticas en palabras grandes.

Un resultado temprano en esta dirección fue proporcionado por Ajtai, Fredman y Komlós (1984) utilizando el modelo de computación de sonda celular (un modelo artificial en el que la complejidad de un algoritmo se mide solo por el número de accesos a la memoria que realiza). Basándose en su trabajo, Fredman y Willard (1994) describieron dos estructuras de datos, el Q-heap y el atomic heap, que son implementables en una máquina de acceso aleatorio. El Q-heap es una versión de bit-paralelo de un trie binario , y permite que tanto las operaciones de cola de prioridad como las consultas de sucesor y predecesor se realicen en tiempo constante para conjuntos de O ((log N ) ^1/4 ) elementos, donde N ≤ 2 ^w es el tamaño de las tablas precalculadas necesarias para implementar la estructura de datos. El atomic heap es un B-tree en el que cada nodo del árbol se representa como un Q-heap; permite operaciones de cola de prioridad de tiempo constante (y por lo tanto, ordenación) para conjuntos de (log N ) ^{O (1)} elementos.

Andersson et al. (1998) proporcionan un algoritmo aleatorio llamado ordenamiento por firma que permite el ordenamiento en tiempo lineal de conjuntos de hasta 2 ^{O ((log w ) 1/2 − ε )} elementos a la vez, para cualquier constante ε > 0 . Al igual que en el algoritmo de Kirkpatrick y Reisch, realizan una reducción de rango utilizando una representación de las claves como números en base  b para una elección cuidadosa de b . Su algoritmo de reducción de rango reemplaza cada dígito por una firma, que es un valor hash con O (log n ) bits de modo que los diferentes valores de dígitos tienen diferentes firmas. Si n es suficientemente pequeño, los números formados por este proceso de reemplazo serán significativamente más pequeños que las claves originales, lo que permite que el algoritmo de ordenamiento empaquetado no conservativo de Albers & Hagerup (1997) ordene los números reemplazados en tiempo lineal. A partir de la lista ordenada de números reemplazados, es posible formar un trie comprimido de las claves en tiempo lineal, y los hijos de cada nodo en el trie pueden ordenarse recursivamente usando solo claves de tamaño b , después de lo cual un recorrido del árbol produce el orden ordenado de los elementos.

Fredman y Willard (1993) introdujeron el modelo transdicotómico de análisis para algoritmos de ordenamiento de números enteros, en el que no se asume nada sobre el rango de las claves de números enteros y se debe limitar el rendimiento del algoritmo a una función del número de valores de datos únicamente. Alternativamente, en este modelo, se supone que el tiempo de ejecución de un algoritmo en un conjunto de n elementos es el peor tiempo de ejecución para cualquier combinación posible de valores de K y  w . El primer algoritmo de este tipo fue el algoritmo de ordenamiento de árbol de fusión de Fredman y Willard , que se ejecuta en un tiempo O( n log n / log log n ) ; esto es una mejora sobre el ordenamiento por comparación para cualquier elección de K y  w . Una versión alternativa de su algoritmo que incluye el uso de números aleatorios y operaciones de división de números enteros mejora esto a O( n √ log n ) .

Desde su trabajo, se han desarrollado algoritmos aún mejores. Por ejemplo, al aplicar repetidamente la técnica de reducción de rango de Kirkpatrick-Reisch hasta que las claves sean lo suficientemente pequeñas para aplicar el algoritmo de ordenamiento empaquetado de Albers-Hagerup, es posible ordenar en tiempo O ( n log log n ) ; sin embargo, la parte de reducción de rango de este algoritmo requiere una memoria grande (proporcional a √ K ) o aleatorización en forma de tablas hash. ^[17]

Han y Thorup (2002) mostraron cómo ordenar en tiempo aleatorio O( n √ log log n ) . Su técnica implica el uso de ideas relacionadas con la ordenación de firmas para particionar los datos en muchas sublistas pequeñas, de un tamaño lo suficientemente pequeño como para que la ordenación de firmas pueda ordenar cada una de ellas de manera eficiente. También es posible usar ideas similares para ordenar números enteros de manera determinista en tiempo O ( n log log n ) y espacio lineal. ^[18] Usando solo operaciones aritméticas simples (sin multiplicaciones ni búsquedas en tablas) es posible ordenar en tiempo esperado aleatorio O ( n log log n ) ^[19] o de manera determinista en tiempo O ( n (log log n ) ^{1 + ε} ) para cualquier constante ε > 0 . ^[1]

Notas al pie

Fuentes secundarias

Fuentes primarias