Google+ Seguidores

miércoles, 27 de septiembre de 2017

Ordenamiento de Burbuja - Algoritmos de Ordenamiento en Python

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.

En mi ordenar tengo un algoritmo burbuja escrito en python, el cual les enseñare de inmediato, por cuestiones de tiempo y de flojera, copiare y pegare a continuación el código, ¿listos?, aquí esta. :D
           
   
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)

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.

Si tienes una pregunta, con gusto la responderé. :D

2 comentarios :
Write comentarios
  1. Hola no se podría cambiar la parte:

    while j < num:
    if A[i] > A[j]:
    aux = A[i]
    A[i] = A[j]
    A[j] = aux



    Por la forma "pythonica" :

    while j < num:
    if A[i] > A[j]:
    A[i],A[j] = A[j], A[i]

    ResponderEliminar
    Respuestas
    1. Si podríamos hacerlo, pero de la otra forma es más legible, e impide en que los que empiezan en el lenguaje no se confundan :D

      Eliminar

Tu comentario es importante y nos motiva a seguir escribiendo...

Entradas más recientes

Powered by Blogger .