Ordenación por inserción

Se trata de ordenar un arreglo formado por n enteros. Para esto el algoritmo de inserción va intercambiando elementos del arreglo hasta que esté ordenado.

Procedimiento Ordenación por Inserción

( var T [ 1 .. n ] )
para i := 2 hasta n hacer x := T [ i ] ;
j := i – 1 ;
mientras j > 0 y T [ j ] > x hacer
T [ j + 1 ] := T[ j ] ; j := j – 1
fin mientras ; T [ j + 1 ] := x
fin para
fin procedimiento

n es una variable o constante global que indica el tamaño del arreglo.

Los resultados obtenidos dependen, en parte, de la inicialización del arreglo de datos. Este arreglo puede estar inicializado de forma creciente, decreciente o aleatoriamente.

El peor caso ocurre cuando el arreglo está inicializado descendentemente. El mejor caso ocurre cuando el arreglo está inicializado ascendentemente. (En este caso el algoritmo recorre el arreglo hasta el final sin ‘apenas’ realizar trabajo, pues ya está ordenado.)

Se ha calculado empíricamente la complejidad para este algoritmo y se ha obtenido una complejidad lineal cuando el arreglo está inicializado en orden ascendente, y una complejidad cuadrática O(n2), cuando el arreglo está inicializado en orden decreciente y también cuando está inicializado aleatoriamente.

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM