Ordenación por Inserción

El algoritmo de ordenación por inserción toma cada elemento a partir del segundo y recorre el vector en sentido inverso ubicando el elemento en su posición correcta haciendo los intercambios necesarios. Cuando termina de ubicar un elemento en su posición correcta, continúa con el siguiente elemento hasta hacer este proceso con todos los elementos del arreglo.

La implementación de este algoritmo en lenguaje JAVA es la siguiente:

// Algoritmo de ordenacion por insercion
    public static void ordenacionInsercion(int[] v) {
        final int N = v.length;
        for(int i=1; i<N; i++) {
            int j=i;
            while(j>0 && v[j]<v[j-1] ){
                int tmp = v[j];
                v[j]    = v[j-1];
                v[j-1]  = tmp;
                j--;
            }
        }
    }

La complejidad del algoritmo es cuadrática, puesto que cada para insertar el elemento en su posición correcta se deben recorrer los elementos anteriores a él. Sin embargo, este algoritmo presenta un mejor desempeño que otros algoritmos de complejidad cuadrática pues no es necesario recorrer para cada elemento la totalidad de los elementos anteriores, sino solamente hasta la posición correcta para un elemento en particular. Se puede probar con la ecuación de recurrencias T(n) = k n + T(n-1) con la tecnología del motor de cálculo WolframAlpha.