Estructura de Datos : Clasificación MergeSort

Definiciones

Las condiciones iniciales son las siguientes :

El archivo a clasificar ya está en memoria, dispuesto en slots contiguos.
Los registros del archivo los denominaremos R1, R2, R3, ..., Ri, ..., Rn donde 1=< i =< n.
Existen en memoria n slots, donde en cada uno de ellos se dispone un registro del archivo a clasificar.
Todos los registros tienen una clave Ki, donde i es 1 =< i =< n.
Los registros están desordenados respecto de la clave mencionada.
La clasificación será hecha valiéndose de un archivo de trabajo.

La secuencia de acciones es la siguiente :

Se implementa un procedimiento elemental que mezcla dos subarchivos, que ya están ordenados, en otro archivo, que resultará la suma de los dos subarchivos y también ordenado.
Inicialmente se considera a cada registro del archivo original como un subarchivo ordenado.
Se utiliza el procedimiento elemental, descripto más arriba, para mezclar de a dos los subarchivos ordenados. Luego de este procedimiento la cantidad de subarchivos ordenados pasa de n a n / 2, cada uno de los cuales tiene 2 registros ordenados. En caso de n impar, queda un subarchivo con 1 registro.
Vuelven a mezclarse de a pares los subarchivos ordenados resultantes del punto anterior, hasta que quede un solo archivo, el que quedará clasificado.
Este procedimiento de clasificación requiere almacenamiento adicional, de tamaño igual a la cantidad de registros del archivo original.

              R1   R2   R3             Ri             Rn
   ........------------------.......--------.......--------.......
            | K1 | K2 | K3 |         | Ki |         | Kn |              n slots       Archivo original
   ........------------------.......--------.......--------.......

              R1   R2   R3             Ri             Rn
   ........------------------.......--------.......--------.......
            | K1 | K2 | K3 |         | Ki |         | Kn |              n slots       Archivo de trabajo
   ........------------------.......--------.......--------.......

Ejemplos

Ejemplo 1

En el ejemplo pueden observarse como evolucionan los subarchivos de registros ordenados, subarchivos que están cerrados entre corchetes.

Paso           R1     R2     R3     R4     R5     R6     R7     R8     R9    R10

  1          [ 26 ] [  5 ] [ 77 ] [  1 ] [ 61 ] [ 11 ] [ 59 ] [ 15 ] [ 48 ] [ 19 ]

  2          [  5     26 ] [  1     77 ] [ 11     61 ] [ 15     59 ] [ 19     48 ]

  3          [  1      5     26     77 ] [ 11     15     59     61 ] [ 19     48 ]

  4          [  1      5     11     15     26     59     61     77 ] [ 19     48 ]

  5          [  1      5     11     15     19     26     48     59     61     77 ]

Funciones

MERGE

Necesitamos contar con una funcion elemental de mezcla, la cual utilizaremos reiteradamente. Esta funcion devuelve un archivo ordenado, si recibe dos subarchivos ordenados. Los subarchivos ordenados van desde los indices xl a xm el primero y desde xm+1 a xn el segundo. El archivo final ordenado va de xl a xn y ocupa un espacio adicional igual al espacio que ocupan los dos archivos originales.

              Xl  Xl+1 Xl+2            Xm  Xm+1 Xm+2           Xn-2 Xn-1  Xn
   ........------------------.......------------------.......------------------.......
            |    |    |    |         |    |    |    |         |    |    |    |              n slots       Archivo original
   ........------------------.......------------------.......------------------.......

            |.............. i ...........>|............... j ...............>|


            |--- Subarchivo ordenado 1 -->|------ Subarchivo ordenado 2 ---->|



              Zl  Zl+1 Zl+2            Zm  Zm+1 Zm+2           Zn-2 Zn-1  Zn
   ........------------------.......------------------.......------------------.......
            |    |    |    |         |    |    |    |         |    |    |    |              n slots       Archivo mezclado
   ........------------------.......------------------.......------------------.......

            |............................... k .............................>|


            |<----------------- Archivo ordenado mezclado ------------------>|

Las claves de cada registro se denota con misma letra que los registros, pero en minúscula. Por ejemplo, la clave del registro Xm es xm.

procedure MERGE(X,l,m,n,Z)
- k <---- l
- i <---- k
- j <---- m + 1
- while i =< m and j =< n // Control de los rangos de los subarchivos
  - do
    - if xi =< xj // Comparacion de claves de los subarchivos
      - then
        
        Zk <---- Xi // Muevo el menor al archivo de salida
        i <---- i + 1
      - else
        
        Zk <---- Xj // Muevo el menor al archivo de salida
        j <---- j + 1
      k <---- k + 1
  - end
- if i > m // Determinacion del subarchivo agotado
  - then
    - ( Zk, ..., Zn ) <---- ( Xj, ..., Xn ) // Transfiero el resto del subarchivo no agotado a la salida
  - else
    - ( Zk, ..., Zn ) <---- ( Xi, ..., Xm ) // Transfiero el resto del subarchivo no agotado a la salida
end MERGE

Donde :

X ----> Archivo original
l ----> Indice del primer registro del primer subarchivo ordenado original
m ----> Indice del ultimo registro del primer subarchivo ordenado original
n ----> Indice del ultimo registro del segundo subarchivo ordenado original
Z ----> Archivo ordenado de salida
i ----> Iterador para barrer el primer subarchivo ordenado
j ----> Iterador para barrer el segundo subarchivo ordenado
k ----> Iterador para barrer el archivo ordenado de salida

Observar que los dos subarchivos originales ordenados deben estar contiguos en memoria. Observar que el while controla que se procese solo dentro de los margenes de los dos subarchivos ordenados originales. Observar que en la transferencia del remanente del subarchivo no agotado a la salida uso una notacion abreviada, en realidad se necesitaria de un loop para dicha transferencia. Observar que no es necesario que los subarchivos ordenados sean del mismo ancho, pudiendo ser de cualquier ancho, como muestra la siguiente figura.


            |................... i ................>|...... j .......>|

   ........-------------------------------------------------------------.......
            |    | ........................... |    |    | ..... |    |
   ........-------------------------------------------------------------.......

            l                                  m    m+1          n

MPASS

Esta funcion intermedia sera utilizada repetidamente y administra los pasos requeridos para clasificar un archivo. Como puede apreciarse en el ejemplo 1 :

En el paso 1 los subarchivos clasificados son de ancho igual a 1 ----> ( 2**0 = 1 )

En el paso 2 los subarchivos clasificados son de ancho igual a 2 ----> ( 2**1 = 2 )

En el paso 3 los subarchivos clasificados son de ancho igual a 4 ----> ( 2**2 = 4 )

En el paso 4 los subarchivos clasificados son de ancho igual a 8 ----> ( 2**3 = 8 )

En el paso 5 los subarchivos clasificados son de ancho igual a 16 ----> ( 2**4 = 16 )

Puede apreciarse tambien, que el ultimo subarchivo puede ser de ancho menor a los precedentes.

            <---------- 2a --------->

   ........------------------------------------------------------------------............
            |     a     |     a     |     a     |     a     |     a     | h |
   ........------------------------------------------------------------------............

            1                       2a+1                    4a+1                   h = n - ( 2*a ) - 1

            |............................... i ..............................>

procedure MPASS(X,Y,n,a)
- i <---- 1
- while i =< n - 2 * a + 1 // Controlo ancho archivo original
  - do
    - call MERGE(X, i, i + a - 1, i + 2 * a - 1, Y) // Invoco funcion elemental
    - i <---- i + 2 * a
  - end
- if i + a - 1 < n
  - then
    - call MERGE(X, i, i + a - 1, n, Y) // Invoco funcion elemental
  - else
    - ( Yi, ..., Yn ) <---- ( Xi, ..., Xm )
end MPASS

Donde :

X ----> Archivo original
Y ----> Archivo ordenado de salida
n ----> Cantidad de registros del archivo original
a ----> Ancho de los subarchivos
i ----> Iterador del archivo original

MSORT

Veamos la funcion final, la cual invoca a la intermedia y esta a la elemental. Observar que el archivo de trabajo y el archivo original intercambian sus roles en el algoritmo.

                 X1                                                       Xn
                *--*--.................................................--*--*
                |  |                                                     |  |
                *--*--.................................................--*--*


                 Y1                                                       Yn
                *--*--.................................................--*--*
                |  |                                                     |  |
                *--*--.................................................--*--*

procedure MSORT(X,n)
- a <---- 1 // Inicialmente los subarchivos ordenados son de ancho 1
- while a < n // Hasta que el ancho clasificado sea todo el archivo
  - do
    - call MPASS(X, Y, n, a) // Intercambio los roles de X e Y para reusarlos
    - a <---- 2 * a // Hago crecer al doble el ancho de los subarchivos ordenados
    - call MPASS(Y, X, n, a) // Intercambio los roles de X e Y para reusarlos
    - a <---- 2 * a // Hago crecer al doble el ancho de los subarchivos ordenados
  - end
end MSORT

Donde :

X ----> Archivo original
n ----> Cantidad de registros del archivo original desordenado
a ----> Ancho de los subarchivos

Observar que para clasificar un archivo desordenado de n registros se deben hacer i pasos, siendo i el techo de log2 n.

¨ Cuan rapido puedo clasificar ?

Teniendo en cuenta que los ordenes de magnitud de los siguientes metodos de clasificacion son :

Insert Sort : O(n**2)

Merge Sort : O(n log n)

La pregunta que surge es : ¨ Cuan rapido puedo clasificar ?.
Tener en cuenta que la mejora en el orden de magnitud por clasificar con el Merge Sort acarrea un costo de almacenamiento, que es el doble del uso de memoria del Insert Sort.

Ejercicios

Demostrar que el orden de magnitud del algoritmo MERGE es O(n).

Demostrar que el orden de magnitud del algoritmo PASS es O(n).

Demostrar que el orden de magnitud del algoritmo MSORT es O(n logn).