clasificación externa de enteros con O (N log N) lee y O (N) escribe

Question

Me interesa algoritmo que debo utilizar para cumplir con los requisitos de la clasificación externa de ints con O(N log N) lee y escribe O(N)

Answer 1

Si lo que busca es un algoritmo para ese tipo de clasificación (donde los datos no todos pueden encajar en base a la vez), mi solución viene desde los primeros días de la "revolución" cuando las máquinas de gama alta tuvieron menos memoria que la mayoría de las calculadoras de hoy en día.

No han funcionado las propiedades de orden O, pero creo que sería O (n) lee, O (n log n) una especie de fase (depende del método elegido especie) y O (n) escribe.

Supongamos que su conjunto de datos tiene un millón de elementos y sólo se puede encajar 100.000 en memoria a la vez. Esto es lo que haría:

• leer en el primer 100.000, ordenar y escribir esa lista ordenada de vuelta.
• hacer esto para cada grupo de 100.000.
• ejecutar una operación de combinación de los 10 grupos.

En otras palabras, una vez que los 10 grupos se clasifican dentro del grupo, tomar la primera entrada de cada grupo.

A continuación, escribir que el más bajo de los 10 (que es la más baja de toda la millones) para el archivo de salida y leer el siguiente de ese grupo en su lugar.

A continuación, sólo seguir seleccionando el más bajo de los 10, escribiéndolo y su sustitución del mismo grupo. De ese modo, el resultado final es toda la lista ordenada de un millón de entradas.

Answer 2

de fusión externo algoritmo de ordenación .

Answer 3

Trate de esta página: algoritmos de ordenación . Además de mostrar buenas animaciones de varios algoritmos que explica cómo funcionan y su complejidad.