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.

8 comentarios:

mcknight dijo...

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

JorgeP dijo...

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

Anónimo dijo...

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

Anónimo dijo...

muchas gracia

alejandro maldonado perez dijo...

GRACIAS!!!! MUY BUEN CODIGO

Dargor dijo...

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

Anónimo dijo...

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

Unknown dijo...

Como puedo implementarlo para objetos?

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar