Algoritmo BubbleSort

Introducción y Descripción del Algoritmo

El algoritmo de ordenamiento por burbujeo (o bubblesort) es un algoritmo "simple" de ordenamiento. La idea es que se van a comparar pares consecutivos de elementos, y en caso en que estén desordenados, es decir que el primer elemento (izquierda) sea mayor al segundo (derecha), se hará un intercambio de posiciones.

Ejemplo bien simple para una lista de dos elementos:

Ej1: [ 20, 45 ] -> [ 20, 45 ]
Ej2: [ 45, 20 ] -> [ 20, 45 ]

Vamos a llegar de a poco a la solución final del algoritmo, vamos por partes.

Primer Intento, 1 Iteración

Entonces, si tenemos que comparar cada elemento con el siguiente, podríamos pensar que el algoritmo es:

Iterar cada elemento de la lista (hasta el anteúltimo), e ir comparándolo con el siguiente.
Cambiarlos de posiciones si están desordenados

Una implementación de esto en Python sería:

def bubbleSort1Iteracion(lista):

    for i in xrange(len(lista) - 1):

        if lista[i] > lista[i+1]:

            lista[i], lista[i+1] = lista[i+1], lista[i]

    return lista

En los ejemplos anteriores teníamos solo dos elementos, entonces con una única comparación ya nos alcanzó para ordenar toda la lista.

Qué pasa si tengo más de dos elementos ?

Paso 0: [ 45, 20, 23 ]
Paso 1: [ 20, 45, 23 ]
Paso 2: [ 20, 23, 45 ]

Como vemos acá tuvimos que hacer 2 comparaciones. Sin embargo al ir comparando cada uno de los elementos desde el inicio hasta el anteultimo con su siguiente, pudimos ordenar la lista completamente. O sea nuestro algoritmo parece válido hasta ahora.

Veamos otro ejemplo con más elementos y aún más desordenados:

Paso 0: [ 45, 20, 23, -1, 44 ]
Paso 1: [ 20, 45, 23, -1, 44 ]
Paso 2: [ 20, 23, 45, -1, 44 ]
Paso 3: [ 20, 23, -1, 45, 44 ]
Paso 4: [ 20, 23, -1, 44, 45 ]

Ahí fuimos comparando cada elemento con el siguiente. Y pudo de esta forma correr el 45 (el máximo elemento de la lista) hasta el final.

Sin embargo, vemos que sigue desordenado, porque el -1 está en el medio !

[ 20, 23, -1, 44, 45 ]

Eso quiere decir que no alcanza con iterar la lista una única vez e ir comparando cada elemento con el siguiente

Debemos volver a iterar y comparar nuevamente, para seguir subiendo los mayores y bajando los menores (burbujear).

Segundo Intento, N Iteraciones

Entonces, no nos alcanza con una única iteración. Así que hacemos otra implementación del algoritmo que haga lo mismo que la anterior, solo que varias veces. Cuántas ? N, donde N es la cantidad de elementos que tiene la lista.

def bubbleSortNIteraciones(lista):

    for _ in xrange(len(lista)):

        for i in xrange(len(lista) - 1):

            if lista[i] > lista[i+1]:

                lista[i], lista[i+1] = lista[i+1], lista[i]

    return lista

Ahora probamos nuevamente con el mismo ejemplo:

print bubbleSortNIteraciones([45,20,23,-1,44])

>>> [-1, 20, 23, 44, 45]

Ahora sí vemos que quedó bien ordenado. Esta implementación entonces es la (primera) correcta.

Optimizaciones

Veamos paso a paso la ejecución de nuestro ejemplo anterior:

Iteración 1,
Iteración 2,
Iteración 3,
- Iteración 4:
  - Paso 0: [ -1, 20, 23, 44, 45 ]
  - Paso 1: [ -1, 20, 23, 44, 45 ]
  - Paso 2: [ -1, 20, 23, 44, 45 ]
  - Paso 3: [ -1, 20, 23, 44, 45 ]
  - Paso 4: [ -1, 20, 23, 44, 45 ]
- Iteración 5:
  - Paso 0: [ -1, 20, 23, 44, 45 ]
  - Paso 1: [ -1, 20, 23, 44, 45 ]
  - Paso 2: [ -1, 20, 23, 44, 45 ]
  - Paso 3: [ -1, 20, 23, 44, 45 ]
  - Paso 4: [ -1, 20, 23, 44, 45 ]

Acá podemos notar varias cosas:

Conejos y Tortugas: la velocidad con la que se mueven los elementos grandes hacia atrás y los chicos hacia adelante.
Pasos innecesarios: Que tenemos pasos de más en cada iteración.
Iteraciones innecesarias: Que podríamos tener iteraciones de más que no hacen nada.

Veamos cada punto...

Conejos y Tortugas

Como mencionan en wikipedia algo que podemos notar es que con este algoritmo:

Los elementos más grandes se corren hacia la derecha (hacia el fondo) bastante rápido. Por eso se los suele llamar conejos.
En cambio los elementos "menores" que se encuentran muy atrás, se van acomodando hacia adelante en forma más lenta. Por eso se los llama tortugas.

Un ejemplo claro de esto lo vemos en la primer iteración:

Iteración 1,

Acá vemos que el 45, el máximo elemento de la lista, se va derechito hasta el final. Un conejo!

En cambio fíjense que el -1 es el mínimo, y llega a su posición final recién en el Paso 1 de la Iteración 3. Una torguga !

Iteración 1,
Iteración 2,
Iteración 3,

Por qué sucede este comportamiento ?

Fácil, porque nuestro algoritmo va recorriendo desde principio hacia el fin de la lista, y va de alguna forma desplazando el mayor (entre comparar pares), hacia atrás. Entonces cuando agarra el máximo lo va a ir deplazándo complétamente hacia la derecha (atrás) dónde va a terminar para el final de la iteración.

En cambio no se garantiza que el mínimo haya quedado en la izquierda, porque cuando lo encontramos, no sabemos que es el mínimo, solo sabemos que es menor que el anterior, por lo que le cambiamos el lugar. Así que a lo sumo en una iteración se mueve 1 posición hacia la izquierda

Es importante entender esto para el siguiente punto.

Acá un diagrama animado que muestra esta idea:

Pasos Innecesarios: Acotando Pasos en Iteraciones

Vimos entonces que los conejos (elementos más grandes) van hacia el final muy rápidamente porque ese es el sentido de iteración ! Hacía el fondo. (Podríamos probar una implementación inversa que vaya desde el fin hacia el principio moviendo los más chicos hacia el principio. Sería lo mismo)

Entonces, podemos saber que:

En la primer iteración el máximo elemento va a terminar último
En la segunda iteración, el anterior al máximo va a terminar en el anteúltimo
- ... (etc)
- A saber: Iteración N => asegura que el elemento en la posición (tamaño - N) estará bien ordenado.

Resaltemos eso en nuestro ejemplo:

Iteración 1,
Iteración 2,
Iteración 3,
- Iteración 4:
  - Paso 0: [ -1, 20, 23, 44, 45 ]
  - Paso 1: [ -1, 20, 23, 44, 45 ]
  - Paso 2: [ -1, 20, 23, 44, 45 ]
  - Paso 3: [ -1, 20, 23, 44, 45 ]
  - Paso 4: [ -1, 20, 23, 44, 45 ]
- Iteración 5:
  - Paso 0: [ -1, 20, 23, 44, 45 ]
  - Paso 1: [ -1, 20, 23, 44, 45 ]
  - Paso 2: [ -1, 20, 23, 44, 45 ]
  - Paso 3: [ -1, 20, 23, 44, 45 ]
  - Paso 4: [ -1, 20, 23, 44, 45 ]

Esto indica que a medida que avanzan las iteraciones el final de la lista ya está ordenado, ya tiene los elementos definitivos. Sin embargo por cada iteración nosotros estamos comparando todos los elementos con su siguiente. Veamos arriba de nuevo, el primer paso que no tiene sentido es Iteración 2, Paso 4

Marquemos los pasos innecesarios:

Iteración 1,
Iteración 2,
Iteración 3,
- Iteración 4:
  - Paso 0: [ -1, 20, 23, 44, 45 ]
  - Paso 1: [ -1, 20, 23, 44, 45 ]
  - Paso 2: [ -1, 20, 23, 44, 45 ]
  - Paso 3: [ -1, 20, 23, 44, 45 ]
  - Paso 4: [ -1, 20, 23, 44, 45 ]
- Iteración 5:
  - Paso 0: [ -1, 20, 23, 44, 45 ]
  - Paso 1: [ -1, 20, 23, 44, 45 ]
  - Paso 2: [ -1, 20, 23, 44, 45 ]
  - Paso 3: [ -1, 20, 23, 44, 45 ]
  - Paso 4: [ -1, 20, 23, 44, 45 ]

Como vemos en cada iteración se requiere un paso menos. De hecho la Iteración 5 no tiene sentido porque ninguno de sus pasos haría un reordenamiento, ya que todo está ordenado.

Entonces si los elementos se van ubicando desde el final hacia el principio podemos pensar como que cada iteración solo debe trabajar con una "sublista", desde el principio hasta N.Ejemplo:

Iteración 1,
Iteración 2,
Iteración 3,
Iteración 4:

Fíjense:

Nro Elementos "N" = 5

Iteraciones: N - 1
Pasos Iteracion(i) = N - i

Entonces ya podemos repensar nuestra implementación:

N - 1 veces hacer con indice "i"
- N - i veces hacer con indice "j"
  - comparar y ordenar lista[j] , lista[j+1]

Acá la implementación en Python:

def bubblesort(lista):

    for i in xrange(len(lista) - 1):

        for j in xrange(len(lista) - i - 1):

            if lista[j] > lista[j+1]:

                lista[j], lista[j+1] = lista[j+1], lista[j]

Y si analizamos paso a paso la ejecución para esta otra lista más grande:

unaLista = [2, 124, 23, 5, 89, -1, 44, 643, 34]

bubblesort(unaLista)

(i,j) = lista

----------------------------------------------------------------------------------------------------

(0,0) = [ 2 124 23 5 89 -1 44 643 34 ]

(0,1) = [ 2 23 124 5 89 -1 44 643 34 ]

(0,2) = [ 2 23 5 124 89 -1 44 643 34 ]

(0,3) = [ 2 23 5 89 124 -1 44 643 34 ]

(0,4) = [ 2 23 5 89 -1 124 44 643 34 ]

(0,5) = [ 2 23 5 89 -1 44 124 643 34 ]

(0,6) = [ 2 23 5 89 -1 44 124 643 34 ]

(0,7) = [ 2 23 5 89 -1 44 124 34 643 ]

(1,0) = [ 2 23 5 89 -1 44 124 34 643 ]

(1,1) = [ 2 5 23 89 -1 44 124 34 643 ]

(1,2) = [ 2 5 23 89 -1 44 124 34 643 ]

(1,3) = [ 2 5 23 -1 89 44 124 34 643 ]

(1,4) = [ 2 5 23 -1 44 89 124 34 643 ]

(1,5) = [ 2 5 23 -1 44 89 124 34 643 ]

(1,6) = [ 2 5 23 -1 44 89 34 124 643 ]

(2,0) = [ 2 5 23 -1 44 89 34 124 643 ]

(2,1) = [ 2 5 23 -1 44 89 34 124 643 ]

(2,2) = [ 2 5 -1 23 44 89 34 124 643 ]

(2,3) = [ 2 5 -1 23 44 89 34 124 643 ]

(2,4) = [ 2 5 -1 23 44 89 34 124 643 ]

(2,5) = [ 2 5 -1 23 44 34 89 124 643 ]

(3,0) = [ 2 5 -1 23 44 34 89 124 643 ]

(3,1) = [ 2 -1 5 23 44 34 89 124 643 ]

(3,2) = [ 2 -1 5 23 44 34 89 124 643 ]

(3,3) = [ 2 -1 5 23 44 34 89 124 643 ]

(3,4) = [ 2 -1 5 23 34 44 89 124 643 ]

(4,0) = [ -1 2 5 23 34 44 89 124 643 ]

(4,1) = [ -1 2 5 23 34 44 89 124 643 ]

(4,2) = [ -1 2 5 23 34 44 89 124 643 ]

(4,3) = [ -1 2 5 23 34 44 89 124 643 ]

(5,0) = [ -1 2 5 23 34 44 89 124 643 ]

(5,1) = [ -1 2 5 23 34 44 89 124 643 ]

(5,2) = [ -1 2 5 23 34 44 89 124 643 ]

(6,0) = [ -1 2 5 23 34 44 89 124 643 ]

(6,1) = [ -1 2 5 23 34 44 89 124 643 ]

(7,0) = [ -1 2 5 23 34 44 89 124 643 ]

Leyenda:

En rojo los elementos que se movieron a la derecha
Subrayados los pares que se compararon en dicho paso.
En degradé o con colores más claros a la derecha las partes de la lista que ya están ordenadas por los pasos anteriores. Esto deja resaltada entonces la sublista que se está trabajando en cada iteración
Con diferentes colores los pasos de cada iteración.

Iteraciones Innecesarias: Atajo para acotar Iteraciones

Todavía podemos realizar una optimización más.

Veamos el ejemplo anterior. Cuántos movimientos se hicieron por iteración:

Iteración 0: 6
Iteracion 1: 4
Iteracion 2: 2
Iteracion 3: 2
Iteracion 4: 1
Iteracion 5: 0
Iteracion 6: 0
Iteracion 7: 0

Qué quiere decir que en la iteración 5 no se haya realizado ningún movimiento ??

Quiere decir que se recorrió toda la lista (en realidad solo hasta el elemento 4 porque lo que sigue ya estará con los valores máximos, comparando, y no hubo ningún elemento que fuera mayor al siguiente. Esto quiere decir que esa "sublista" ya está ordenada de menor a mayor !!

Con lo cual, una vez que una iteración no realizar ningún movimiento, no hay forma de que las siguientes tenga que modificar algo. Con lo cual no tiene sentido seguir ejecutando.

Esto nos dá pié a realizar una nueva mejora para cortar la ejecución antes.

def bubblesortConAtajo(lista):

    for i in xrange(len(lista) - 1):

        cambio = False

        for j in xrange(len(lista) - i - 1):

            if lista[j] > lista[j+1]:

                lista[j], lista[j+1], cambio = lista[j+1], lista[j], True

        if not cambio: break

Versión Recursiva

Hasta ahora veníamos trabajando con todas versiones secuenciales, es decir que iteraban con ciclos. Sin embargo como ya vimos hay un patrón en las iteraciones. Podiamos ver cada iteración como el procesamiento de una sublista, ya que la iteración anterior se ocupó de "burbujear" el elemento más grande a la última posición. Definamos entonces una versión recursiva:

Caso Base: bubbleSort de una lista de un elemento, retorna esa misma lista

Regla Recursiva:

Acá la versión en Python:

def bubblesortRecursivo(lista):

    if len(lista) == 1: return lista

    burbujear(lista)

    return bubblesortRecursivo(inicio(lista)) + [lista[-1]]

def burbujear(lista):

    for i in xrange(len(lista) - 1):

        if lista[i] > lista[i+1]:

            lista[i], lista[i+1] = lista[i+1], lista[i]

Fíjense que la implementación de burbujear igual la hicimos iterativa. Se podría haber hecho también recursiva :P

Otro detalle a mencionar es que la función inicio(lista) que utilizamos ahí es lo contrario a cola(lista) es decir que retorna la sublista desde el principio hasta el anteúltimo elemento. Eso es lo que justamente necesitamos para seguir ordenando recursivamente.

Análisis del Algoritmo

Veamos el tiempo requerido para cada versión:

Versión original (segunda que vimos) con N iteraciones, con N Pasos:
- O(n²)
- Ej: bubbleSort(5) => 25
Versión con la optimización de recortar pasos:
O( (n² - n) / 2)
- Ej: bubbleSort(5) => 25 - 5 / 2 => 10
- Esto se lee porque:
  - n2 daría todas las iteraciones con todos los pasos.
  - como no hacemos la última iteración se resta un n (5 pasos)
  - Pero en promedio cada iteración tendrá la mitad de pasos, porque la primera tiene N (5 pasos), mientras que la última tiene solo 1. Entonces es lo mismo que decir, la mitad.