Clasificación externa
La clasificación externa es una clase de algoritmos de clasificación que pueden manejar cantidades masivas de datos . La clasificación externa es necesaria cuando los datos que se clasifican no caben en la memoria principal de un dispositivo informático (generalmente RAM ) y, en cambio, deben residir en la memoria externa más lenta , generalmente una unidad de disco duro . Por lo tanto, los algoritmos de clasificación externos son algoritmos de memoria externa y, por lo tanto, aplicables en el modelo de cálculo de memoria externa .
Los algoritmos de clasificación externa generalmente se dividen en dos tipos, clasificación de distribución, que se parece a la clasificación rápida , y clasificación de combinación externa, que se parece a la clasificación de combinación . Este último suele utilizar una estrategia híbrida de clasificación y fusión. En la fase de clasificación, se leen, clasifican y escriben en un archivo temporal fragmentos de datos lo suficientemente pequeños como para caber en la memoria principal. En la fase de fusión, los subarchivos ordenados se combinan en un solo archivo más grande.
Los algoritmos de clasificación externos se pueden analizar en el modelo de memoria externa . En este modelo, una caché o memoria interna de tamaño M y una memoria externa ilimitada se dividen en bloques de tamaño B , y el tiempo de ejecución de un algoritmo está determinado por el número de transferencias de memoria entre la memoria interna y la externa. Al igual que sus contrapartes ajenas a la memoria caché , los algoritmos de clasificación externa asintóticamente óptimos logran un tiempo de ejecución (en notación Big O ) de .
Un ejemplo de clasificación externa es el algoritmo de clasificación de combinación externa , que es un algoritmo de combinación de K-way . Ordena los fragmentos que caben en la RAM y luego fusiona los fragmentos ordenados. [1] [2]
El algoritmo primero ordena M elementos a la vez y vuelve a colocar las listas ordenadas en la memoria externa. A continuación , se fusiona de forma recursiva en esas listas ordenadas. Para hacer esta combinación, los elementos B de cada lista ordenada se cargan en la memoria interna y el mínimo se emite repetidamente.
Históricamente, en lugar de una ordenación, a veces se usaba un algoritmo de selección de reemplazo [3] para realizar la distribución inicial, para producir en promedio la mitad de los trozos de salida del doble de longitud.