Juan Garcés

Personal Blog

Métodos de Ordenamiento

enero 25th, 2013

Ordenamiento por Burbuja

 

La idea básica de este método de ordenamiento es la de comparar pares de valores de llaves e intercambiarlos si no están en sus posiciones relativas correctas.


Como los métodos de selección e inserción vistos anteriormente, el método de burbuja requiere O(n^2) comparaciones. No obstante, el método de la burbuja es frecuentemente usado.

La idea de este método es la de permitir que cada llave flote a su posición adecuada a través de una serie de pares de comparaciones e intercambios con los valores adyacentes. Cada paso haces que una llave suba a su posición final, como una burbuja, en la lista ordenada.

Consideremos otra vez nuestro ejemplo de lista de llaves no ordenadas:


Cada llave se compara con la llave que está encima de ella (en nuestro caso al lado derecho de ella) y se intercambia, si la llave de arriba es más pequeña. Cuando una llave mayor que la llave sujeto se encuentra, la llave sujeto queda encima, y el proceso continúa. Después de la pasada, todas las llaves arriba de la última por intercambiar deberán estar en su posición final. No necesitarán examinarse en pasos posteriores.

La actividad del primer paso sube a 14, a 22 y a 25.


El método de la burbuja en realidad es muy poco recomendado, sin embargo, es muy conocido (tal vez debido a su nombre) y desafortunadamente muy utilizado (puede ser debido a su relativa facilidad de implementación). Su comportamiento es un poco parecido al método de intercambio selectivo, en el cual las llaves más pequeñas bajan al fondo de la lista.

Este método de ordenamiento también puede funcionar con 2 listas, una de llaves desordenadas y otra de llaves ordenadas, pasando el elemento que flota hasta el final a la lista de ordenados, pero para minimizar el espacio utilizado, trabajaremos con una sola lista.

Una implementación del método de ordenamiento por burbuja puede ser el siguiente:

void Burbuja(Lista Numeros, int Largo)
{
    int ultimo=Largo-1;
    int posicion;
    int auxiliar;
    while(ultimo>=1)
    {
        for(posicion=0;posicion<ultimo;posicion++)
        {
            if(Numeros[posicion]>Numeros[posicion+1])
            {
                auxiliar=Numeros[posicion];
                Numeros[posicion]=Numeros[posicion+1];
                Numeros[posicion+1]=auxiliar;
            };
        };
        ultimo–;
    };
};

 

Juan Garcés

Personal Blog