Ordenamiento por inserción

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere $O(n^{2})$ operaciones para ordenar una lista de $n$ elementos.

Ejemplo de ordenamiento por inserción ordenando una lista de números aleatorios.

Inicialmente, se tiene un solo elemento que, obviamente, es un conjunto ordenado. Después, cuando hay $k$ elementos ordenados de menor a mayor se toma el elemento $k+1$ y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento $k+1$ debiendo desplazarse los demás elementos.

Complejidad temporal

En el mejor de los casos, el arreglo está inicialmente en orden, el algoritmo solo hace una pasada y entonces la complejidad es $O(n)$.​ En el peor caso, con el arreglo ordenado con el criterio contrario, se obtiene una complejidad temporal cuadrática del orden de $O(n^{2}/2)$

Véase también

• Algoritmo de ordenamiento

Bibliografía

Martínez Vidal (2006). Introducción al análisis de algoritmos. Consultado el 22 de junio de 2020. 

Enlaces externos

• Distintas implementaciones del algoritmo en Wikibooks (inglés)
• Distintas implementaciones del algoritmo en RosettaCode.org (inglés)

• Datos: Q117241
• Multimedia: Insertion sort / Q117241