Clasificación de burbujas en Python

C

Introducción

Para la mayoría de las personas, Bubble Sort es probablemente el primer algoritmo de clasificación del que han oído hablar en su curso de informática.

Es muy intuitivo y fácil de “traducir” en código, lo cual es importante para los nuevos desarrolladores de software para que puedan convertir las ideas en una forma que se pueda ejecutar en una computadora. Sin embargo, Bubble Sort es uno de los algoritmos de clasificación de peor rendimiento en todos los casos, excepto en la verificación de si la matriz ya está ordenada, donde a menudo supera a los algoritmos de clasificación más eficientes como Quick Sort.

Ordenamiento de burbuja

La idea detrás de Bubble Sort es muy simple, miramos pares de elementos adyacentes en una matriz, un par a la vez, e intercambiamos sus posiciones si el primer elemento es más grande que el segundo, o simplemente seguimos adelante si no lo es. Veamos un ejemplo y ordenemos la matriz 8, 5, 3, 1, 4, 7, 9:

Si te enfocas en el primer número, el número 8, puede ver que “burbujea” la matriz en el lugar correcto. Luego, este proceso se repite para el número 5 y así.

Implementación

Con la visualización fuera del camino, sigamos adelante e implementemos el algoritmo. Nuevamente, es extremadamente simple:

def bubble_sort(our_list):
    # We go through the list as many times as there are elements
    for i in range(len(our_list)):
        # We want the last pair of adjacent elements to be (n-2, n-1)
        for j in range(len(our_list) - 1):
            if our_list[j] > our_list[j+1]:
                # Swap
                our_list[j], our_list[j+1] = our_list[j+1], our_list[j]

Ahora, completemos una lista y llamemos al algoritmo en ella:

our_list = [19, 13, 6, 2, 18, 8]
bubble_sort(our_list)
print(our_list)

Salida:

[2, 6, 8, 13, 18, 19]

Mejoramiento

La implementación simple hizo su trabajo, pero hay dos optimizaciones que podemos hacer aquí.

Cuando no se realizan intercambios, eso significa que la lista está ordenada. Sin embargo, con el algoritmo implementado anteriormente, seguirá evaluando el resto de la lista aunque realmente no sea necesario. Para arreglar esto, mantendremos un boolean marcar y comprobar si se realizaron intercambios en la iteración anterior.

Si no se realizan intercambios, el algoritmo debería detenerse:

def bubble_sort(our_list):
    # We want to stop passing through the list
    # as soon as we pass through without swapping any elements
    has_swapped = True

    while(has_swapped):
        has_swapped = False
        for i in range(len(our_list) - 1):
            if our_list[i] > our_list[i+1]:
                # Swap
                our_list[i], our_list[i+1] = our_list[i+1], our_list[i]
                has_swapped = True

La otra optimización que podemos hacer aprovecha el hecho de que Bubble Sort funciona de tal manera que los elementos más grandes en una iteración particular terminan al final de la matriz.

La primera vez que pasamos por la lista, se garantiza que la posición n será el elemento más grande, la segunda vez que pasamos por la posición n-1, se garantiza que será el segundo elemento más grande y así sucesivamente.

Esto significa que con cada iteración consecutiva podemos mirar un elemento menos que antes. Más precisamente, en la k-ésima iteración, solo es necesario mirar los primeros n – k + 1 elementos:

def bubble_sort(our_list):
    has_swapped = True

    num_of_iterations = 0

    while(has_swapped):
        has_swapped = False
        for i in range(len(our_list) - num_of_iterations - 1):
            if our_list[i] > our_list[i+1]:
                # Swap
                our_list[i], our_list[i+1] = our_list[i+1], our_list[i]
                has_swapped = True
        num_of_iterations += 1

Comparación de tiempo

Avancemos y comparemos el tiempo que tarda cada uno de estos fragmentos de código en ordenar la misma lista mil veces usando el timeit módulo:

Unoptimized Bubble Sort took: 0.0106407
Bubble Sort with a boolean flag took: 0.0078251
Bubble Sort with a boolean flag and shortened list took: 0.0075207

No hay mucha diferencia entre los dos últimos enfoques debido al hecho de que la lista es extremadamente corta, pero en listas más grandes, la segunda optimización puede marcar una gran diferencia.

Conclusión

En el enfoque más ineficiente, Bubble Sort pasa por n-1 iteraciones, observando n-1 pares de elementos adyacentes. Esto le da la complejidad temporal de O (n2), tanto en el mejor de los casos como en el promedio. O (n2) se considera bastante horrible para un algoritmo de clasificación.

Tiene una complejidad espacial O (1), pero eso no es suficiente para compensar sus deficiencias en otros campos.

Sin embargo, sigue siendo una gran parte de la comunidad y la historia del desarrollo de software, y los libros de texto casi nunca dejan de mencionarlo cuando se habla de algoritmos básicos de clasificación.

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con tus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad