domingo, octubre 03, 2010

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.

7 comentarios:

Jhoana Torijano Riascos dijo...

PROFE POR FA RECOMIENDAME UN PROGRAMA PARA HACER LA IMPLEMENTACION DE LOS ALGORITMOS...
GRACIAS

JorgeP dijo...

Creo que el mejor ambiente de desarrollo para java es NetBeans. Puedes descargarlo desde la dirección http://netbeans.org

Anónimo dijo...

no entendi ni chimbaaa

Anónimo dijo...

sirve para pura mierda su pinche cochinada de porqueria.......

Anónimo dijo...

que putas paridas de mierda

Anónimo dijo...

muy buen codigo

Anónimo dijo...

nice code ! also u can use Arrays.sort(vector);

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar