Ordenament per inserció

El ordenament per inserció (insertion sort en anglés) és una manera molt natural d'ordenar per a un ser humà i pot usar-se fàcilment per a ordenar un mall de cartes numerades en forma arbitrària. Requerix $O(n^2)$ operacions per a ordenar una llista de $n$ elements.

Ordenament per inserció

Eixemple d'ordenament per inserció ordenant una llista de números aleatoris.

Inicialment, es té un sol element que, òbviament, és un conjunt ordenat. Despuix, quan hi ha $k$ elements ordenats de menor a major es pren l'element $k+1$ i es compara en tots els elements ya ordenats, detenint-se quan es troba un element menor (tots els elements majors han segut desplaçats una posició a la dreta) o quan ya no es troben elements (tots els elements varen ser desplaçats i est és el més menut). En este punt es inserta l'element $k+1$ devent desplaçar-se els demés elements.

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

Complexitat temporal

En el millor dels casos, l'apany està inicialment en orde, l'algoritme solament fa una passada i llavors la complexitat és $O(n)$. En el pijor cas, en l'apany ordenat en el criteri contrari, s'obté una complexitat temporal quadràtica de l'orde de $O(n^2/2)$

Vore també

• Algoritme d'ordenament