java

2014-I

MATERIA
ESTRUCTURA DE DATOS
TEMA
METODOS DE ORDENAMIENTO
EXTERNOS

PROFESOR
Ing. MIGUEL ANGEL SÁNCHEZ HERNÁNDEZ

Ordenación Externa

Recibeeste nombre, dado que los elementos se encuentran almacenados en un archivo, lo cual
indica que se encuentran en un dispositivo de almacenamiento secundario oexterno.
Esto es debido a que la cantidad de elementos que se tiene no caben en la memoria RAM, los
métodos que ocupan esta técnica siguen la metodología de dividey vencerás. Para esto se ocupan
dos o más archivos que nos ayudaran a ordenar los elementos, para que al último se ocupe otro
archivo que se fusionara con losarchivos ocupados, quedando este ordenado. Los algoritmos más
comunes de ordenamiento Mezcla Directa y Mezcla Natural.

Mezcla Directa
La idea central consisteen realizar una partición y fusión produciendo secuencias ordenadas cada
vez mayor, en la primera pasada se parte el archivo F, tomando el primer elemento ypasarlo a F1,
tomando el segundo elemento de F y pasarlo a F2, así sucesivamente. Cuando se realice la fusión
de F1 y F2 en F, se toma el menor elemento de F1 y F2 yse pone como primer elemento a F, así
sucesivamente.
En la segunda pasada se hace ahora una partición de longitud 2, y se fusionan de nuevo, logrando
obtenerordenamiento de longitud 4, este proceso se repite hasta que la longitud de la partición
sea menor o igual al número de elementos del archivo original.
Ejercicios1.-Crear un archivo con 1,000,000 de números enteros entre el rango de 0 a 2000.
2.-Implementar la Mezcla Directa y ocupar el archivo generado anteriormente.