Ordenación de Ficheros Secuenciales
Informática. Programación. Archivos en Memoria. Estructura de Datos
- Enviado por: El remitente no desea revelar su nombre
- Idioma: castellano
-
País:
España - 5 páginas
Ordenación de Ficheros Secuenciales.-
Generalidades:
Restricción en la clasificación.-
Acceso secuencial a cada uno de los elementos
Mezcla.-
Combinación de secuencias en una sola ordenada por
selección repetida de componentes accesibles en cada
momento.
Mezcla Directa.-
También llamado mezcla o fusión con 3 cintas, un método de ordenación basado en la mezla se describe como sigue:
! 1. Dividir la secuencia a en 2 mitades, b y c.
cinta a=
| 44 | 35 | 12 | 42 | 94 | 18 | 06 | 67 | a |
! b !b !c
cinta b=
| 44 | 35 | 12 | 42 |
cinta c=
| 94 | 18 | 06 | 67 |
!2. Se mezclan b y c combinando cada elemento en pares
ordenados.
b=
!
| 44 | 35 | 12 | 42 |
c=
| 94 | 18 | 06 | 67 |
!
Al ser 2 cintas tenemos visibles 2 cursores (!,!)
y se realiza el proceso de agrupar pares de
componentes accesibles en cada momento
| 44 94 | 55 18 | 12 06 | 42 67 |
Ahora empieza el proceso de ordenación por parejas
!
| 44 94 | 55 18 | 12 06 | 42 67 |
!
al ser 44<94 se coloca en la secuencia a
avanzando los cursores
!
| 44 94 | 55 18 | 12 06 | 42 67 |
!
cinta a=
| 44 | 94 |
|
|
|
|
| a |
!
| 44 94 | 55 18 | 12 06 | 42 67 |
!
cinta a=
| 44 | 94 | 18 | 55 |
|
|
| a |
!
| 44 94 | 55 18 | 12 06 | 42 67 |
!
cinta a=
| 44 | 94 | 18 | 55 | 06 | 12 |
| a |
!
| 44 94 | 55 18 | 12 06 | 42 67 |
!
cinta a=
| 44 | 94 | 18 | 55 | 06 | 12 | 42 | 67 | a |
!3. Llamar a a la secuencia mezclada y repetir los pasos
1 y 2 combinando los pares ordenados en cuádruplos
ordenados.
b= !
| 44 94 06 12 | 18 55 42 67 |
c= !
cinta a=
| 06 |
|
|
|
|
| a |
al comparar (44,06), se coloca en la cinta a 06 y la
cinta c avanza una posición, ahora se compara (12,44)
y se copia en la cinta a el valor 12
b= !
| 44 94 06 12 | 18 55 42 67 |
c= !
posteriormente se copian los valores de la
cinta b en la cinta a
cinta a=
| 06 | 12 | 44 | 94 |
|
| a |
procedamos con el siguiente cuádruplo
b= !
| 44 94 06 12 | 18 55 42 67 |
c= !
al comparar (18,42) copiamos en la cinta a el valor 18
y desplazamos el cursor a 55 y comparamos (42,55) y
copiamos en la cinta a el valor 42, avanzamos el
cursor de la cinta c y comparamos (55,67)
cinta a=
| 06 | 12 | 44 | 94 | 18 | 42 |
| a |
b= !
| 44 94 06 12 | 18 55 42 67 |
c= !
b= !
| 44 94 06 12 | 18 55 42 67 |
c= !
cinta a=
| 06 | 12 | 44 | 94 | 18 | 42 | 55 | 67 | a |
! 4.Seguir duplicando las longitudes de las
subsecuencias combinadas hasta que
quede ordenada toda la secuencia
cinta b= !
| 06 12 44 94 18 42 55 67 |
cinta c= !
cinta a=
| 06 | 12 | 18 | 42 | 44 | 55 | 67 | 94 | a |
secuencia ordenada
Terminología:
Fase:
Cada operación que trate al conjunto entero de
datos una vez. (división,mezcla).
Pase o Etapa:
El proceso más corto que por repetición
constituye el proceso de ordenación.Un
pase consta de fases, una de división y otra
de combinación.
Cinta:
Cada una de las secuencias necesarias en el
proceso de ordenación.