Mezcla equilibrada


ORDENAMIENTO DE ARCHIVOS POR MEZCLA EQUILIBRADA Y BÚSQUEDA SECUENCIAL




PRESENTADO A:




PRESENTADO POR:









Junio 20 de 2014


ORDENAMIENTO POR EL MÉTODO DE MEZCLAEQUILIBRADA

Ordenamiento externo es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando lainformación que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente un disco duro) tiene que utilizarse en el proceso.El método de ordenación por mezcla equilibrada, conocido también como natural, es una optimización del método de mezcla directa.
La idea central de este algoritmo consiste en realizar lasparticiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias de tamaño fijo previamente determinadas. Luego se realiza la fusión de las secuencias ordenadas, en alternada, sobre dosarchivos. Aplicando estas acciones en forma repetida se logrará el archivo original quede ordenado. Para la realización de este proceso de ordenación se necesitaran cuatro archivos. El archivo original F ytres 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 lafusión-partición. El proceso termina cuando en la realización de una fusión-partición el segundo archivo quede vacío.
Funcionamiento:
1. Dividir la entrada en pasadas (una pasada es una secuencia de elementosque aumentan o disminuyen)
2. Invertir las pasadas decrecientes para que se conviertan en crecientes.
3. Combinar todas las pasadas juntas.
Complejidad:
•Tiempo O(n) para datos ordenados, ordenadosa la inversa o datos casi ordenados.
•Complejidad O(n*logr), donde r es el número de pasadas en la entrada. En el peor caso, cada pasada tiene dos elementos, así r= n/2 y la complejidad es de...