Ingeniero Técnico en Informática de Sistemas
Ordenación externa
TEMA 4
ORDENACIÓN EXTERNA
…o como perder menos tiempo, y hacer menor número de accesos a la memoria.
INDICE TEMA 4.
4.1 Justificación
4.2 Ordenación por mezcla
Ordenación externa
4.3.1. Mezcla directa
4.3.2. Mezcla natural
4.4. Intercalación múltiple
1. JUSTIFICACIÓN
Volumen de datos amplio
Tamaño de memoria limitado
Objetivo: minimizar el número de accesos a los ficheros
2. ORDENACIÓN POR MEZCLA.
-
N ficheros `ordenados' de unen para formar un único archivo ordenado:
| A | B | Operación C |
| Vacio | Vacio | nada |
| Vacio | No vacio | copiar todos los registros de B en C |
| No vacio | Vacio | copiar todos los registros de A en C |
| No vacio | No vacio | bucle a repetir hasta que A o B estén vacios (*) |
(*) Operaciones a realizar en este caso:
Leer ( A, ElemA )
Leer ( B, ElemB )
Bucle hasta llegar al final de A o B
Comparar ( ElemA, ElemB )
if ElemA > ElemB
then Escribir ElemB en C
Leer B
else Escribir ElemA en C
Leer A
Introducir el resto de A o B en C
3. ORDENACIÓN EXTERNA.
-
MEZCLA DIRECTA
Se ordenan las secuencias de un archivo en grupos de tamaño creciente = 2n (1, 2, 4, 8, …):
Sea la secuencia:
22 6 25 48 32 5 12 20 31 35
Para grupos de tamaño = 1, tenemos:
22 25 32 12 31
6 48 5 20 35
Ordenando estas secuencias:
6 , 22 25 , 48 5 , 32 12 , 20 31 , 35
Agrupando en grupos de tamaño = 2:
6 , 22 5 , 32 31 , 35
25 , 48 12 , 20
Ordenando estos grupos:
6 , 22 , 25 , 48 5 , 12 , 30 , 32 , 31 , 35
Agrupando en grupos de tamaño = 4:
6 , 22 , 25 , 48 31 , 35
5 , 12 , 20 , 32
Ordenando:
5 , 6 , 12 , 20 , 22 , 25 , 32 , 48 31, 35
La ultima agrupación ( tamaño = 8 ):
5 , 6 , 12 , 20 , 22 , 25 , 32 , 48
31 , 35
Ordenando:
5 , 6 , 12 , 20 , 22 , 25 , 31 , 32 , 35 , 48
El procedimiento a seguir es el siguiente:
Dividir la secuencia a ordenar en 2 subsecuencias de menor tamaño, cada una la mitad de la secuencia original.
Mezclar las dos secuencias de forma ordenada, para generar otra mayor, formada por cinjuntos ordenados de valores con 20, 21, 22, … elementos.
Iterar los pasos 1 y 2 hasta que el tamaño del conjunto ordenado (2n) sea mayor que el número de elemtentos a ordenar.
-
MEZCLA NATURAL
Las secuencias intermedias no tienen tamaño prefijado ni longitud constante. Estas se generan con sus elementos ordenados, separando un elemento nuevo a otra secuencia si no se respeta esta condición.
Se incluyen separadores de secuencia.
Sea la cadena de numeros:
F1:
3 15 7 17 9 8 14 2 41 24 36 1 13 42 26 35 5 33
Aplicando el método de mezcla natural con tres ficheros, uno original y dos auxiliares (frecuententemente llamados `cintas'), el resultado es:
F2:
3 15 9 2 41 1 13 42 5 33
7 17 8 14 24 36 36 35
Cap. 4 ORDENACIÓN EXTERNA
p-5-
Descargar
| Enviado por: | Jesús Alonso |
| Idioma: | castellano |
| País: | España |
Todos los derechos reservados.