Ejemplo de Selección con Reemplazo
Registros a ordenar (representados por
identificadores):
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Buffer de ordenación con capacidad para 7
registros
1. Se carga el buffer desde el archivo (única
vez):
29, 132, 234, 68, 130, 49, 197
ODD - Curso Servetto
Ord. Externo con Montículos
1
29, 132, 234, 68, 130, 49, 197, 35, 110, 146, 174,
153, 189, 200, 115
2. Construir montículo en el buffer (de izquierda
derecha, hasta el último elemento cargado):
29, 132, 234, 68, 130, 49, 197
29, 132, 234, 68, 130, 49, 197
29, 132, 234, 68, 130, 49, 197
29, 132, 234, 68, 130, 49, 197
29, 68, 234, 132, 130, 49, 197
29, 68, 234, 132, 130, 49, 197
29, 68, 234, 132, 130, 49, 197
29, 68, 49, 132, 130, 234, 197
29, 68, 49, 132, 130, 234, 197
ODD - Curso Servetto
Ord. Externo con Montículos
2
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
3. Crear archivo de trabajo ordenado y
repetir hasta que se agote el montículo
Extraer registro de la raíz y escribirlo
ordenado
29, 68, 49, 132, 130, 234, 197
Tomar un registro desordenado
35, 68, 49, 132, 130, 234, 197
29
ODD - Curso Servetto
Ord. Externo con Montículos
3
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo
ordenado
35, 68, 49, 132, 130, 234, 197
Tomar un registro desordenado
110, 68, 49, 132, 130, 234, 197
49, 68, 110, 132, 130, 234, 197
29, 35
ODD - Curso Servetto
Ord. Externo con Montículos
4
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo
ordenado
49, 68, 110, 132, 130, 234, 197
Tomar un registro desordenado
146, 68, 110, 132, 130, 234, 197
68, 146, 110, 132, 130, 234, 197
68, 130, 110, 132, 146, 234, 197
29, 35, 49
ODD - Curso Servetto
Ord. Externo con Montículos
5
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo
ordenado
68, 130, 110, 132, 146, 234, 197
Tomar un registro desordenado
174, 130, 110, 132, 146, 234, 197
110, 130, 174, 132, 146, 234, 197
29, 35, 49, 68
ODD - Curso Servetto
Ord. Externo con Montículos
6
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo
ordenado
110, 130, 174, 132, 146, 234, 197
Tomar un registro desordenado
153, 130, 174, 132, 146, 234, 197
130, 153, 174, 132, 146, 234, 197
130, 132, 174, 153, 146, 234, 197
29, 35, 49, 68, 110
ODD - Curso Servetto
Ord. Externo con Montículos
7
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo
ordenado
130, 132, 174, 153, 146, 234, 197
Tomar un registro desordenado
189, 132, 174, 153, 146, 234, 197
132, 189, 174, 153, 146, 234, 197
132, 146, 174, 153, 189, 234, 197
29, 35, 49, 68, 110, 130
ODD - Curso Servetto
Ord. Externo con Montículos
8
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo
ordenado
132, 146, 174, 153, 189, 234, 197
Tomar un registro desordenado
200, 146, 174, 153, 189, 234, 197
146, 200, 174, 153, 189, 234, 197
146, 153, 174, 200, 189, 234, 197
29, 35, 49, 68, 110, 130, 132
ODD - Curso Servetto
Ord. Externo con Montículos
9
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo ordenado
146, 153, 174, 200, 189, 234, 197
Tomar un registro desordenado
197, 153, 174, 200, 189, 234, 115
197, 153, 174, 200, 189, 234, 115
153, 197, 174, 200, 189, 234, 115
153, 189, 174, 200, 197, 234, 115
29, 35, 49, 68, 110, 130, 132, 146
ODD - Curso Servetto
Ord. Externo con Montículos
10
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo ordenado
153, 189, 174, 200, 197, 234, 115
Tomar un registro desordenado
234, 189, 174, 200, 197, 234, 115
234, 189, 174, 200, 197, 234, 115
174, 189, 234, 200, 197, 234, 115
29, 35, 49, 68, 110, 130, 132, 146, 153
ODD - Curso Servetto
Ord. Externo con Montículos
11
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo ordenado
174, 189, 234, 200, 197, 234, 115
Tomar un registro desordenado
197, 189, 234, 200, 197, 234, 115
197, 189, 234, 200, 197, 234, 115
189, 197, 234, 200, 197, 234, 115
29, 35, 49, 68, 110, 130, 132, 146, 153, 174
ODD - Curso Servetto
Ord. Externo con Montículos
12
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo ordenado
189, 197, 234, 200, 197, 234, 115
Tomar un registro desordenado
200, 197, 234, 200, 197, 234, 115
200, 197, 234, 200, 197, 234, 115
197, 200, 234, 200, 197, 234, 115
29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189
ODD - Curso Servetto
Ord. Externo con Montículos
13
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo ordenado
197, 200, 234, 200, 197, 234, 115
Tomar un registro desordenado
234, 200, 234, 200, 197, 234, 115
234, 200, 234, 200, 197, 234, 115
200, 234, 234, 200, 197, 234, 115
29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197
ODD - Curso Servetto
Ord. Externo con Montículos
14
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo ordenado
200, 234, 234, 200, 197, 234, 115
Tomar un registro desordenado
234, 234, 234, 200, 197, 234, 115
29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200
ODD - Curso Servetto
Ord. Externo con Montículos
15
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
Extraer registro de la raíz y escribirlo ordenado
234, 234, 234, 200, 197, 234, 115
Tomar un registro desordenado
234, 234, 234, 200, 197, 234, 115
¡Montículo agotado!
Se cierra el archivo de trabajo ordenado y se justifican a
izquierda los elementos congelados
115 (Y se continúa desde el paso 2...)
29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
ODD - Curso Servetto
Ord. Externo con Montículos
16
29, 132, 234, 68, 130, 49, 197, 35, 110, 146,
174, 153, 189, 200, 115
2. Construir montículo en el buffer (de izquierda derecha,
hasta el último elemento cargado):
115
3. Crear archivo de trabajo ordenado y repetir hasta que se
agote el montículo
Extraer registro de la raíz y escribirlo ordenado
115
Tomar un registro desordenado
115
¡Montículo agotado! ...
115
ODD - Curso Servetto
Ord. Externo con Montículos
17
4. Fusionar los archivos de trabajo ordenados:
Leer un registro de cada archivo y obtener el de menor
identificador
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174, 189,
197, 200, 234
–115
Mientras el menor identificador no sea la clave
máxima 999:
Escribir el registro en el archivo fusión y obtener el
siguiente menor
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174, 189,
197, 200, 234
–115
29
ODD - Curso Servetto
Ord. Externo con Montículos
18
Escribir el registro en el archivo fusión y
obtener el siguiente menor
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
–115
29, 35
Escribir el registro en el archivo fusión y obtener el
siguiente menor
•29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
•115
29, 35, 49
ODD - Curso Servetto
Ord. Externo con Montículos
19
Escribir el registro en el archivo fusión y
obtener el siguiente menor
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
–115
29, 35, 49, 68
Escribir el registro en el archivo fusión y obtener el
siguiente menor
•29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
•115, 999
29, 35, 49, 68, 110
ODD - Curso Servetto
Ord. Externo con Montículos
20
Escribir el registro en el archivo fusión y
obtener el siguiente menor
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
–115, 999
29, 35, 49, 68, 110, 115
Escribir el registro en el archivo fusión y obtener el
siguiente menor
•29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
•115, 999
29, 35, 49, 68, 110, 115, 130
ODD - Curso Servetto
Ord. Externo con Montículos
21
Escribir el registro en el archivo fusión y
obtener el siguiente menor
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
–115, 999
29, 35, 49, 68, 110, 115, 130, 132
Escribir el registro en el archivo fusión y obtener el
siguiente menor
•29, 35, 49, 68, 110, 130, 132, 146, 153, 174,
189, 197, 200, 234
•115, 999
29, 35, 49, 68, 110, 115, 130, 132, 146
ODD - Curso Servetto
Ord. Externo con Montículos
22
Escribir el registro en el archivo fusión y obtener el
siguiente menor
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174, 189,
197, 200, 234
–115, 999
29, 35, 49, 68, 110, 115, 130, 132, 146, 153
Escribir el registro en el archivo fusión y obtener el
siguiente menor
•29, 35, 49, 68, 110, 130, 132, 146, 153, 174, 189,
197, 200, 234
•115, 999
29, 35, 49, 68, 110, 115, 130, 132, 146, 153,
174
ODD - Curso Servetto
Ord. Externo con Montículos
23
Escribir el registro en el archivo fusión y obtener el
siguiente menor
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174, 189,
197, 200, 234
–115, 999
29, 35, 49, 68, 110, 115, 130, 132, 146, 153,
174, 189
Escribir el registro en el archivo fusión y obtener el
siguiente menor
•29, 35, 49, 68, 110, 130, 132, 146, 153, 174, 189,
197, 200, 234
•115, 999
29, 35, 49, 68, 110, 115, 130, 132, 146, 153,
174, 189, 197
ODD - Curso Servetto
Ord. Externo con Montículos
24
Escribir el registro en el archivo fusión y obtener el
siguiente menor
–29, 35, 49, 68, 110, 130, 132, 146, 153, 174, 189,
197, 200, 234, 999
–115, 999
29, 35, 49, 68, 110, 115, 130, 132, 146, 153,
174, 189, 197, 200
Escribir el registro en el archivo fusión y obtener el
siguiente menor
•29, 35, 49, 68, 110, 130, 132, 146, 153, 174, 189,
197, 200, 234, 999
•115, 999
29, 35, 49, 68, 110, 115, 130, 132, 146, 153,
174, 189, 197, 200, 234
ODD - Curso Servetto
Ord. Externo con Montículos
25
Descargar

Ordenación Externa