Estructura de Datos : Clasificación InsertSort

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 en los mismos slots donde están los registros, conmutando registros hasta que queden ordenados.
Se dispondrá de un slot ficticio, ubicado en la posición anterior al primer slot, con un registro ficticio cuya clave tiene un valor mucho menor que cualquier clave del archivo. A este registro ficticio lo llamaremos R0.

La secuencia de acciones es la siguiente :

Se implementa un procedimiento elemental que ordena un registro dentro de un subconjunto de registros del archivo, estando formado este subconjunto por los registros que ya están ordenados.
Se dan por ordenados R0 y R1, por lo mencionado en las condiciones iniciales respecto del registro ficticio, que llamamos R0, constituyendose en el primer subarchivo ordenado.
Se utiliza el procedimiento elemental hasta que el archivo quede ordenado.
Luego, uno a uno, todos los registros son incorporados al subconjunto ordenado, hasta que todos los registros queden ordenados.

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

         R0   R1   R2   R3             Ri             Rn
   ...-----------------------.......--------.......--------.......
       | K0 | K1 | K2 | K3 |         | Ki |         | Kn |              n + 1 slots
   ...-----------------------.......--------.......--------.......

Ejemplos

Ejemplo 1

En el ejemplo pueden observarse como evoluciona el subconjunto de registros ordenados, subconjunto que está cerrado entre corchetes. Se aprecian también la variable del loop i y la posición de comienzo y final del subconjunto ya ordenado.

         R0    R1    R2    R3    R4    R5
                                                                        Subarchivo
                5     4     3     2     1        Secuencia Inicial     Desde  Hasta

     [ -999 ]   5     4     3     2     1        i = 0                   0      0

     [ -999     5 ]   4     3     2     1        i = 1                   0      1

     [ -999     4     5 ]   3     2     1        i = 2                   0      2

     [ -999     3     4     5 ]   2     1        i = 3                   0      3

     [ -999     2     3     4     5 ]   1        i = 4                   0      4

     [ -999     1     2     3     4     5 ]      i = 5                   0      5

Ejemplo 2

         R0    R1    R2    R3    R4    R5
                                                                        Subarchivo
                2     3     4     5     1        Secuencia Inicial     Desde  Hasta

     [ -999 ]   2     3     4     5     1        i = 0                   0      0

     [ -999     2 ]   3     4     5     1        i = 1                   0      1

     [ -999     2     3 ]   4     5     1        i = 2                   0      2

     [ -999     2     3     4 ]   5     1        i = 3                   0      3

     [ -999     2     3     4     5 ]   1        i = 4                   0      4

     [ -999     1     2     3     4     5 ]      i = 5                   0      5

Funciones

INSERT

Este procedimiento ubica ordenadamente el registro R dentro del subarchivo que vá desde el registro R0 hasta el registro Ri, subarchivo que yá está ordenado. Antes del procedimiento el subarchivo ordenado tiene i + 1 registros, debido a la presencia del registro R0. Como consecuencia del procedimiento el subarchivo ordenado crece en un registro, o sea, se eleva a i + 2.

procedure INSERT(R,i)

j <---- i
while K < Kj
- Rj+1 <---- Rj
- j <---- j - 1
end
Rj+1 <---- R

end INSERT

donde :

R es el registro a insertar y es el que tiene la clave K
i es el numero de registros del subarchivo ordenado, cuyos registros son R1, R2, ..., Rn y sus claves K1, k2, ..., Kn respectivamente.

                                           K     K   K            K    K
                                           >     <   <            <    <
                                          Km-1  Km  Km+1         Ki-1  Ki

              R0   R1   R2   R3           Rm-1  Rm  Rm+1         Ri-1  Ri  Ri+1
         ..-----------------------.......----------------.......----------------.....................................
            | K0 | K1 | K2 | K3 |        |Km-1| Km |Km+1|       |Ki-1| Ki | ** |   ** Se asume libre para ser usado        i + 2 slots
         ..-----------------------.......----------------.......----------------.....................................
   *---*                                   .      .  . .  .    .  . .  . .  .
 R | K |.................>..................      ..>. ..>.    ..>. ..>. ..>.
   *---*
                 <------------------------ i ----------------------------->

            <---------------------------- i+1 ---------------------------->

            <---------------------------- i+2---------------------------------->

Observar que la creación de R0 simplifica el while, evitando controlar el fin de archivo, en este caso debería hacerse a través de la interrogación de si j < 1. Con la disposición mostrada el while siempre termina, ya que K < Kj en algún momento es falso, aunque mas no sea al alcanzar K0. Debido a este hecho de insertar un registro en un subarchivo ordenado, es que recibe el nombre de clasificación por inserción. Observar que en el peor caso, este algoritmo hace i + 1 comparaciones antes de hacer la insercion. Por lo tanto su orden de magnitud es lineal, del tipo O(i).

INSORT

Este procedimiento utiliza el procedimiento anterior.

procedure INSORT(R,n)

K0 <---- -999
for j <---- 2 to n do
- T <---- Rj
- call INSERT(T,j-1)
end

end INSERT

Donde :

R es un archivo desordenado de n registros, R1, R2, ..., Rn, cuyas claves son K1, K2, ..., Kn respectivamente.
n es la cantidad de registros del archivo desordenado.

En el siguiente dibujo, T es un slot auxiliar para guardar temporariamente un registro, el registro de la iteracion dentro del loop.

                                  T
                                *---*
                                |   | <......................................
                                *---*                                       .
                                  .        K     K   K            K    K    .
                                  .        >     <   <            <    <    .
                                  .       Km-1  Km  Km+1         Kj-2  Kj   .
                                  ....>.....                                .
                                           .                                .
              R0   R1   R2   R3           Rm-1  Rm  Rm+1         Rj-2 Rj-1  Rj            Rn
   ........-----------------------.......----------------.......----------------.......--------.......
            | K0 | K1 | K2 | K3 |        |Km-1| Km |Km+1|       |Kj-2|Kj-1| Rj |        | Kn |              n + 1 slots
   ........-----------------------.......----------------.......----------------.......--------.......
                                             .  . .  . .  .    .  . .  . .  .
                                             .>.. .>.. .>..    .>.. .>.. .>..

                 <----------------------- j-1 ---------------------------->

            <----------------------------- j ----------------------------->

            <---------------------------- j+1---------------------------------->

Este procedimiento invoca a INSERT para i = 2, ..., n, con lo que en el peor caso, las comparaciones suman 2 + 3 + 4 + ... + ( n - 1 + 1 ), lo que nos lleva a un orden de magnitud del tipo O(n**2), n veces n, n**2. El tiempo de ejecución de este algoritmo depende del grado de desorden del juego de registros en su estado original y en el peor caso es O(n**2). Este método de clasificación es muy rápido para clasificar entre 20 y 25 registros, dependiendo de la implementación y propiedades de la máquina donde corre.