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 ${\displaystyle O(n^{2})}$ operaciones para ordenar una lista de ${\displaystyle 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 ${\displaystyle k}$ elementos ordenados de menor a mayor se toma el elemento ${\displaystyle 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 ${\displaystyle k+1}$ debiendo desplazarse los demás elementos.

Pseudocódigo

INSERTION-SORT(A, n)
1  for i = 2 to n
2      key = A[i]
3      // Insert A[i] into the sorted subarray A[1 : i - 1].
4      j = i - 1
5      while j > 0 and A[j] > key
6          A[j + 1] = A[j]
7          j = j - 1
8      A[j + 1] = key

^[1]

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 ${\displaystyle O(n)}$.^[2] En el peor caso, con el arreglo ordenado con el criterio contrario, se obtiene una complejidad temporal cuadrática del orden de ${\displaystyle O(n^{2}/2)}$

Véase también

• Algoritmo de ordenamiento