Ordenamiento entero

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de enero de 2021; las comprobaciones requieren 2 ediciones .

La clasificación de enteros  es la tarea de clasificar un conjunto de valores utilizando claves enteras . Los algoritmos de clasificación de enteros también se pueden usar para problemas en los que las claves son números de coma flotante o cadenas de texto [1] . La capacidad de realizar operaciones aritméticas de enteros en claves permite que los algoritmos de clasificación de enteros sean más rápidos en muchos casos que los algoritmos de clasificación similares que utilizan comparaciones, según las operaciones permitidas en el modelo de cálculo y el tamaño de los números clave.

Los algoritmos habituales de clasificación de enteros: cesta de clasificación , clasificación de raíz, clasificación de conteo son ampliamente utilizados y eficientes [2] [3] . La investigación adicional sobre los algoritmos de clasificación de enteros se ha centrado en las mejoras teóricas del peor de los casos, y los algoritmos que se han obtenido no se consideran eficientes en las computadoras modernas de 64 bits, aunque los experimentos han demostrado que algunos de estos métodos pueden ser mejores que la clasificación de datos bit a bit. con 128 o más bits en la clave [4] . Además, para grandes conjuntos de datos, la naturaleza de acceso a la memoria casi aleatoria de los algoritmos de clasificación de enteros es una limitación, especialmente cuando se compara con otros algoritmos de clasificación que han sido diseñados con una estructura de memoria jerárquica en mente .

La ordenación de enteros se utiliza en uno de los seis puntos de referencia de la suite de Matemáticas discretas de los sistemas informáticos de alta productividad de DARPA y en uno de los once criterios de la suite NAS Parallel Benchmarks [5] .

Modelos de computación

Las restricciones de tiempo de los algoritmos de clasificación de enteros generalmente dependen de tres parámetros:  - la cantidad de valores de datos que se clasificarán,  - el orden de magnitud de la clave más grande posible, y  - la cantidad de bits en la palabra de máquina de la computadora en que se ejecutará el algoritmo. En general, se supone que , es decir, las palabras de máquina son lo suficientemente grandes para representar tanto el índice en la secuencia de entrada como la clave [6] .

Los algoritmos de clasificación de enteros generalmente están diseñados para funcionar para la máquina de puntero, o para una máquina con acceso aleatorio a la memoria . La principal diferencia entre estos modelos es que las máquinas de acceso aleatorio le permiten usar un valor arbitrario en un registro como dirección de memoria en operaciones de lectura y escritura con un valor de unidad de tiempo, y organizar manipulaciones de datos complejas usando una tabla de búsqueda . El modelo de máquina de punteros permite el acceso a la memoria solo a través de punteros, que no pueden manipularse mediante operaciones aritméticas. En ambos modelos , las operaciones bit a bit se pueden realizar, por regla general, en un segmento de tiempo . Diferentes algoritmos de clasificación de enteros hacen diferentes suposiciones sobre si la multiplicación de enteros se puede realizar en un intervalo de tiempo [6] [7] . También se pueden considerar modelos de computación más especializados, como máquinas paralelas de acceso aleatorio [8] [9] [10] [11] [12] .

En 1999 se demostró que, en algunos casos, la multiplicación o la búsqueda en tablas requeridas para algunos algoritmos de clasificación de enteros pueden reemplazarse por operaciones especializadas que pueden implementarse fácilmente en hardware pero que normalmente no están disponibles en computadoras de propósito general [7] .

Notas

  1. ↑ Han, Thorup, 2002 .
  2. ↑ McIlroy, Bostic, McIlroy, 1993 .
  3. ↑ Andersson, Nilsson, 1998 .
  4. ↑ Rahman, Raman, 1998 .
  5. ↑ DARPA HPCS Discrete Mathematics Benchmarks Archivado el 10 de marzo de 2016 en Wayback Machine , Duncan A. Buell, Universidad de Carolina del Sur, consultado el 20 de abril de 2011.
  6. ↑ 1 2 Fredman, Willard, 1993 .
  7. ↑ 1 2 Andersson, Miltersen, Thorup, 1999 .
  8. ↑ Reif, 1985 .
  9. ↑ Cole, Vishkin, 1986 , Comentario.
  10. ↑ Hagerup, 1987 .
  11. ↑ Bhatt et al., 1991 .
  12. ↑ Albers, Hagerup, 1997 .

Literatura