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.