Bubble sort y selection sort en Python, paso a paso

Ordenar una lista es una de las tareas más antiguas de la programación: poner notas en orden, listar nombres en orden alfabético, ordenar lecturas de un sensor para encontrar la mediana. Python ya tiene sorted() y sort() listos, y es lo que se usa día a día, como muestra el artículo siguiente. Entonces, ¿por qué aprender a ordenar a mano? Porque escribir un algoritmo de ordenación entrena, en un problema pequeño, todo lo que programar exige: bucles anidados, índices, intercambio de valores, contadores, casos de borde y pruebas. Y porque entender lo que ocurre dentro del sorted() ayuda a percibir por qué ordenar cuesta trabajo.

Este artículo presenta los dos algoritmos más simples. El bubble sort compara vecinos e intercambia los que están fuera de orden, una y otra vez. El selection sort busca el menor elemento y lo coloca en la primera posición, después busca el menor entre los que sobraron y lo coloca en la segunda, y así sucesivamente. Los dos están lejos de ser los más rápidos, pero son fáciles de ver, y justamente eso los hace buenos para aprender. Todos los ejemplos corrieron en el simulador, y los resultados citados son los que él produce.

El intercambio de dos valores

Los dos algoritmos están hechos de una sola operación, repetida: intercambiar dos elementos de lugar. En Python, el intercambio se escribe en una línea, con asignación múltiple:

lista = [10, 20, 30]
lista[0], lista[2] = lista[2], lista[0]
print(lista)
a = 1
b = 2
a, b = b, a
print(a, b)
print("fin")

La salida es [30, 20, 10], después 2 1 y por último fin. El lado derecho, lista[2], lista[0], se calcula entero antes de cualquier asignación, y solo entonces los valores se guardan en las posiciones de la izquierda. Es la misma tupla que presentó el artículo sobre tuplas y desempaquetado. En otros lenguajes, el intercambio pide una variable auxiliar, y aquí no es necesaria. Más adelante veremos qué ocurre cuando se intenta intercambiar con dos asignaciones separadas, porque es un error que casi todo el mundo comete una vez.

Bubble sort: intercambiar vecinos

La idea del bubble sort, u ordenación por burbujas, es recorrer la lista comparando cada elemento con el vecino de la derecha. Si están fuera de orden, los intercambia. Al final de una pasada completa, el mayor valor llegó al final de la lista, como una burbuja que sube. Se repite la pasada, ahora ignorando la última posición, que ya está correcta, y después las dos últimas, hasta que la lista entera quede en orden.

def bubble(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

nums = [5, 1, 4, 2, 8]
print(bubble(nums))
print(nums)
print(bubble([3, 3, 1]), bubble([]), bubble([7]), bubble([1, 2, 3]))

def bubble_passos(lista):
    n = len(lista)
    for i in range(n - 1):
        trocou = False
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                trocou = True
        print("pasada", i + 1, lista, "intercambió" if trocou else "sin intercambios")
        if not trocou:
            break
    return lista
bubble_passos([5, 1, 4, 2, 8])
bubble_passos([1, 2, 3, 4, 5])

def bubble_conta(lista):
    comparacoes = 0
    trocas = 0
    n = len(lista)
    for i in range(n - 1):
        trocou = False
        for j in range(n - 1 - i):
            comparacoes += 1
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                trocas += 1
                trocou = True
        if not trocou:
            break
    return comparacoes, trocas
print(bubble_conta([5, 1, 4, 2, 8]))
print(bubble_conta([1, 2, 3, 4, 5]))
print(bubble_conta([5, 4, 3, 2, 1]))
print("fin")

La salida empieza con [1, 2, 4, 5, 8] dos veces, y después [1, 3, 3] [] [7] [1, 2, 3]. A continuación vienen las pasadas de la primera lista: pasada 1 [1, 4, 2, 5, 8] intercambió, pasada 2 [1, 2, 4, 5, 8] intercambió y pasada 3 [1, 2, 4, 5, 8] sin intercambios. La segunda lista, que ya estaba en orden, da solo pasada 1 [1, 2, 3, 4, 5] sin intercambios. Después vienen los tres pares de conteos, (9, 4), (4, 0) y (10, 10), y por último fin.

Vale leer la función bubble con calma, porque los dos límites de los bucles son el punto delicado:

• El bucle de afuera, for i in range(n - 1), cuenta las pasadas. Una lista de n elementos necesita como máximo n - 1 pasadas, porque en cada pasada un elemento gana su lugar definitivo, y el último queda solo, ya correcto.
• El bucle de adentro, for j in range(n - 1 - i), recorre los pares. Compara lista[j] con lista[j + 1], y por eso j solo puede llegar hasta n - 2, para que el vecino exista. El - i refleja que, en la pasada i, los últimos i elementos ya están fijos y no necesitan mirarse más.
• El if compara y, si el de la izquierda es mayor, intercambia los dos. La comparación con > y no con >= evita intercambiar valores iguales sin motivo.

El primer resultado muestra algo que quien viene de otros lenguajes puede encontrar extraño: el print(nums) muestra la lista ya ordenada. La función modificó la propia lista, y no una copia, porque las listas son mutables y la función recibió la lista entera, no un valor copiado. El return lista es una comodidad, para poder escribir print(bubble(nums)), pero la lista original se cambió de todos modos.

Las líneas siguientes prueban los casos de borde: valores repetidos, lista vacía, lista de un elemento y lista ya ordenada. Todos funcionan. En el de la lista vacía, n - 1 vale -1, y el range de un número negativo no genera ninguna vuelta, así que no ocurre nada.

Parar cuando ya nada se intercambia

La versión bubble_passos muestra la mejora más conocida del algoritmo. Si una pasada entera no intercambia nada, la lista ya está ordenada, y continuar sería una pérdida de tiempo. La variable trocou guarda eso: empieza en False en cada pasada, pasa a True en el primer intercambio, y, si al final sigue en False, el break termina todo. En la lista [5, 1, 4, 2, 8], tres pasadas bastan, y la tercera solo confirma. En la lista ya ordenada, una pasada lo resuelve.

La función bubble_conta mide el trabajo. Para la lista [5, 1, 4, 2, 8], fueron 9 comparaciones y 4 intercambios. Para la ya ordenada, 4 comparaciones y ningún intercambio: es el mejor caso, y la parada anticipada lo vuelve barato. Para la lista invertida [5, 4, 3, 2, 1], el peor caso, fueron 10 comparaciones y 10 intercambios, es decir, cada comparación se volvió un intercambio.

Selection sort: elegir el menor

El selection sort, ordenación por selección, piensa de otra manera. En lugar de intercambiar vecinos todo el tiempo, elige el elemento correcto para cada posición. En la primera pasada, busca el menor valor de toda la lista y lo coloca en la posición 0. En la segunda, busca el menor entre los que sobraron, de la posición 1 en adelante, y lo coloca en la posición 1. La parte de la izquierda, ya ordenada, va creciendo, y la de la derecha, todavía por ordenar, va encogiéndose.

def selection(lista):
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            if lista[j] < lista[menor]:
                menor = j
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
    return lista

print(selection([64, 25, 12, 22, 11]))
print(selection([3, 3, 1]), selection([]), selection([7]), selection([1, 2, 3]))

def selection_passos(lista):
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            if lista[j] < lista[menor]:
                menor = j
        print("pasada", i + 1, "menor", lista[menor], "en la posición", menor)
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
        print("   ", lista)
    return lista
selection_passos([64, 25, 12, 22, 11])

def selection_conta(lista):
    comparacoes = 0
    trocas = 0
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            comparacoes += 1
            if lista[j] < lista[menor]:
                menor = j
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
            trocas += 1
    return comparacoes, trocas
print(selection_conta([64, 25, 12, 22, 11]))
print(selection_conta([1, 2, 3, 4, 5]))
print(selection_conta([5, 4, 3, 2, 1]))
print("fin")

La salida empieza con [11, 12, 22, 25, 64] y [1, 3, 3] [] [7] [1, 2, 3]. El paso a paso es pasada 1 menor 11 en la posición 4 seguido de [11, 25, 12, 22, 64], después pasada 2 menor 12 en la posición 2 seguido de [11, 12, 25, 22, 64], después pasada 3 menor 22 en la posición 3 seguido de [11, 12, 22, 25, 64], y pasada 4 menor 25 en la posición 3 con la lista igual. Los conteos son (10, 3), (10, 0) y (10, 2), y por último fin.

El corazón de la función es la variable menor, que guarda la posición del menor valor visto hasta ahora. Empieza en i, el primer lugar de la parte no ordenada. El bucle de adentro, for j in range(i + 1, n), mira todos los que vienen después y actualiza menor cuando encuentra un valor menor. Guardar la posición, y no el valor, es lo que permite intercambiar al final. Solo después de que termine el bucle de adentro se hace el intercambio, y solo si menor != i: cuando el menor ya está en su lugar, como en la pasada 4 del ejemplo, no hay nada que intercambiar.

Este bucle es una búsqueda del mínimo, el mismo recorrido del desafío Mayor de la lista, solo que por el menor. El selection sort es, por lo tanto, la búsqueda del artículo anterior repetida varias veces, cada una sobre una parte más pequeña de la lista.

Fíjate en la diferencia de comportamiento en los conteos. El selection hace 10 comparaciones en las tres listas de 5 elementos, no importa el orden en que estén: siempre recorre la parte que falta, incluso cuando la lista ya está ordenada. En cambio, los intercambios son pocos: 3 para la primera lista, 0 para la ordenada y 2 para la invertida. Como máximo un intercambio por pasada, es decir, nunca más de n - 1 en total.

Los dos lado a lado

def bubble_conta(lista):
    comparacoes = 0
    trocas = 0
    n = len(lista)
    for i in range(n - 1):
        trocou = False
        for j in range(n - 1 - i):
            comparacoes += 1
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                trocas += 1
                trocou = True
        if not trocou:
            break
    return comparacoes, trocas
def selection_conta(lista):
    comparacoes = 0
    trocas = 0
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            comparacoes += 1
            if lista[j] < lista[menor]:
                menor = j
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
            trocas += 1
    return comparacoes, trocas
for n in [5, 10, 100]:
    inv = list(range(n, 0, -1))
    ord_ = list(range(1, n + 1))
    print(n, "bubble inv", bubble_conta(inv[:]), "ord", bubble_conta(ord_[:]), "| selection inv", selection_conta(inv[:]), "ord", selection_conta(ord_[:]))
dados = [37, 5, 91, 12, 5, 64, 28, 3, 77, 50]
a = dados[:]
b = dados[:]
bubble_conta(a)
selection_conta(b)
print(a)
print(b)
print(a == sorted(dados), b == sorted(dados), a == b)
print(dados)
print("fin")

La salida trae tres líneas de conteo, 5 bubble inv (10, 10) ord (4, 0) | selection inv (10, 2) ord (10, 0), 10 bubble inv (45, 45) ord (9, 0) | selection inv (45, 5) ord (45, 0) y 100 bubble inv (4950, 4950) ord (99, 0) | selection inv (4950, 50) ord (4950, 0). Después, dos veces [3, 5, 5, 12, 28, 37, 50, 64, 77, 91], después True True True, después la lista original [37, 5, 91, 12, 5, 64, 28, 3, 77, 50] y fin.

Los números muestran un patrón que vale la pena memorizar. En una lista de n elementos, el número de comparaciones de la versión sin parada anticipada es n * (n - 1) / 2: con 5 elementos, 10; con 10, 45; con 100, 4950. Diez veces más elementos, de 10 a 100, y las comparaciones pasan de 45 a 4950, más de cien veces más. El trabajo crece con el cuadrado del tamaño de la lista, y por eso estos dos algoritmos sirven para listas pequeñas y empiezan a pesar en las grandes. El artículo sobre la complejidad de algoritmos, al final de esta parte, le da un nombre a ese crecimiento.

Las diferencias prácticas entre los dos son estas:

• Lista ya ordenada. El bubble con parada anticipada hace solo n - 1 comparaciones y ningún intercambio. El selection sigue haciendo todas las comparaciones.
• Lista invertida. El bubble intercambia en cada comparación, 4950 intercambios para 100 elementos. El selection hace solo 50, la mitad del tamaño, porque cada intercambio coloca un elemento definitivamente en su lugar y además saca otro del camino.
• Intercambiar es más caro que comparar. Cuando intercambiar cuesta caro, como mover registros grandes o grabar en una memoria lenta, el selection lleva ventaja. Cuando la lista ya viene ordenada, o casi, el bubble con parada anticipada suele llevar ventaja.

En la última parte del ejemplo, las dos versiones ordenan una copia de la lista, hecha con dados[:], y la original queda intacta. Las dos dan el mismo resultado, igual al del sorted(dados), lo que confirma que el código está correcto. Comparar con el sorted es una buena prueba para cualquier algoritmo de ordenación que escribas.

Variaciones: decreciente, textos y registros

El mismo esqueleto sirve para otros órdenes. Basta cambiar la comparación, o lo que se compara:

def bubble_desc(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] < lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(bubble_desc([5, 1, 4, 2, 8]))
def bubble_texto(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(bubble_texto(["caio", "ana", "dora", "bia"]))
print(bubble_texto(["b", "B", "a", "A"]))
alunos = [{"nome": "Ana", "nota": 8.5}, {"nome": "Bruno", "nota": 6.0}, {"nome": "Carla", "nota": 9.5}, {"nome": "Davi", "nota": 7.0}]
def ordenar_por_nota(lista):
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            if lista[j]["nota"] < lista[menor]["nota"]:
                menor = j
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
    return lista
for a in ordenar_por_nota(alunos):
    print(a["nome"], a["nota"])
pares = [(3, "c"), (1, "a"), (2, "b")]
print(bubble_texto(pares))
print("fin")

La salida es [8, 5, 4, 2, 1], después ['ana', 'bia', 'caio', 'dora'], después ['A', 'B', 'a', 'b'], después cuatro líneas Bruno 6.0, Davi 7.0, Ana 8.5, Carla 9.5, después [(1, 'a'), (2, 'b'), (3, 'c')] y fin.

Para el orden decreciente, el > pasa a <, y el mayor valor va al comienzo. Para textos, la misma función funciona sin cambiar una letra, porque el > compara textos en orden alfabético, como se vio en el artículo sobre strings. El resultado con "b", "B", "a" y "A" recuerda que la comparación usa la tabla de caracteres: las mayúsculas vienen antes que las minúsculas.

Para registros, como una lista de diccionarios, lo que cambia es lo que se compara: en lugar de lista[j] < lista[menor], se escribe lista[j]["nota"] < lista[menor]["nota"], comparando el campo elegido. Los alumnos salen del menor al mayor en nota, y el intercambio sigue siendo el de los diccionarios enteros, de modo que cada nombre acompaña a su nota. En cambio la lista de tuplas se ordena por el primer campo, y el segundo solo desempata, porque la comparación de tuplas mira elemento a elemento.

En la ESP32: mediana de lecturas y ranking

Los sensores dan lecturas ruidosas. El sensor de distancia HC-SR04, por ejemplo, puede devolver de vez en cuando un valor absurdo. Una salida común es el filtro de mediana: se lee el sensor algunas veces, se ordenan las lecturas y se queda con la del medio, que ignora los extremos.

def ordenar(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

def mediana(leituras):
    copia = leituras[:]
    ordenar(copia)
    return copia[len(copia) // 2]

distancias = [12.4, 12.6, 98.0, 12.5, 12.7]
print(mediana(distancias))
print(distancias)
print(round(sum(distancias) / len(distancias), 1))
temps = [("sala", 24.5), ("cuarto", 22.0), ("cocina", 27.5), ("terraza", 21.0)]
n = len(temps)
for i in range(n - 1):
    menor = i
    for j in range(i + 1, n):
        if temps[j][1] < temps[menor][1]:
            menor = j
    temps[i], temps[menor] = temps[menor], temps[i]
for nome, t in temps:
    print(nome, t)
print("fin")

La salida es 12.6, después [12.4, 12.6, 98.0, 12.5, 12.7], después 29.6, después terraza 21.0, cuarto 22.0, sala 24.5 y cocina 27.5, y por último fin.

La lectura 98.0 es un error del sensor, y el promedio de las cinco lecturas da 29.6, muy lejos de la realidad, porque un valor malo arrastra la cuenta. La mediana da 12.6, que es el valor típico. La función mediana ordena una copia, con leituras[:], y por eso la lista distancias sigue en el orden original, como muestra la segunda línea. El índice len(copia) // 2 toma el elemento del medio, y vale para cantidades impares de lecturas. El artículo sobre sensores DHT22, HC-SR04 y PIR muestra cómo obtener esas lecturas en la placa. Como la mediana pide ordenar poquísimos valores, un algoritmo simple es más que suficiente.

El segundo ejemplo es un ranking: ordenar habitaciones por temperatura, de la más fría a la más caliente. Cada elemento es una tupla (nome, temperatura), y la comparación mira el campo [1]. El for nome, t in temps desempaqueta cada tupla, otro recurso del artículo sobre tuplas.

Errores comunes

El primer error es dejar que el bucle de adentro llegue demasiado lejos:

def bubble_erro(lista):
    n = len(lista)
    for i in range(n):
        for j in range(n):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(bubble_erro([3, 1, 2]))

IndexError: list index out of range

Con j llegando hasta n - 1, el lista[j + 1] mira una posición que no existe. El límite correcto es n - 1, es decir, range(n - 1) o, mejor, range(n - 1 - i).

El segundo es comparar elementos de tipos distintos, como un número y un texto:

lista = [3, "1", 2]
for i in range(len(lista) - 1):
    for j in range(len(lista) - 1 - i):
        if lista[j] > lista[j + 1]:
            lista[j], lista[j + 1] = lista[j + 1], lista[j]

TypeError: unsupported types for __gt__: 'int', 'str'

En el Python de computador, el mensaje es '>' not supported between instances of 'int' and 'str'. Esto ocurre cuando las lecturas vienen de input() y nadie las convirtió con int() o float(). La ordenación solo funciona entre valores comparables.

Trampas silenciosas

Los peores errores de ordenación son los que no dan mensaje. El más clásico es el intercambio hecho con dos asignaciones:

def troca_errada(lista):
    for i in range(len(lista) - 1):
        for j in range(len(lista) - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j] = lista[j + 1]
                lista[j + 1] = lista[j]
    return lista
print(troca_errada([5, 1, 4, 2, 8]))
def bubble_sem_return(lista):
    for i in range(len(lista) - 1):
        for j in range(len(lista) - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
x = [3, 1, 2]
r = bubble_sem_return(x)
print(r, x)
y = [3, 1, 2]
print(y.sort(), y)
z = [3, 1, 2]
print(sorted(z), z)
print("fin")

La salida es [1, 1, 2, 2, 8], después None [1, 2, 3], después None [1, 2, 3], después [1, 2, 3] [3, 1, 2] y por último fin.

En la troca_errada, la primera asignación, lista[j] = lista[j + 1], borra el valor antiguo de lista[j]. La segunda copia el valor que acaba de copiarse, y el valor original se perdió. El resultado, [1, 1, 2, 2, 8], tiene el tamaño correcto y parece ordenado, pero el 5 y el 4 desaparecieron, y el 1 y el 2 aparecen dos veces. Es el error que la asignación múltiple evita: lista[j], lista[j + 1] = lista[j + 1], lista[j] calcula los dos lados antes de guardar.

La segunda trampa es la función que ordena en el lugar pero no tiene return. Funciona, la lista x queda ordenada, pero quien escribe r = bubble_sem_return(x) recibe None. Lo mismo vale para el método sort() de las listas: ordena en el lugar y devuelve None, como muestra la tercera línea. Quien escribe y = y.sort() pierde la lista. En cambio, el sorted() devuelve una lista nueva y deja la original como estaba, como muestra la última línea.

La tercera trampa son los límites de los bucles:

def limite_errado(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(limite_errado([5, 1, 4, 2, 8]))
def passada_curta(lista):
    n = len(lista)
    for i in range(n - 2):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(passada_curta([5, 4, 3, 2, 1]))
print("fin")

La salida es [1, 2, 4, 5, 8], después [2, 1, 3, 4, 5] y por último fin. En la limite_errado, el bucle de adentro va siempre hasta el final, sin el - i. Esto no rompe nada, porque comparar posiciones ya ordenadas no altera nada. Solo hace comparaciones de más. En la passada_curta, el bucle de afuera tiene una pasada menos, n - 2 en lugar de n - 1, y la lista invertida sale casi ordenada, [2, 1, 3, 4, 5], sin ningún aviso. Probar solo con listas fáciles no revela este defecto, y por eso conviene siempre probar con una lista invertida.

Lo que suele aparecer en el aula

Son patrones que se repiten en quien aprende ordenación. No son el relato de un grupo específico.

Intercambiar con dos asignaciones. Es el campeón, como se mostró. El resultado tiene valores repetidos, y la persona busca el defecto en la comparación, cuando el problema está en el intercambio.

El IndexError del j + 1. Aparece cuando el bucle de adentro usa range(n). Entender por qué el último elemento no tiene vecino a la derecha lo resuelve de una vez.

Olvidar mirar la segunda pasada. Mucha gente prueba una lista que se ordena en una sola pasada, y concluye que el código está correcto. Una lista invertida, que exige todas las pasadas, es la prueba que importa.

Confundir menor con el valor. En el selection sort, guardar el valor del menor en lugar de la posición. Sin la posición, no hay cómo intercambiar, y el programa o falla o ordena mal.

Intercambiar dentro del bucle de búsqueda. En el selection, hacer el intercambio cada vez que se encuentra un nuevo "menor", en lugar de solo al final. El algoritmo se vuelve una mezcla de los dos y hace demasiados intercambios.

Ordenar la lista original sin querer. La función modifica la lista recibida. Quien necesitaba el orden original pierde los datos. La copia con lista[:] antes de ordenar es el remedio.

y = y.sort(). La lista se vuelve None y el programa sigue hasta fallar más adelante, lejos del error.

Creer que el sorted() es "trampa". En la práctica, es lo que se usa. Escribir a mano sirve para entender, y no para reemplazar la función lista. El próximo artículo muestra cuándo se aplica cada uno.

Ejercicio: ordenar y reportar

Escribe un programa que lea la cantidad n de números, después los n valores, los ordene con bubble sort con parada anticipada, y muestre la lista antes y después, el número de pasadas hechas, el menor y el mayor valor. El bloque usa entradas= para entregar 5 números: 5, 1, 4, 2 y 8.

n = int(input())
lista = []
for i in range(n):
    lista.append(int(input()))
print("antes", lista)
passadas = 0
for i in range(n - 1):
    trocou = False
    for j in range(n - 1 - i):
        if lista[j] > lista[j + 1]:
            lista[j], lista[j + 1] = lista[j + 1], lista[j]
            trocou = True
    passadas += 1
    if not trocou:
        break
print("después", lista)
print("pasadas", passadas)
print("menor", lista[0], "mayor", lista[-1])
print("fin")

El simulador repite en la salida los valores escritos, uno por línea, y después vienen antes [5, 1, 4, 2, 8], después [1, 2, 4, 5, 8], pasadas 3, menor 1 mayor 8 y fin.

Fíjate en que, después de ordenada, el menor valor está siempre en la primera posición y el mayor en la última, y por eso lista[0] y lista[-1] bastan. El conteo de las pasadas solo suma después de terminar el bucle de adentro, y el break sale cuando una pasada no intercambia nada, lo que explica las 3 pasadas: dos con intercambios y una de confirmación.

Para practicar, prueba: ordenar del mayor al menor; cambiar el bubble por el selection y comparar el número de intercambios; contar las comparaciones y mostrar el total; y ordenar una lista de textos leída del teclado, una palabra por vez.

Preguntas frecuentes

¿Por qué aprender bubble sort si existe el sorted()? Porque el algoritmo entrena bucles, índices e intercambio de valores, y porque entender el costo de ordenar ayuda a decidir cuándo y cómo ordenar. Para el código de verdad, el sorted() y el sort() son la elección.

¿Cuál de los dos es mejor? Depende. El bubble con parada anticipada gana en listas casi ordenadas. El selection gana cuando intercambiar es caro, porque hace pocos intercambios. Ninguno de los dos sirve para listas grandes.

¿El bubble sort ordena la lista original? La función que escribimos, sí: intercambia elementos en la propia lista. Para preservar la original, ordena una copia, hecha con lista[:].

¿Por qué la comparación es > y no >=? Con >=, los valores iguales se intercambiarían sin necesidad, y el algoritmo haría trabajo en vano. Con >, los valores iguales se quedan donde están.

¿El selection sort siempre hace el mismo número de comparaciones? Sí: n * (n - 1) / 2, cualquiera que sea el orden inicial de la lista, como mostraron los conteos. Lo que cambia es el número de intercambios.

¿Cuánto tarda ordenar 100 elementos? Cerca de 4950 comparaciones, lo que en el computador es instantáneo. El punto es cómo crece el trabajo: con 1000 elementos, serían cerca de 500 mil. Es el tema del artículo sobre complejidad.

Para continuar

Los desafíos Lista al revés, Mayor de la lista y Media de la lista practican el recorrido y la elección de elementos que usan los dos algoritmos. Para repasar la base, vale la pena pasar por los artículos sobre listas, búsqueda lineal y binaria y tuplas, y por la ruta de lógica.

El próximo artículo presenta el insertion sort, el tercer algoritmo simple de ordenación, y muestra cuándo vale usar el sorted() en lugar de escribir el tuyo.