Ordenar con bubble sort

A continuación vemos como ordenar una lista de menor a mayor. Como siempre decimos, en la práctica es mejor que uses una función ya hecha. Sin embargo es útil saber lo básico sobre los algoritmos de ordenación. Esto te ayudará a saber cual elegir.

Simplificando las cosas, los algoritmos de ordenación se reducen a dos cosas:

⏱️ Velocidad: El tiempo que tardan en ejecutarse.
🧠 Memoria: La memoria que consumen.

Algo también muy importante es lo que se conoce como Big O Notation. Esto mide como se comportan los algoritmos (en términos de velocidad y memoria) a medida que se usan con entradas mas grandes. Algunos ejemplo para entenderlo:

🥇 O(1) El tiempo en ejecutarse es el mismo sin importar el tamaño de la entrada.
🥈 O(log n) El tiempo crece lentamente, con el logaritmo.
🥉 O(n) El tiempo crece proporcionalmente.
🥲 O(n^2) El tiempo crece de manera cuadrática.

Veamos algunos ejemplos para entender esto. Imagina un algoritmo que:

⌛ Tarda 1 segundo en ejecutarse.
➡️ Para una entrada de tamaño 10.

Imagina ahora que usamos una entrada del doble de tamaño. La entrada pasa de 10 → 20. Dependiendo del O() de nuestro algoritmo, el tiempo se verá incrementado de forma diferente:

Si es O(1) pasamos de 1 segundo a 1 segundo. El mismo tiempo.
Si es O(log n) pasamos de 1 segundo a 1.3 segundos. No está mal.
Si es O(n) pasamos de 1 segundo a 2 segundos. Sigue sin estar mal.
Si es O(n^2) pasamos de 1 segundo a 4 segundos. El tiempo empieza a incrementar notablemente.

Por esto es tan importante saber de que tipo es nuestro algoritmo. Dicho esto, vamos a implementar un algoritmo de ordenación conocido como bubble sort. Este es muy sencillo de implementar y tiene un O(n^2) en el peor de los casos. No es el mejor, pero si el mas sencillo y muy didáctico. Su funcionamiento es sencillo.:

⚖️ Toma cada elemento y lo compara con el resto.
➡️ Si es mayor se desplaza al siguiente.
🔄 En cada nueva iteración, iteramos un elemento menos, ya que los del final van quedando ordenados.
📊 Tras realizar todas las iteraciones, tenemos l ordenado.

def bubble_sort(l):
    n = len(l)
    for i in range(n):
        for j in range(0, n-i-1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
                # Pista: Puede optimizarse
    return l

Lo podemos usar de la siguiente forma.

l = [64, 34, 25, 12, 22, 11, 90]
l_ordenado = bubble_sort(l)
print("Ordenado:", l_ordenado)
# Ordenado: [11, 12, 22, 25, 34, 64, 90]

✏️ Ejercicios:

En la función bubble_sort hemos dejado una pista. Este algoritmo puede optimizarse de manera muy sencilla para evitar hacer trabajo redundante. Lo puedes hacer en dos líneas de código. Optimízalo y explícalo.
Cambia la función bubble_sort para que ordene l de mayor a menor.