Clasificaci贸n de burbujas en Python

    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.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *