asaas

Mezcla Natural

Ordenación por el método de mezcla equilibrada
El método de ordenación por mezcla equilibrada, conocido tambien como natural, es una optimization del metodo de mezcla directa.La idea central de este algoritmo consiste en realizar las particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias de tamaño fijo previamente determinadas. Luego se realizala fusion de las secuencias ordenadas, en alternada, sobre dos archivos. Aplicando estas acciones en forma repetida se logrará el archivo original quede ordenado. Para la realization de este procesode ordenación se necesitaran cuatro archivos. El archivo original F y tres archivos auxiliares a los que se denominara F1, F2 y F3. De estos archivos, dos serán considerados de entrada y dos de salida;esto, de manera alternada, con el objeto de realizar la fusion-partición. El proceso termina cuando en la realización de una fusion-partición el segundo archivo quede vacío.
Supongamos que se deseaordenar las claves del archivo F utilizando el método mezcla equilibrada.
F:    09    75    14    68    29    17    31    25    04   05    13    18    72   46    61
Los pasos que se realizan son:PARTICIÓN  INICIAL
F2:    09    75'    29'    25'    46    61'
F3:    14    68'    17     31'    04   05    13    18    72'
PRIMERA FUSION-PARTICION
F:     09    14   68   75'    04   05    13   18    25    46    61    72'
F1:    17   29    31'

SEGUNDA FUSION-PARTICION
F1: 09 14 17 29 31 68 75'
F3: 04 05 13 18 25 46 61 72'
TERCERA FUSION-PARTICION
F:    04   05    09    13    14   17    18    25    29    31    46    61    68    72   75
Observe que al realizar la tercera fusion-partición el segundo archivo queda vacío; por lo tanto, se puede afirmar que el archivo ya se encuentraordenado. A continuación se presenta la description formal del algoritmo de mezcla equilibrada.

Mezcla_equilibrada (F, F1, F2, F3)
El algoritmo ordena los elementos del archivo F por el metodo...