Algoritmos de ordenación. Metodo de la Burbuja

ALGORITMO DE LA BURBUJA

El algoritmo de la burbuja es uno de los métodos de ordenación más conocidos y uno de los primeros que aprenden los programadores.

Consiste en comparar pares de elementos adyacentes en un array y si están desordenanos intercambiarlos hasta que estén todos ordenados.

Si A es el array a ordenar, se realizan A.length-1 pasadas. Si la variable i es la que cuenta el número de pasadas, en cada pasada i se comprueban los elementos adyacentes desde el primero hasta A.length-i-1 ya que el resto hasta el final del array están ya ordenados. Si los elementos adyacentes están desordenados se intercambian.

El método de ordenación de la burbuja en java para ordenar un array A es el siguiente:

public static void burbuja(int[] A) {
        int i, j, aux;
        for (i = 0; i < A.length - 1; i++) {
            for (j = 0; j < A.length - i - 1; j++) {                                                              
                if (A[j + 1] < A[j]) {
                    aux = A[j + 1];
                    A[j + 1] = A[j];
                    A[j] = aux;
                }
            }
        }
}

Ejemplo de ejecución:

Ya están ordenados, pero los dos bucles for seguirán ejecutándose hasta el final.
El tiempo de ejecución del algoritmo de la burbuja es del orden O(n²)
Es uno de los peores algoritmos de ordenación en cuanto a tiempo de ejecución, solamente es recomendable su uso para ordenar listas con un número pequeño de elementos.