El algoritmo de clasificación de burbujas requiere un par de bucles anidados. El ciclo externo debe iterar una vez para cada elemento del conjunto de datos (de tamaño n) mientras que el ciclo interno itera n veces la primera vez que se ingresa, n-1 veces la segunda, y así sucesivamente. Considere el propósito de cada ciclo. Como se explicó anteriormente, la clasificación de burbujas está estructurada de modo que en cada paso por la lista, el siguiente elemento más grande de los datos se mueva a su lugar adecuado. Por lo tanto, para obtener todos los n elementos en sus lugares correctos, el ciclo externo debe ejecutarse n veces.
El ciclo interno se ejecuta en cada iteración del ciclo externo. Su propósito es poner en su lugar el siguiente elemento más grande. Por lo tanto, el bucle interno realiza la comparación e intercambio de elementos adyacentes. Para determinar la complejidad de este bucle, calculamos el número de comparaciones que deben realizarse. En la primera iteración del bucle externo, mientras se intenta colocar el elemento más grande, debe haber n – 1 comparaciones: la primera comparación se realiza entre el primer y el segundo elemento, la segunda se realiza entre el segundo y el tercer elemento, y así sucesivamente hasta que se haga la n-1ª comparación entre el n-1º y el nº elemento. En la segunda iteración del ciclo externo, no hay necesidad de comparar el con el último elemento de la lista, porque se colocó en el lugar correcto en la pasada anterior. Por lo tanto, la segunda iteración requiere solo n-2 comparaciones. Este patrón continúa hasta la penúltima iteración del bucle externo cuando solo los dos primeros elementos de la lista están sin clasificar; Claramente en este caso, sólo es necesaria una comparación. El número total de comparaciones, por lo tanto, es (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 o O (n2).
El mejor caso para la ordenación de burbujas ocurre cuando la lista ya está ordenada o casi ordenada. En el caso de que la lista ya esté ordenada, la clasificación de burbujas terminará después de la primera iteración, ya que no se realizaron intercambios. Siempre que se pase a través de la lista y no se realizaron intercambios, es seguro que la lista está ordenada. La clasificación de burbujas también es eficaz cuando es necesario clasificar un elemento aleatorio en una lista ordenada, siempre que el elemento nuevo se coloque al principio y no al final. Cuando se coloca al principio, simplemente burbujeará hasta el lugar correcto, y la segunda iteración a través de la lista generará 0 intercambios, finalizando la clasificación. Recuerde que si el elemento aleatorio se coloca al final, la clasificación de burbujas pierde su eficiencia porque cada elemento mayor que él debe burbujear hasta la parte superior.
El peor caso absoluto para la clasificación de burbujas es cuando el El elemento más pequeño de la lista está en el extremo grande. Debido a que en cada iteración solo el elemento sin clasificar más grande se coloca en su ubicación adecuada, cuando el elemento más pequeño está al final, tendrá que intercambiarse cada vez a través de la lista, y no llegará al principio de la lista hasta que todos Se han producido iteraciones. En el peor de los casos, se necesitan n iteraciones de n / 2 intercambios, por lo que el orden es, nuevamente, n2.
Mejor caso: n Caso promedio: n2 Peor caso: n2