6.3 Ordenación por Inserción

La ordenación por inserción es otro algoritmo simple, pero altamente fundamental en la informática. Ordena una lista construyendo un arreglo ordenado un elemento a la vez, de manera similar a cómo ordenarías una mano de cartas.

Antes de sumergirnos en los detalles del algoritmo, expliquemos el funcionamiento de la Ordenación por Inserción a través de una metáfora fácil de entender. Imagina que estás jugando a un juego de cartas. Te reparten las cartas una por una. A medida que recibes cada carta, la colocas en su posición correcta en relación con las cartas que ya has ordenado en tu mano. ¡Para cuando hayas recibido todas las cartas, tu mano estará ordenada!

La ordenación por inserción es un algoritmo de ordenación fundamental en la informática que se utiliza a menudo en aplicaciones de procesamiento de datos. Es un algoritmo relativamente simple que opera construyendo un arreglo ordenado un elemento a la vez. Para comprender mejor cómo funciona el algoritmo, usemos una metáfora. Imagina que estás organizando tu armario.

Comienzas con un montón de ropa y recoges cada artículo uno por uno. A medida que recoges cada artículo, lo colocas en su posición correcta en relación con la ropa que ya has ordenado. ¡Para cuando hayas pasado por todo el montón, tu armario estará ordenado y organizado! La ordenación por inserción funciona de manera similar, ordenando una matriz insertando cada elemento en su posición ordenada adecuada en relación con los elementos que ya han sido ordenados. Este algoritmo puede parecer simple, pero es una herramienta poderosa para procesar grandes cantidades de datos de manera eficiente.

Aquí tienes el desglose técnico de la Ordenación por Inserción:

Comienza considerando el primer elemento como una "sublista ordenada". Al principio, esta sublista solo contiene el primer elemento de la lista.
Considera el siguiente elemento en la lista. Si es mayor que el elemento en la sublista ordenada, déjalo en su lugar. Si es menor, muévelo a su posición correcta en la sublista ordenada.
Amplía la sublista ordenada para incluir el siguiente elemento. Repite el proceso hasta que todos los elementos de la lista hayan sido cubiertos.

Veamos un ejemplo:

Considera la lista [4,3,2,1].

Después del primer paso, el primer número '4' se considera ordenado.
En el siguiente paso, '3' es menor que '4'. Movemos '3' antes de '4': [3,4,2,1].
Luego, '2' es menor que todos los elementos a su izquierda, así que se mueve al principio: [2,3,4,1].
Finalmente, '1' también necesita moverse al principio: [1,2,3,4].

Así es como se puede implementar la Ordenación por Inserción en Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Testing it
print(insertion_sort([4, 3, 2, 1]))  # Output: [1, 2, 3, 4]

Desde una perspectiva de eficiencia, si bien la ordenación por inserción es eficiente para listas más pequeñas, su complejidad temporal es O(n^2), lo que la hace menos óptima para listas más grandes. Sin embargo, su complejidad espacial es O(1), lo que la convierte en una buena elección cuando la memoria es una restricción. También funciona bien cuando la lista de entrada ya está parcialmente ordenada, solo necesitando tiempo lineal O(n) en el mejor caso.

La simplicidad y eficiencia de la Ordenación por Inserción en ciertas situaciones la convierten en una adición valiosa a tu caja de herramientas algorítmicas. A menudo se utiliza como un bloque de construcción en algoritmos más complejos. ¡Sigamos adelante hacia el próximo tema!

Solo para ampliar un poco el contexto donde la Ordenación por Inserción brilla, es una ordenación estable, lo que significa que mantiene el orden relativo de los elementos con claves de ordenación iguales. En otras palabras, dos elementos equivalentes permanecerán en el mismo orden en la salida ordenada como estaban en la entrada. Esto puede ser importante en ciertas aplicaciones donde el orden original tiene un significado.

Además, la Ordenación por Inserción es un algoritmo en línea. Esto significa que puede ordenar una lista a medida que la recibe. En escenarios donde no se conoce el input completo de antemano, como leer un archivo grande línea por línea, esta característica de la Ordenación por Inserción puede ser muy útil.

En el uso del mundo real, si bien la Ordenación por Inserción es menos eficiente en listas grandes que algoritmos más avanzados como QuickSort, MergeSort o HeapSort, tiene la ventaja de la simplicidad y la facilidad de implementación. Además, es muy eficiente para listas que ya están casi ordenadas.