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.

9 comentarios:

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

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

    ResponderBorrar
  3. Anónimo11:18 a.m.

    no entendi ni chimbaaa

    ResponderBorrar
  4. Anónimo2:13 p.m.

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

    ResponderBorrar
  5. Anónimo9:10 p.m.

    que putas paridas de mierda

    ResponderBorrar
  6. Anónimo3:44 p.m.

    muy buen codigo

    ResponderBorrar
  7. Anónimo6:34 a.m.

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

    ResponderBorrar
  8. Anónimo4:03 p.m.

    al tomar el numero que vamos a comparar con los anteriores y cuando se inserte en su lugar los otros numeros se recorren en auntomatico??

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...