Estructura de Datos : Clasificación MergeSort


Definiciones

              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. Donde : 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 :

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 ..............................>

Donde :

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
                *--*--.................................................--*--*
                |  |                                                     |  |
                *--*--.................................................--*--*
Donde : 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 :

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