19.2. Ordenamiento por inserción

Éste otro método de ordenamiento se basa en la siguiente idea:

Paso 0: Partimos de la misma lista de ejemplo utilizada para el ordenamiento por selección.

Lista = | 3 | 2 | -1 | 5 | 0 | 2 |

Paso 1: Considerar el segundo elemento de la lista, y ordenarlo respecto del primero, desplazándolo hasta la posición correcta, si corresponde.

Lista = | 2 | 3 | -1 | 5 | 0 | 2 |

Se desplaza el valor 2 antes de 3.

Paso 2: Considerar el tercer elemento de la lista, y ordenarlo respecto del primero y el segundo, deplazándolo hasta la posición correcta, si corresponde.

Lista = | -1 | 2 | 3 | 5 | 0 | 2 |

Se desplaza el valor —1 antes de 2 y de 3.

Paso 3: Considerar el cuarto elemento de la lista, y ordenarlo respecto del primero, el segundo y el tercero, deplazándolo hasta la posición correcta, si corresponde.

El 5 está correctamente ubicado respecto de —1, 2 y 3 (como el segmento hasta la tercera posición está ordenado, basta con comparar con el tercer elemento del segmento para verificarlo).

Paso N-1:

Todos los elementos excepto el ante-último ya se encuentran ordenados.

Paso N: Considerar el N–ésimo elemento de la lista, y ordenarlo respecto del segmento formado por el primero hasta el N − 1–ésimo, deplazándolo hasta la posición correcta, si corresponde.

Lista = | -1 | 0 | 2 | 2 | 3 | 5 |

Se desplaza el valor 2 antes de 3 y de 5.

Una posible implementación en Python de este algoritmo se incluye en el código 19.2.

La función principal, ord_insercion, recorre la lista desde el segundo elemento hasta el último, y cuando uno de estos elementos no está ordenado con respecto al anterior, llama a la función auxiliar reubicar, que se encarga de colocar el elemento en la posición que le corresponde.

En la función reubicar se busca la posición correcta donde debe colocarse el elemento, a la vez que se van corriendo todos los elementos un lugar a la derecha, de modo que cuando se encuentra la posición, el valor a insertar reemplaza al valor que se encontraba allí anteriormente.

En las siguientes ejecuciones puede verse que funciona correctamente.

>>> l=[3, 2,-1,5, 0, 2]
>>> ord_insercion(l)
DEBUG:   [2,    3,   -1,   5,   0,   2]
DEBUG:   [-1,   2,   3,    5,   0,   2]
DEBUG:   [-1,   2,   3,    5,   0,   2]
DEBUG:   [-1,   0,   2,    3,   5,   2]
DEBUG:   [-1,   0,   2,    2,   3,   5]
>>> print l
[-1, 0, 2, 2, 3, 5]
>>> l=[]
>>> ord_insercion(l)
>>> l=[1]
>>> ord_insercion(l)
>>> print l
[1]
>>> l=[1,2,3,4,5,6]
>>> ord_insercion(l)
DEBUG: [1, 2, 3, 4, 5, 6]
DEBUG: [1, 2, 3, 4, 5, 6]
DEBUG: [1, 2, 3, 4, 5, 6]
DEBUG: [1, 2, 3, 4, 5, 6]
DEBUG: [1, 2, 3, 4, 5, 6]
>>> print l
[1, 2, 3, 4,     5,   6]

# Código 19.2: insercion.py: Ordena una lista por Inserción

#!/usr/bin/env python
#encoding: latin1

def ord_insercion(lista):
    """ Ordena una lista de elementos según el método de inserción.
        Pre: los elementos de la lista deben ser comparables.
        Post: la lista está ordenada. """

    # i va desde la primera hasta la penúltima posición de la lista
    for i in xrange(len(lista)-1):
        # Si el elemento de la posición i+1 está desordenado respecto
        # al de la posición i, reubicarlo dentro del segmento (0:i]
        if lista[i+1]< lista[i]:
            reubicar(lista, i+1)

        print "DEBUG: ", lista

def reubicar(lista, p):
    """ Reubica al elemento que está en la posición p de la lista
        dentro del segmento (0:p-1].
        Pre: p tiene que ser una posicion válida de lista. """

    # v es el valor a reubicar
    v = lista[p]

    # Recorre el segmento (0:p-1] de derecha a izquierda hasta
    # encontrar la posición j tal que lista(j-1] <= v < lista(j].
    j = p
    while j > 0 and v < lista[j-1]:
        # Desplaza los elementos hacia la derecha, dejando lugar
        # para insertar el elemento v donde corresponda.
        lista[j] = lista[j-1]
        # Se mueve un lugar a la izquierda
        j -= 1

    # Ubica el valor v en su nueva posición
    lista[j] = v

19.2.1. Invariante del ordenamiento por inserción

En el ordenamiento por inserción, a cada paso se considera que los elementos que se encuentran en el segmento de 0 a i están ordenados, de manera que agregar un nuevo elemento implica colocarlo en la posición correspondiente y el segmento seguirá ordenado.

19.2.2. ¿Cuánto cuesta ordenar por inserción?

Del código 19.2 se puede ver que la función principal avanza por la lista de izquierda a derecha, mientras que la función reubicar cambia los elementos de lugar de derecha a izquierda.

Lo peor que le puede pasar a un elemento que está en la posición j es que deba ser ubicado al principio de la lista. Y lo peor que le puede pasar a una lista es que todos sus elementos deban ser reubicados.

Por ejemplo, en la lista [10, 8, 6, 2, -2, -5], todos los elementos deben ser reubicados al principio de la lista.

En el primer paso, el segundo elemento se debe intercambiar con el primero; en el segundo paso, el tercer elemento se compara con el segundo y el primer elemento, y se ubica adelante de todo; en el tercer paso, el cuarto elemento se compara con el tercero, el segundo y el primer elemento, y se ubica adelante de todo; etc...

T(N) = c * (2 + 3 + . . . + N ) = c * N * (N + 1)/2 = N^2

Es decir que ordenar por inserción una lista de tamaño N puede insumir (en el peor caso) tiempo del orden de N^2. En cuanto al espacio utilizado, nuevamente sólo se tiene en memoria la lista que se desea ordenar y algunas variables de tamaño 1.

19.2.3. Inserción en una lista ordenada

Sin embargo, algo interesante a notar es que cuando la lista se encuentra ordenada, este algoritmo no hace ningún movimiento de elementos, simplemente compara cada elemento con el anterior, y si es mayor sigue adelante.

Es decir que para el caso de una lista de N elementos que se encuentra ordenada, el tiempo que insume el algoritmo de inserción es:

T(N) = N