El ordenamiento por inserción es un algoritmo de ordenamiento simple e intuitivo que funciona de manera similar a cómo los humanos ordenan cartas en sus manos. Es especialmente útil para listas pequeñas o listas que ya están parcialmente ordenadas. En esta sección, aprenderemos cómo funciona el algoritmo, analizaremos su complejidad y veremos ejemplos prácticos.

El ordenamiento por inserción construye la lista ordenada de manera incremental, tomando un elemento a la vez y colocándolo en la posición correcta dentro de la lista ya ordenada.

1. Inicialización: Comienza con el segundo elemento de la lista (el primer elemento se considera ya ordenado).
2. Comparación: Compara el elemento actual con los elementos de la lista ordenada.
3. Inserción: Desplaza los elementos mayores hacia la derecha para hacer espacio e inserta el elemento actual en su posición correcta.
4. Repetición: Repite los pasos 2 y 3 para todos los elementos de la lista.

Supongamos que tenemos la lista [5, 2, 4, 6, 1, 3].

1. Inicialización: [5, 2, 4, 6, 1, 3]
2. Comparación e Inserción:
   • 2 se compara con 5 y se inserta antes de 5: [2, 5, 4, 6, 1, 3]
   • 4 se compara con 5 y se inserta antes de 5: [2, 4, 5, 6, 1, 3]
   • 6 se compara con 5 y se queda en su lugar: [2, 4, 5, 6, 1, 3]
   • 1 se compara con 6, 5, 4 y 2 y se inserta al principio: [1, 2, 4, 5, 6, 3]
   • 3 se compara con 6, 5, 4 y se inserta antes de 4: [1, 2, 3, 4, 5, 6]

A continuación, se presenta una implementación del algoritmo de ordenamiento por inserción en Python:

1. Inicialización: for i in range(1, len(arr)) recorre la lista desde el segundo elemento.
2. Comparación: while j >= 0 and key < arr[j] compara el elemento actual (key) con los elementos de la lista ordenada.
3. Inserción: arr[j + 1] = key inserta el elemento en su posición correcta después de desplazar los elementos mayores.

• Mejor Caso: O(n) - Ocurre cuando la lista ya está ordenada.
• Peor Caso: O(n^2) - Ocurre cuando la lista está ordenada en orden inverso.
• Caso Promedio: O(n^2)

• Espacio Auxiliar: O(1) - Solo se utilizan variables adicionales para la clave y el índice.

Ordena la siguiente lista utilizando el algoritmo de ordenamiento por inserción: [8, 3, 1, 7, 0, 10, 2].

Solución:

Modifica el algoritmo de ordenamiento por inserción para que ordene la lista en orden descendente.

Solución:

El ordenamiento por inserción es un algoritmo eficiente para listas pequeñas o parcialmente ordenadas. Aunque su complejidad en el peor caso es O(n^2), su simplicidad y eficiencia en casos específicos lo hacen una herramienta útil en el análisis y diseño de algoritmos. En la siguiente sección, exploraremos otros algoritmos de ordenamiento más eficientes para listas grandes y desordenadas.