Una ves

I N D I C E

U N I D A D 7 = Ordenación Externa

7.1 Algoritmos Ordenacion Externa ………………………………2

7.1.1 Intercalacion Directa ………………………………………..5

7.1.2 Mezcla Natural ………………………………………………67.1 Algoritmos de ordenación externa

Es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento se requiere cuando lainformación que se dice que se tiene que ordenar no cabe en la memoria principal de una computadora (o sea la memoria RAM). Y un tipo de memoria más lenta (o sea el disco duro), tiene que utilizarse en elproceso.

Métodos de ordenación interna.
Intercalación Directa:
La intercalación directa consiste en la unión de dos arreglos ordenados de modo que la unión esté también ordenada. Para ello, bastacon recorrer los arreglos de izquierda a derecha e ir cogiendo el menor de los dos elementos, de forma que sólo aumenta el contador del arreglo del que sale el elemento siguiente para el arreglo suma.Mezcla Natural:
Es realizar particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias ordenadas de tamaño fijo previamente determinadas. Luego se realiza la fusión deesas secuencias ordenadas, alternativamente sobre dos archivos. Repitiendo este proceso secuencialmente, se logra que el archivo quede completamente ordenado.

Ejemplo de Intercalación DirectaEjemplo. Supongamos que se desea ordenar las claves del archivo F. Para realizar tal actividad se utilizan los archivos auxiliares a los que se les denominara F1 y F2.

F:    09    75    14    68   29    17    31    25    04  05  13  18   72  46   61

PRIMERA PASADA

Partición en secuencias de longitud 1.

F1: 09’    14'    29'    31'    04'    13'    72'    61'
F2: 75’    68'    17'    25'05' 18'    46'

Fusión en secuencias de longitud 2.

F:    09    75'    14    68'    17    29'    25    31'    04    05'    13    18'    46    72'    61
SEGUNDA PASADA
Partición en...