En ciencias de la computación, la ordenación de 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 enteros también se pueden aplicar a menudo a problemas de ordenación en los que las claves son números con coma flotante, números racionales o cadenas de texto.. La capacidad de realizar aritmética de enteros sobre las claves permite que los algoritmos de ordenación de enteros sean en muchos casos más rápidos que los algoritmos de ordenación por comparación, dependiendo de los detalles de las operaciones permitidas en el modelo de computación y del tamaño de los enteros a ordenar.
Los algoritmos de ordenación de enteros, incluidos el ordenamiento del palomar, el ordenamiento por cuentas y el ordenamiento Radix, son ampliamente utilizados y prácticos. Se considera que otros algoritmos de ordenación de enteros con límites de tiempo mínimos más pequeños no son prácticos para arquitecturas de computadoras con 64 bits o menos por palabra. Se conocen muchos de estos algoritmos, cuyo rendimiento depende de una combinación del número de elementos a ordenar, del número de bits por clave y del número de bits por palabra de la computadora que ejecuta el algoritmo de ordenación.
Consideraciones generales
Modelos de computación Los límites de tiempo para los algoritmos de ordenación de enteros suelen depender de tres parámetros: el número de valores de datos a ordenar, la magnitud de la clave más grande posible a ordenar y el número de bits que se pueden representar en una sola palabra de máquina de la computadora en la que se ejecutará el algoritmo. Normalmente, se asume que ; 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..
Los algoritmos de ordenación de enteros suelen diseñarse para funcionar en los modelos de computación sobre máquinas de punteros o sobre máquinas de acceso aleatorio. La principal diferencia entre ambos radica en 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 para las operaciones de lectura y escritura en memoria, con un coste unitario por operación. Esta capacidad permite implementar rápidamente ciertas operaciones complejas sobre datos mediante búsquedas en tablas. En cambio, 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 desplazamientos binarios, con un coste unitario por operación. Sin embargo, los distintos algoritmos de ordenación de enteros parten de diferentes supuestos sobre si la multiplicación de enteros también se permite como una operación de coste unitario.La cuestión de si se deben permitir las operaciones de multiplicación de enteros o de búsqueda en tablas se remonta a ; véase también . También se han considerado otros modelos de computación más especializados, como la máquina de acceso aleatorio paralelo.; comentado en ; ; ; .
demostró que, en algunos casos, las multiplicaciones o búsquedas en tablas requeridas por ciertos algoritmos de ordenación de enteros podían reemplazarse por operaciones personalizadas más fáciles de implementar en hardware, pero que no suelen estar disponibles en computadoras de propósito general. mejoró este enfoque mostrando cómo reemplazar estas operaciones especiales por las instrucciones de manipulación de campo de bits ya disponibles en los procesadores Intel Pentium.
En modelos de computación con memoria externa, ningún algoritmo de ordenación de enteros conocido es más rápido que la ordenación por comparación. Los investigadores han demostrado que, en estos modelos, las clases restringidas de algoritmos, limitadas en la forma en que manipulan sus claves, no pueden ser más rápidas que la ordenación por comparación, y que un algoritmo de ordenación de enteros más rápido que la ordenación por comparación implicaría la falsedad de una conjetura estándar en codificación de red.
Clasificación frente a colas de prioridad entera Una cola de prioridades es una estructura de datos para mantener una colección de elementos con prioridades numéricas, con operaciones para encontrar y eliminar el elemento con el valor de prioridad mínimo. Las colas de prioridad basadas en comparaciones, como el montículo binario, requieren 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ápidos para entradas cuyas prioridades son enteros pequeños. Estas estructuras de datos se pueden usar en un algoritmo de ordenamiento por selección, que ordena una colección de elementos encontrando y eliminando repetidamente el elemento más pequeño de la colección, y devolviendo los elementos en el orden en que fueron encontrados. Una cola de prioridad se puede usar para mantener la colección de elementos en este algoritmo, y el tiempo de este algoritmo en una colección de elementos puede estar limitado por el tiempo necesario para inicializar la cola de prioridad y luego realizar las operaciones de búsqueda y eliminación. Por ejemplo, usar un montículo binario como cola de prioridad en la ordenación por selección conduce al algoritmo heapsort, un procedimiento de ordenación por comparación que requiere un tiempo . En cambio, usar la ordenación por selección con una cola de cubetas da como resultado una forma del ordenamiento del palomar, y usar árboles de van Emde-Boas u otras colas de prioridad enteras conduce a otros algoritmos rápidos de ordenación de enteros.
En lugar de usar una cola de prioridad entera en un algoritmo de ordenación, es posible ir en la dirección opuesta y usar algoritmos de ordenación entera como subrutinas dentro de una estructura de datos de cola de prioridad entera. utilizó esta idea para demostrar que, si es posible realizar una ordenación entera en tiempo 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 compleja y presupone la disponibilidad de operaciones de multiplicación rápidas o búsquedas en tablas, pero también proporciona una cola de prioridad alternativa que utiliza solo sumas y operaciones booleanas con un tiempo por operación, multiplicando como máximo el tiempo por un logaritmo iterado.
Usabilidad Los algoritmos clásicos de ordenación entera de ordenamiento del palomar, ordenamiento por cuentas y ordenamiento Radix son ampliamente utilizados y prácticos.; . Gran parte de la investigación posterior sobre algoritmos de ordenación de enteros se ha centrado menos en la practicidad y más en mejoras teóricas en su análisis del peor caso, y no se cree que los algoritmos que provienen de esta línea de investigación sean prácticos para las arquitecturas informáticas de 64 bits actuales, aunque los experimentos han demostrado que algunos de estos métodos pueden ser una mejora con respecto a la ordenación por radix para datos con 128 o más bits por clave.. Además, para conjuntos de datos grandes, el patrón de acceso a la memoria casi aleatorio de muchos algoritmos de ordenación de enteros puede perjudicarlos en comparación con los algoritmos de ordenación por comparación que se han diseñado teniendo en cuenta la jerarquía de memoria..
La ordenación de enteros proporciona uno de los seis puntos de referencia del conjunto de pruebas de rendimiento de los sistemas informáticos de alta productividad en matemáticas discretas, desarrolladas por la Agencia de Proyectos de Investigación Avanzados de DefensaDARPA HPCS Discrete Mathematics Benchmarks , Duncan A. Buell, University of South Carolina, retrieved 2011-04-20. y uno de los once de la suite NAS Parallel Benchmarks.
Algoritmos prácticos Los algoritmos de ordenamiento del palomar o ordenamiento por cuentas pueden ordenar elementos de datos con claves en el rango de a en tiempo . En el ordenamiento del palomar (a menudo llamado ordenación por cubetas ocubos), los punteros a los elementos de datos se distribuyen en una tabla de cubetas, representados como colecciones de tipos de datos, como una lista enlazada, utilizando las claves como índices en la tabla. Luego, todas las cubetas se concatenan para formar la lista de salida. El algoritmo de ordenación por conteo. Sin embargo, también describen una versión de este algoritmo de ordenación. La versión que describen está adaptada a entradas donde las claves son números reales con una distribución conocida, en lugar de a la ordenación de enteros. utiliza una tabla de contadores en lugar de una tabla de cubetas para determinar la cantidad de elementos con cada clave. Luego, se realiza un cálculo mediante suma prefija para determinar el rango de posiciones en la salida ordenada donde deben ubicarse los valores con cada clave. Finalmente, en una segunda pasada sobre la entrada, cada elemento se mueve a la posición correspondiente a su clave en la disposición de salida., 8.2 Counting Sort, pp. 168–169. Ambos algoritmos implican solo bucles simples sobre los datos de entrada (con un tiempo ) y sobre el conjunto de claves posibles (con un tiempo ), lo que les confiere un límite de tiempo total .
El ordenamiento Radix es un algoritmo de ordenación que funciona con claves más grandes que el ordenamiento del palomar o el ordenamiento por conteo, mediante múltiples pasadas sobre los datos. Cada pasada ordena la entrada utilizando solo una parte de las claves, mediante un algoritmo de ordenación diferente (como el ordenamiento del palomar o el ordenamiento por conteo) adecuado únicamente para claves pequeñas. Para dividir las claves en partes, el algoritmo de ordenamiento Radix calcula su notación posicional para cada clave, según algún base elegida. Luego, la parte de la clave utilizada para la pasada del algoritmo es el dígito en la notación posicional de la clave completa, comenzando por el dígito menos significativo y avanzando hasta el más significativo. Para que este algoritmo funcione correctamente, el procedimiento de ordenación utilizado en cada pasada sobre los datos debe ser estable: los elementos con dígitos iguales no deben intercambiar posiciones. Para una mayor eficiencia, la base debe elegirse cercana al número de elementos de datos, . Además, usar una potencia de dos cercana a como base permite calcular rápidamente las claves de cada pasada utilizando únicamente operaciones rápidas de desplazamiento binario y máscara. Con estas elecciones, y con la ordenación del palomar o por conteo como algoritmo base, el algoritmo de ordenación por base puede ordenar elementos de datos con claves en el rango de a en tiempo .; , 8.3 Radix Sort, pp. 170–173.
Algoritmos teóricos Se han desarrollado muchos algoritmos de ordenación de enteros cuyo análisis teórico demuestra que se comportan mejor que la ordenación por comparación, la ordenación del palomar o la ordenación por base 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 palabra de máquina. El algoritmo con mejor rendimiento depende de los valores de estos parámetros. Sin embargo, a pesar de sus ventajas teóricas, estos algoritmos no representan una mejora para los rangos típicos de estos parámetros que se presentan en problemas prácticos de ordenación.
Algoritmos para claves pequeñas