Ordenamiento de Burbuja - Algoritmos

Introducción:

Supongamos que tenemos la siguiente lista:

A = {55, 86, 32, 12, 82, 43}

Aquí tenemos una simple lista conformada por 6 datos, supongamos que necesitas ordenar esta lista, ¿Como lo harías?, relativamente es fácil, podrías usar la función sort, que se encarga de ordenar listas, pero en ocasiones, como programadores, debemos resolver estos tipos de problemas de una forma más profesional, ¿Como?, creando nuestros propios procedimiento, sí, me refiero a los maravillosos Algoritmos, en este caso, Algoritmos de Ordenamiento.

Hoy te mostrare el funcionamiento del Ordenamiento de Burbuja, un sencillo algoritmo de ordenamiento.

¿Que es el Ordenamiento de Burbuja?

-Como e mencionado anteriormente, el ordenamiento de burbuja es un algoritmo de ordenamiento que nos permite colocar los elementos de una lista o vector en una secuencia dada, ya sea de mayor a menor, o de menor a mayor.

Este algoritmo funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado.

A continuación te mostrare una representación del procedimiento del un algoritmo burbuja:


Gracias a Wikipedia por proporcionarme esta representación, con la cual podemos entender mejor el algoritmo.

Como podemos apreciar en el GIF, el algoritmo hace distintas comparaciones, si se compara un numero menor con uno mayor, cambian de posición, y así sucesivamente.

Podemos definirlo mejor de la siguiente manera:

"Este algoritmo realiza el ordenamiento o reordenamiento de una lista a de n valores, en este caso de n términos numerados del 0 al n-1; consta de dos bucles anidados, uno con el índice i, que da un tamaño menor al recorrido de la burbuja en sentido inverso de 2 a n, y un segundo bucle con el índice j, con un recorrido desde 0 hasta n-i, para cada iteración del primer bucle, que indica el lugar de la burbuja."

La burbuja son dos términos de la lista seguidos, j y j+1, que se comparan: si el primero es mayor que el segundo sus valores se intercambian.

Para entender mejor al algoritmo, echemos un vistazo a su pseudocódigo:

Estas imágenes, proporcionadas por wikipedia, nos muestra uno de los procedimientos del ordenamiento de burbuja, digo uno, ya que existen varios, pero con este podemos darnos una idea del algoritmo, y de que manera podríamos implementarlo en un lenguaje de programación.

Bueno, si no les diera un ejemplo de este algoritmo, yo serie un total idiota.

A continuación les mostrare la implementación del algoritmo en Python:

# Algoritmo Ordenamiento de Burbuja. Implementación en Python

A = [55, 86, 32, 12, 82, 43]

num = len(A)
i = 0
while i < num:
      j = i
      while j < num:
              if A[i] > A[j]:
                      aux = A[i]
                      A[i] = A[j]
                      A[j] = aux

              j = j + 1
      i = i + 1

print("Lista ordenada: ")
print(A)

Lista ordenada: 
[12, 32, 43, 55, 82, 86]

En la organización Código Comentado puedes encontrar el código y las implementaciones en los otros lenguajes:


  

 

Como podemos ver, es un algoritmo corto y muy sencillo de entender, podemos ver la comparación entre el indice i y j de la lista A, si el indice i es mayor que el indice j, entonces intercambian de posición.

La salida del programa debería quedar así:

Lista ordenada:

[12, 32, 43, 55, 82, 86]

A continuación te mostrare un Ejemplo Paso a Paso del algoritmo de burbuja, nuevamente proporcionado por Wikipedia (gracias wikipedia, por ser tan considerada con nosotros).

Ejemplo Paso a Paso:

Tomemos como ejemplo los números: "9 6 5 8 2 1", que serán ordenados de menor a mayor valor usando el método burbuja. Los elementos siguientes resaltados están siendo comparados.

Primera vuelta: ( 9 6 5 8 2 1 )  ( 6 9 5 8 2 1 ), el algoritmo compara los primeros dos elementos y los cambia porque 9 > 6 ( 6 9 5 8 2 1 )  ( 6 5 9 8 2 1 ) ( 6 5 9 8 2 1 )  ( 6 5 89 2 1 ) ( 6 5 8 9 2 1 )  ( 6 5 8 2 9 1 ) ( 6 5 8 2 9 1 )  ( 6 5 8 2 1 9 )

Segunda vuelta: ( 6 5 8 2 1 9 )  ( 5 6 8 2 1 9 ) ( 5 6 8 2 1 9 )  ( 5 6 8 2 1 9 ), como estos elementos ya están en orden, el algoritmo no hace cambios. ( 5 6 8 2 1 9 )  ( 5 6 2 81 9 ) ( 5 6 2 8 1 9 )  ( 5 6 2 1 8 9 ) ( 5 6 2 1 8 9 )  ( 5 6 2 1 8 9 )

Tercera vuelta: ( 5 6 2 1 8 9 )  ( 5 6 2 1 8 9 ) ( 5 6 2 1 8 9 )  ( 5 2 6 1 8 9 ) ( 5 2 6 1 8 9 )  ( 5 2 1 6 8 9 ) ( 5 2 1 6 8 9 )  ( 5 2 1 6 8 9 ) ( 5 2 1 6 8 9 )  ( 5 2 1 6 8 9 )

Cuarta vuelta: ( 5 2 1 6 8 9 )  ( 2 5 1 6 8 9 ) ( 2 5 1 6 8 9 )  ( 2 1 5 6 8 9 ) ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 ) ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 ) ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 )

Quinta vuelta: ( 2 1 5 6 8 9 )  ( 1 2 5 6 8 9 ) ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 ) ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 ) ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 ) ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )

Es muy interesante la forma en la que trabaja el algoritmo ¿Cierto?, puedes comprobarlo tu mismo ejecutando el código que te e facilitado.

Bueno, hemos llegado al final, espero que este articulo te fuera de ayuda, ya sea para resolver algún problema especifico o para ampliar tus conocimientos.

Buen material sobre este tema: Algoritmos de Ordenamiento PDF Español.

Recuerda que puedes seguirnos en nuestra pagina de Facebook para estar enterado nuestra actividad: https://www.facebook.com/codigocomentado/.