Clasificación de burbujas en Python

Aunque terriblemente ineficiente, Bubble Sort sigue siendo una gran parte de la historia y la comunidad de desarrollo de software. En este artículo, nos sumergiremos en algunos enfoques de las listas de 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 que escucharon en su curso de Ciencias de la Computación.

Es muy intuitivo y fácil de "traducir" a código, lo cual es importante para los nuevos desarrolladores de software, ya que pueden convertir ideas en una forma que se puede ejecutar en una computadora. Sin embargo, Bubble Sort es uno de los algoritmos de ordenación con peor rendimiento en todos los casos, excepto para verificar si la matriz ya está ordenada, donde a menudo supera a los algoritmos de ordenación más eficientes como Ordenación rápida.

Clasificación por burbujas {#clasificación por burbujas}

La idea detrás de Bubble Sort es muy simple, observamos 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 avanzamos si no lo es. . Veamos un ejemplo y ordenemos la matriz 8, 5, 3, 1, 4, 7, 9:

bubble sort

Si se enfoca en el primer número, el número 8, puede verlo "burbujeando" en la matriz en el lugar correcto. Luego, este proceso se repite para el número ‘5’ y así sucesivamente.

Implementación

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

1
2
3
4
5
6
7
8
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:

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

Producción:

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

Optimización

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 previamente, seguirá evaluando el resto de la lista aunque realmente no sea necesario. Para solucionar esto, mantendremos un indicador booleano y verificaremos si se realizaron intercambios en la iteración anterior.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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 pasemos 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 iteración k-ésima, solo es necesario mirar los primeros elementos n - k + 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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 {#comparación de tiempo}

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

1
Unoptimized Bubble Sort took: 0.0106407
1
Bubble Sort with a boolean flag took: 0.0078251
1
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(n^2^), tanto en el mejor de los casos como en el caso promedio. O(n^2^) se considera bastante horrible para un algoritmo de clasificación.

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

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

Licensed under CC BY-NC-SA 4.0