Los algoritmos de ordenamiento externo se usan cuando hay que manejar grandes cantidades de información. Estos algoritmos entran en función cuando la información a ordenar no cabe en la memoria principal del sistema; entonces se recurre al uso de una memoria mas grande, aunque esto conlleva a un proceso de ordenamiento mas lento.
En los métodos de tipo "merge", la informacion es tratada como cadenas, las cuales son organizadas de forma ascendente y combinadas con las demas cadenas a tratar. Al final del proceso de acomodo,se tendra una gran cadena organizada; dicha cadena sera separada en la cantidad original de cadenas, solo que ahora ordenadas.
Uno de los métodos de ordenación externos mas eficiente es el llamado “Polyphase Merge Sort”. Propuesto por R.L. Gilstad en 1960, es un método constituido por una serie de fases, las cuales pueden tan solo consistir en chequeos parciales sobre toda la información.
Suponiendo que solo hay C cintas disponibles, una fase se define como el tiempo durante el cual un conjunto de C-1 cintas esta siendo usado como la fuente de un tipo de fusión de (C-1) sentidos y la otra cinta esta siendo usada como destino. (Donde (C-1) es el máximo numero de cintas que pueden ser usadas en una fusión.)
C6 C5 C4 C3 C2 C1 Corridas
ProcesadasFase 1 131 130 128 124 116 - 129 Fase 2 115 114 112 18 - 516 80 Fase 3 17 16 14 - 98 58 72 Fase 4 13 12 - 174 94 54 68 Fase 5 11 - 332 172 92 52 66 Fase 6 - 651 331 171 91 51 65 Fase 7 1291 - - - - - 129 En la tabla, 131 representa 31 corridas con longitud relativa de 1, etc. (Se asume que las corridas iniciales tienen longitudes aproximadamente iguales). Durante el proceso de fusión, han sido usadas continuamente fusiones de 5 sentidos, lo que significa que cualquier distribución intermedia ha sido completamente eliminada. Para lograr esto, se necesita una distribución perfecta de fibonacci de corridas en las cintas después de cada fase.
Se puede observar por medio de la tabla anterior, que las primeras 7 distribuciones perfectas de Fibonacci son: {1,0,0,0,0}, {1,1,1,1,1}, {2,2,2,2,1}, {4,4,4,3,2}, {8,8,7,6,4}, {16,15,14,12,8}, y {31,30,28,24,16}.
Se inicia con p-1 ceros y un 1, y después cada numero es la suma de los valores p precedentes.
Las distribuciones perfectas de Fibonacci pueden ser obtenidas corriendo el patrón hacia atrás rotando cíclicamente los contenidos de la cinta.
Distribución Perfecta de Fibonacci Nivel C6 C5 C4 C3 C2 Corridas 0 1 0 0 0 0 1 1 1 1 1 1 1 5 2 2 2 2 2 1 9 3 4 4 4 3 2 17 4 8 8 7 6 4 33 5 16 15 14 12 8 65 6 31 30 28 24 16 129 7 61 59 55 47 31 253 8 120 116 108 92 61 497 - - - - - - - n an bn cn dn en tn n+1 an+bn an+cn an+dn an+en an tn+4an
Puede tratar con cualquier cantidad de informacion, teniendo siempre un alto nivel de eficiencia.
No requiere verificar todas las cintas en cada una de las corridas.
Por su manera de tratar la informacion, es mucho mas veloz que otros métodos del mismo tipo.
Disminuye el número de cintas utilizadas durante el ordenamiento, ya que reutiliza los archivos que han sido vaciados en corridas anteriores.
MEJOR DE LOS CASOS. Es O(n) y en el mejor de los casos se contara con una distribucion perfecta de Fibonacci .
PEOR DE LOS CASOS. De igual forma es O(n). (Si no se logra obtener una distribucion perfecta de Fibonacci, bastara con saltar las cintas correspondientes en cada fase de la fusion polyfase. Por ejemplo, si se tienen 53 corridas iniciales, cualquier numero de corridas entre 54 y 65 seran evitados (T=6).El algoritmo tratara de igualar el numero de saltos en cada cinta tan bien como le sea posible.)
void poly_sort( )
{
int i, j, some;
extern int maxfiles, maxruns[], actruns[];
extern struct rec LastRec[];
/* Inicializa la entrada/salida de archivos */
OpenRead(1);
for (i=2; i<=maxfiles; i++) OpenWrite(i);
/* Inicializa el conteo Perfecto y Actual de corridas */
for (i=0; i<=maxfiles; i++) maxruns[i]=actruns[i]=0;
maxruns[0] = maxruns[maxfiles] = 1;
distribute( ); /*Distribución de acuerdo al patrón de Fibonacci*/
/* Inicializa la fase de fusión */
for (i=2; i<=maxfiles; i++) {
OpenRead(i); LastRec[i] = ReadFile(i);
}
for (i=1; maxruns[0]>1; i = (i%maxfiles)+1) {
OpenWrite(i);
/* Bucle mientras la próxima cinta queda vacía*/
while (maxruns[ (i%maxfiles)+1 ] > 0) {
some = FALSE;
for (j=1; j<=maxfiles; j++)
if (j!=i) {
if (maxruns[j]>actruns[j])
FilStat[j] = '-'; /* detenido */
else {
FilStat[j] = 'i'; /* entrada */
actruns[j]--;
some = TRUE;
}
maxruns[j]--; maxruns[0]--;
}
maxruns[i]++; maxruns[0]++;
if (some) { merge(i); actruns[i]++; }
}
OpenRead(i); LastRec[i] = ReadFile(i);
}
return(i==1 ? maxfiles : i-1);
} /* fin de poly_sort( ) */
nextfile( )/*Selección del próximo archivo para fusión polyfase*/
{
extern int maxfiles, maxruns[], actruns[];
int i, j, inc;
actruns[0]++; /* Aumenta al numero total de corridas*/
if (actruns[0]>maxruns[0]) {
/* Encuentra la proxima distribucion perfecta */
inc = maxruns[maxfiles];
maxruns[0] += (maxfiles-2) * inc;
for (i=maxfiles; i>1; i--)
maxruns[i] = maxruns[i-1] + inc;
}
j = 2;
/* Selección del archivo mas alejado al número de la corrida perfecta*/
for (i=3; i<=maxfiles; i++)
if (maxruns[i]-actruns[i]>maxruns[j]-actruns[j])
j = i; /* end of if */
actruns[j]++;
return(j);
} /* Fin de nextfile ( ) */