Ordenamiento por Inserción

6.1 Definición de ordenamiento por inserción

Ordenamiento por inserción (Insertion Sort) es un algoritmo de ordenamiento que construye un arreglo (o lista) ordenado un elemento a la vez. Toma cada elemento de la parte no ordenada y lo inserta en el lugar correcto en la parte ordenada.

Principio de funcionamiento:

1. Comenzamos con el segundo elemento del arreglo (el primer elemento se considera ordenado).
2. Comparamos el elemento actual con los anteriores y lo movemos a la izquierda hasta encontrar el lugar correcto.
3. Repetimos el proceso para todos los elementos del arreglo, insertando cada nuevo elemento en el lugar correcto en la parte ya ordenada del arreglo.

Complejidad temporal y espacial del ordenamiento por inserción

Complejidad temporal:

• En el peor de los casos: O(n^2) — ocurre cuando los elementos están ordenados en el orden inverso inicialmente.
• En el caso promedio: O(n^2) — ocurre para una disposición aleatoria de elementos.
• En el mejor de los casos: O(n) — ocurre cuando los elementos ya están ordenados.

Complejidad espacial:

O(1) — ya que el algoritmo usa una cantidad constante de memoria adicional (solo algunas variables para almacenar valores temporales).

6.2 Análisis del funcionamiento del algoritmo

En cada paso del algoritmo tenemos la siguiente situación:

• Tenemos un elemento actual con índice i.
• Todos los elementos a la izquierda de él ya están ordenados de menor a mayor.
• Intentamos insertar nuestro elemento actual en la parte ordenada del arreglo de manera que el orden de ordenamiento no se altere.

El intento de insertar un elemento en la parte ordenada del arreglo luce así:

1. La variable j en el ciclo toma el valor de i - 1 a 0.
2. Si el elemento actual (i-ésimo) es menor que el j-ésimo, entonces movemos el valor del elemento j-ésimo un lugar a la derecha.

Ejemplo: situación actual:

• Los elementos en verde ya están ordenados.
• En rosa — los elementos que aún no se han ordenado.
• El elemento actual con índice 5 — se ha marcado en marrón.

Tratamos de encontrar el lugar correcto para nuestro elemento actual en la parte ordenada del arreglo.

Paso 1 — guardamos el valor del elemento actual en la variable key.

Paso 2 — ¿el elemento No4 es mayor que key? (¿10 es mayor que 5?) Entonces movemos el elemento No4 a la derecha:

Paso 3 — ¿el elemento No3 es mayor que key? (¿8 es mayor que 5?) Entonces movemos el elemento No3 a la derecha:

Paso 4 — ¿el elemento No2 es mayor que key? (¿6 es mayor que 5?) Entonces movemos el elemento No2 a la derecha:

Paso 5 — ¿el elemento No1 es mayor que key? (¿4 es mayor que 5?) No. Entonces guardamos el elemento key donde estaba el elemento No2.

Después de que hemos insertado el elemento No5 en el lugar correcto, nos movemos al elemento No6 y tratamos de encontrarle un lugar en la parte ordenada del arreglo:

Luego tomamos el séptimo elemento:

Luego el octavo:

6.3 Implementación del algoritmo de ordenamiento por inserción

Así es como se verá este algoritmo en Python:

def insertion_sort(arr):
    # Recorremos todos los elementos del arreglo, comenzando por el segundo
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Movemos los elementos arr[0..i - 1], que son mayores que la clave, una posición hacia adelante
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Insertamos la clave en el lugar correcto
    return arr  # Devolvemos el arreglo ordenado
        
# Ejemplo de uso:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Arreglo ordenado:", sorted_arr)
# Salida: Arreglo ordenado: [5, 6, 11, 12, 13]

Explicación:

• Guardamos el elemento actual en key
• Movemos todos los elementos de la parte ordenada del arreglo a la derecha
• Insertamos nuestro elemento en el lugar apropiado

Ejemplo del funcionamiento del algoritmo

Tomemos un ejemplo de arreglo: [12, 11, 13, 5, 6]

1. Primer paso (i = 1):

• Comparamos 11 y 12, movemos 12 a la derecha.
• Arreglo: [11, 12, 13, 5, 6]

2. Segundo paso (i = 2):

• 13 ya está en su lugar.
• Arreglo: [11, 12, 13, 5, 6]

3. Tercer paso (i = 3):

• Comparamos 5 con 13, 12 y 11, movemos todos a la derecha.
• Arreglo: [5, 11, 12, 13, 6]

4. Cuarto paso (i = 4):

• Comparamos 6 con 13, 12 y 11, movemos todos a la derecha.
• Arreglo: [5, 6, 11, 12, 13]

El algoritmo se completa, ya que todos los elementos están ordenados.