Ordenament per inserció

Ordenament per inserció

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

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.

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