Estos no son números técnicamente grandes (<1e12) porque caben fácilmente en un entero largo, que tiene 64 bits de largo.
Al ordenar objetos que provienen de un dominio limitado y discreto, los algoritmos basados en la comparación, como Quick, Merge o Heap sort, se quedan cortos con los algoritmos que aprovechan el hecho de que sus datos provienen de un conjunto limitado de valores para su ventaja.
Para los enteros, la respuesta típica que encontrará en casi cualquier recurso que se ocupe de la ordenación de enteros es usar la ordenación Radix. En pocas palabras, y específicamente para los enteros de 64 bits: los trataría como números de 4 dígitos, donde cada “dígito” es un número de 16 bits, luego se ordenaría en función de cada dígito usando el orden de conteo.
- ¿Debo comenzar a aprender estructuras de datos y algoritmos en lugar de nuevos lenguajes de programación?
- Cómo alterar el rango de un bucle for dentro del bucle en Python
- ¿Qué tipo de algoritmo de procesamiento del lenguaje natural se usaría para replicar los resultados de esta charla TED?
- Cómo resolver un problema de coincidencia de patrones de cadena sin usar funciones de expresión regular incorporadas
- ¿Qué algoritmo se usa para la predicción de abandono?
La idea detrás del ordenamiento de conteo es simple: si sabe que todos sus elementos provienen de un pequeño conjunto de valores (como enteros delimitados), simplemente puede asignar un contador para cada uno de los valores, recorrer la matriz, incrementar los contadores de los valores que encuentre, luego vacíe los valores repitiéndolos tantas veces como hayan aparecido. El algoritmo se ejecuta en tiempo lineal.
En la clasificación de Radix, clasifica su matriz en función de los valores de los dígitos de sus números, desde el menos significativo hasta el más significativo. Los dígitos pueden ser dígitos decimales, de hecho, pero como estamos usando una computadora, tiene más sentido tratar nuestros números como si estuvieran representados en algún otro sistema numérico. Dado que la ordenación de conteo requiere memoria adicional que es proporcional al número de valores que puede tener el dígito de Radix, equilibramos la velocidad de ejecución y nos conformamos con un dígito de 16 bits. Esto requeriría 65536 * sizeof (int) = 256 KB de memoria adicional para los recuentos. Si desea tener poca memoria, puede conformarse con un dígito de 8 bits.
Recuerdo haber visto una respuesta interesante a una pregunta muy similar, que también presenta la respuesta de Obama y algo de codificación inteligente: la respuesta de Anders Kaseorg a ¿Cuál es la forma más eficiente de clasificar un millón de enteros de 32 bits?
