jueves, septiembre 30, 2010

Ordenación por Montículos - Heap Sort

El algoritmo de ordenación por montículos o Heap Sort recorre el conjunto de elementos desde la posición de la mitad hasta la primera organizando el montículo correspondiente a dicho elemento.  Una vez terminado este proceso, se inicia el proceso de ordenación intercambiando el primer elemento por el último del arreglo y reorganizando el montículo a partir de la primera posición.

// Ordenacion por monticulos - HeapSort
    public static void ordenacionMonticulos(int[] v) {
        final int N = v.length;
        for(int nodo = N/2; nodo>=0; nodo--) hacerMonticulo(v, nodo, N-1);
        for(int nodo = N-1; nodo>=0; nodo--) {
            int tmp = v[0];
            v[0]    = v[nodo];
            v[nodo] = tmp;
            hacerMonticulo(v, 0, nodo-1);
        }
    }

    public static void hacerMonticulo(int[] v, int nodo, int fin) {
        int izq = 2*nodo+1;
        int der = izq+1;
        int may;
        if(izq>fin) return;
        if(der>fin) may=izq;
        else may= v[izq]>v[der]?izq:der;
        if(v[nodo] < v[may]) {
            int tmp = v[nodo];
            v[nodo] = v[may];
            v[may]  = tmp;
            hacerMonticulo(v, may, fin);
        }
    }

La complejidad del algoritmo de ordenación por montículos es O(n log n) teniendo en cuenta que el proceso de organizar el montículo en el peor caso solamente tiene que hacer intercambios sobre una sola línea de elementos desde la raíz del ábol hasta alguna de las hojas para un máximo de log n intercambios.

14 comentarios:

  1. gracias, es de mucha utilidad, aunque solo necesitava la pura teoria :O

    ResponderBorrar
  2. Con mucho gusto y siéntete en libertad de preguntar o solicitar información adicional, que si está en mis manos, con mucho gusto.

    ResponderBorrar
    Respuestas
    1. Anónimo11:46 p.m.

      Como se podría implementar en modo gráfico ese metodo

      Borrar
  3. Anónimo3:56 p.m.

    muchas gracias me salvaste la vida muy agradecido !!!!

    ResponderBorrar
  4. Anónimo7:01 p.m.

    muchas gracia

    ResponderBorrar
  5. GRACIAS!!!! MUY BUEN CODIGO

    ResponderBorrar
  6. Una consulta, cual es el calculo de la complejidad de este algoritmo?

    ResponderBorrar
  7. Anónimo12:37 p.m.

    El may es la equivalencia aun valor mayor en este algoritmo?

    ResponderBorrar
  8. Como puedo implementarlo para objetos?

    ResponderBorrar
  9. Alguien me puede decir como implemento en java algo que aparece así T[i..j], esta en un algoritmo que nos dejó de tarea y no tengo idea pues es un parámetro para un método, y no se si se refiere a una matriz un vector o que?? Y si es vector no envían parámetros i, j.

    ResponderBorrar
  10. Gracias por el aporte, me funciono sin problema alguno.
    Para quien lo necesite, solo se tiene que hacer un método para ver el arreglo, agrego lo que hice.

    public static void ver(int arreglo[]){
    for(int i = 0; i < arreglo.length; i++){
    System.out.print(arreglo[i] + " ");
    }
    System.out.println("");
    }
    public static void main(String[] args) throws Exception {
    int arreglo[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    ver(arreglo);
    ordenacionMonticulos(arreglo);
    ver(arreglo);
    }

    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...