Bubble Sort and Selection Sort in Python, Step by Step

Sorting a list is one of the oldest tasks in programming: putting grades in order, listing names alphabetically, sorting the readings of a sensor to find the median. Python already has sorted() and sort() ready-made, and that is what you use day to day, as the next article shows. So why learn to sort by hand? Because writing a sorting algorithm trains, on a small problem, everything that programming requires: nested loops, indexes, swapping values, counters, edge cases and tests. And because understanding what happens inside sorted() helps you see why sorting takes work.

This article presents the two simplest algorithms. Bubble sort compares neighbors and swaps the ones that are out of order, over and over. Selection sort looks for the smallest element and puts it in the first position, then looks for the smallest among the ones left and puts it in the second, and so on. Both are far from the fastest, but they are easy to see, and that is exactly what makes them good for learning. All the examples ran in the simulator, and the results quoted are the ones it produces.

Swapping two values

Both algorithms are made of a single operation, repeated: swapping two elements. In Python, the swap is written in one line, with multiple assignment:

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("end")

The output is [30, 20, 10], then 2 1 and finally end. The right side, lista[2], lista[0], is calculated entirely before any assignment, and only then are the values stored in the positions on the left. It is the same tuple that the article on tuples and unpacking presented. In other languages, the swap needs an auxiliary variable, and here it is not necessary. Further on we will see what happens when you try to swap with two separate assignments, because it is an error that almost everyone makes once.

Bubble sort: swapping neighbors

The idea of bubble sort is to go through the list comparing each element with its right-hand neighbor. If they are out of order, swap. At the end of a complete pass, the largest value has reached the end of the list, like a bubble rising. The pass is repeated, now ignoring the last position, which is already right, and then the last two, until the whole list is in order.

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("pass", i + 1, lista, "swapped" if trocou else "no swaps")
        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("end")

The output starts with [1, 2, 4, 5, 8] twice, and then [1, 3, 3] [] [7] [1, 2, 3]. Next come the passes of the first list: pass 1 [1, 4, 2, 5, 8] swapped, pass 2 [1, 2, 4, 5, 8] swapped and pass 3 [1, 2, 4, 5, 8] no swaps. The second list, which was already in order, gives only pass 1 [1, 2, 3, 4, 5] no swaps. Then come the three pairs of counts, (9, 4), (4, 0) and (10, 10), and finally end. (In the names, trocou = swapped, comparacoes = comparisons and trocas = swaps.)

It is worth reading the bubble function slowly, because the two loop limits are the delicate point:

• The outer loop, for i in range(n - 1), counts the passes. A list of n elements needs at most n - 1 passes, because on each pass one element gets its definitive place, and the last one is left alone, already right.
• The inner loop, for j in range(n - 1 - i), goes through the pairs. It compares lista[j] with lista[j + 1], and so j can only go up to n - 2, for the neighbor to exist. The - i reflects that, on pass i, the last i elements are already fixed and no longer need to be looked at.
• The if compares and, if the one on the left is larger, swaps the two. The comparison with > and not with >= avoids swapping equal values for nothing.

The first result shows something that those coming from other languages may find odd: the print(nums) shows the list already ordered. The function changed the list itself, and not a copy, because lists are mutable and the function received the whole list, not a copied value. The return lista is a convenience, to be able to write print(bubble(nums)), but the original list was changed anyway.

The following lines test the edge cases: repeated values, empty list, list of one element and already ordered list. All of them work. In the empty list one, n - 1 is -1, and the range of a negative number generates no turns, so nothing happens.

Stopping when nothing swaps anymore

The bubble_passos version shows the best-known improvement of the algorithm. If a whole pass swaps nothing, the list is already ordered, and continuing would be a waste of time. The variable trocou keeps track of this: it starts False on each pass, becomes True at the first swap, and, if at the end it is still False, the break ends everything. In the list [5, 1, 4, 2, 8], three passes are enough, and the third only confirms. In the already ordered list, one pass settles it.

The bubble_conta function measures the work. For the list [5, 1, 4, 2, 8], there were 9 comparisons and 4 swaps. For the already ordered one, 4 comparisons and no swaps: it is the best case, and the early stop makes it cheap. For the reversed list [5, 4, 3, 2, 1], the worst case, there were 10 comparisons and 10 swaps, that is, every comparison became a swap.

Selection sort: choosing the smallest

Selection sort thinks in another way. Instead of swapping neighbors all the time, it chooses the right element for each position. On the first pass, it looks for the smallest value in the whole list and puts it at position 0. On the second, it looks for the smallest among the ones left, from position 1 on, and puts it at position 1. The left part, already ordered, keeps growing, and the right part, still to be ordered, keeps shrinking.

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("pass", i + 1, "smallest", lista[menor], "at position", 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("end")

The output starts with [11, 12, 22, 25, 64] and [1, 3, 3] [] [7] [1, 2, 3]. The step by step is pass 1 smallest 11 at position 4 followed by [11, 25, 12, 22, 64], then pass 2 smallest 12 at position 2 followed by [11, 12, 25, 22, 64], then pass 3 smallest 22 at position 3 followed by [11, 12, 22, 25, 64], and pass 4 smallest 25 at position 3 with the same list. The counts are (10, 3), (10, 0) and (10, 2), and finally end. (The name menor means smallest.)

The heart of the function is the variable menor, which holds the position of the smallest value seen so far. It starts at i, the first place of the unordered part. The inner loop, for j in range(i + 1, n), looks at all those that come after and updates menor when it finds a smaller value. Keeping the position, and not the value, is what allows the swap at the end. Only after the inner loop finishes is the swap made, and only if menor != i: when the smallest is already in place, as on pass 4 of the example, there is nothing to swap.

This loop is a search for the minimum, the same scan as the challenge Largest in the List, only for the smallest. Selection sort is, therefore, the search from the previous article repeated several times, each one on a smaller part of the list.

Notice the difference in behavior in the counts. Selection makes 10 comparisons in the three lists of 5 elements, no matter what order they are in: it always scans the remaining part, even when the list is already ordered. In return, the swaps are few: 3 for the first list, 0 for the ordered one and 2 for the reversed one. At most one swap per pass, that is, never more than n - 1 in total.

The two side by side

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("end")

The output brings three lines of counts, 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) and 100 bubble inv (4950, 4950) ord (99, 0) | selection inv (4950, 50) ord (4950, 0). Then, twice [3, 5, 5, 12, 28, 37, 50, 64, 77, 91], then True True True, then the original list [37, 5, 91, 12, 5, 64, 28, 3, 77, 50] and end. (In the labels, inv means inverted and ord means ordered; dados means data.)

The numbers show a pattern worth memorizing. In a list of n elements, the number of comparisons of the version without early stop is n * (n - 1) / 2: with 5 elements, 10; with 10, 45; with 100, 4950. Ten times more elements, from 10 to 100, and the comparisons go from 45 to 4950, more than a hundred times more. The work grows with the square of the list size, and that is why these two algorithms serve for small lists and start to weigh on large ones. The article on algorithm complexity, at the end of this part, gives a name to this growth.

The practical differences between the two are these:

• Already ordered list. Bubble with early stop makes only n - 1 comparisons and no swaps. Selection keeps making all the comparisons.
• Reversed list. Bubble swaps on every comparison, 4950 swaps for 100 elements. Selection makes only 50, half the size, because each swap puts an element definitively in place and also takes another one out of the way.
• A swap costs more than a comparison. When swapping is expensive, such as moving large records or writing to a slow memory, selection has the advantage. When the list already comes ordered, or almost, bubble with early stop usually has the advantage.

In the last part of the example, the two versions sort a copy of the list, made with dados[:], and the original stays intact. Both give the same result, equal to that of sorted(dados), which confirms that the code is right. Comparing with sorted is a good test for any sorting algorithm you write.

Variations: descending, texts and records

The same skeleton serves other orders. You just change the comparison, or what is compared:

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("end")

The output is [8, 5, 4, 2, 1], then ['ana', 'bia', 'caio', 'dora'], then ['A', 'B', 'a', 'b'], then four lines Bruno 6.0, Davi 7.0, Ana 8.5, Carla 9.5, then [(1, 'a'), (2, 'b'), (3, 'c')] and end. (The dictionary keys nome and nota mean name and grade, and the names are kept in Portuguese.)

For the descending order, the > becomes <, and the largest value goes to the start. For texts, the same function works without changing a letter, because the > compares texts in alphabetical order, as seen in the article on strings. The result with "b", "B", "a" and "A" is a reminder that the comparison uses the character table: capitals come before lowercase letters.

For records, such as a list of dictionaries, what changes is what is compared: instead of lista[j] < lista[menor], you write lista[j]["nota"] < lista[menor]["nota"], comparing the chosen field. The students come out from lowest to highest grade, and the swap is still that of the whole dictionaries, so that each name goes along with its grade. As for the list of tuples, it is ordered by the first field, and the second only breaks ties, because tuple comparison looks element by element.

On the ESP32: median of readings and ranking

Sensors give noisy readings. The HC-SR04 distance sensor, for example, may return an absurd value from time to time. A common way out is the median filter: you read the sensor a few times, sort the readings and keep the one in the middle, which ignores the extremes.

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 = [("living room", 24.5), ("bedroom", 22.0), ("kitchen", 27.5), ("balcony", 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("end")

The output is 12.6, then [12.4, 12.6, 98.0, 12.5, 12.7], then 29.6, then balcony 21.0, bedroom 22.0, living room 24.5 and kitchen 27.5, and finally end. (The names ordenar, mediana, leituras, copia and distancias mean sort, median, readings, copy and distances.)

The reading 98.0 is a sensor error, and the average of the five readings gives 29.6, very far from reality, because one bad value pulls the calculation. The median gives 12.6, which is the typical value. The mediana function sorts a copy, with leituras[:], and so the list distancias stays in the original order, as the second line shows. The index len(copia) // 2 takes the element in the middle, and works for odd numbers of readings. The article on DHT22, HC-SR04 and PIR sensors shows how to get these readings on the board. Since the median requires sorting very few values, a simple algorithm is more than enough.

The second example is a ranking: sorting rooms by temperature, from the coldest to the warmest. Each item is a tuple (name, temperature), and the comparison looks at the field [1]. The for nome, t in temps unpacks each tuple, another feature from the article on tuples.

Common errors

The first error is letting the inner loop go too far:

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

With j going up to n - 1, the lista[j + 1] looks at a position that does not exist. The correct limit is n - 1, that is, range(n - 1) or, better, range(n - 1 - i).

The second is comparing elements of different types, such as a number and a text:

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'

In the computer's Python, the message is '>' not supported between instances of 'int' and 'str'. This happens when the readings come from input() and nobody converted them with int() or float(). Sorting only works between comparable values.

Silent traps

The worst sorting errors are the ones that give no message. The most classic is the swap done with two assignments:

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("end")

The output is [1, 1, 2, 2, 8], then None [1, 2, 3], then None [1, 2, 3], then [1, 2, 3] [3, 1, 2] and finally end. (troca_errada means wrong swap and sem_return means without return.)

In troca_errada, the first assignment, lista[j] = lista[j + 1], erases the old value of lista[j]. The second copies the value that was just copied, and the original value was lost. The result, [1, 1, 2, 2, 8], has the right size and looks ordered, but the 5 and the 4 vanished, and the 1 and the 2 appear twice. It is the error that multiple assignment avoids: lista[j], lista[j + 1] = lista[j + 1], lista[j] calculates both sides before storing.

The second trap is the function that sorts in place but has no return. It works, the list x ends up ordered, but whoever writes r = bubble_sem_return(x) receives None. The same goes for the sort() method of lists: it sorts in place and returns None, as the third line shows. Whoever writes y = y.sort() loses the list. The sorted(), on the other hand, returns a new list and leaves the original as it was, as the last line shows.

The third trap is the loop limits:

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("end")

The output is [1, 2, 4, 5, 8], then [2, 1, 3, 4, 5] and finally end. (limite_errado means wrong limit and passada_curta means short pass.) In limite_errado, the inner loop always goes to the end, without the - i. This breaks nothing, because comparing positions that are already ordered changes nothing. It only makes extra comparisons. In passada_curta, the outer loop has one pass fewer, n - 2 instead of n - 1, and the reversed list comes out almost ordered, [2, 1, 3, 4, 5], without any warning. Testing only with easy lists does not reveal this defect, and so it is always worth testing with a reversed list.

What tends to show up in class

These are patterns that repeat with people learning sorting. They are not the account of a specific class.

Swapping with two assignments. It is the champion, as shown. The result has repeated values, and the person looks for the defect in the comparison, when the problem is in the swap.

The IndexError of the j + 1. It appears when the inner loop uses range(n). Understanding why the last element has no neighbor on the right settles it for good.

Forgetting to look at the second pass. Many people test a list that gets ordered in a single pass, and conclude the code is right. A reversed list, which requires all the passes, is the test that matters.

Confusing menor with the value. In selection sort, keeping the value of the smallest instead of the position. Without the position, there is no way to swap, and the program either fails or sorts wrong.

Swapping inside the search loop. In selection, making the swap at each new "smallest" found, instead of only at the end. The algorithm becomes a mix of the two and makes too many swaps.

Sorting the original list by accident. The function changes the list it receives. Whoever needed the original order loses the data. The copy with lista[:] before sorting is the remedy.

y = y.sort(). The list becomes None and the program goes on until it fails later, far from the error.

Thinking that sorted() is "cheating". In practice, it is what you use. Writing by hand serves to understand, and not to replace the ready-made function. The next article shows when each one applies.

Exercise: sort and report

Write a program that reads the quantity n of numbers, then the n values, sorts them with bubble sort with early stop, and shows the list before and after, the number of passes made, and the smallest and largest value. The block uses entradas= to provide 5 numbers: 5, 1, 4, 2 and 8.

n = int(input())
lista = []
for i in range(n):
    lista.append(int(input()))
print("before", 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("after", lista)
print("passes", passadas)
print("smallest", lista[0], "largest", lista[-1])
print("end")

The simulator repeats the typed values in the output, one per line, and then come before [5, 1, 4, 2, 8], after [1, 2, 4, 5, 8], passes 3, smallest 1 largest 8 and end.

Notice that, once sorted, the smallest value is always in the first position and the largest in the last, and so lista[0] and lista[-1] are enough. The count of passes only adds up after the inner loop finishes, and the break exits when a pass swaps nothing, which explains the 3 passes: two with swaps and one of confirmation.

To practice, try: sorting from largest to smallest; swapping bubble for selection and comparing the number of swaps; counting the comparisons and showing the total; and sorting a list of texts read from the keyboard, one word at a time.

Frequently asked questions

Why learn bubble sort if sorted() exists? Because the algorithm trains loops, indexes and swapping values, and because understanding the cost of sorting helps decide when and how to sort. For real code, sorted() and sort() are the choice.

Which of the two is better? It depends. Bubble with early stop wins on almost-ordered lists. Selection wins when swapping is expensive, because it makes few swaps. Neither of them suits large lists.

Does bubble sort order the original list? The function we wrote does: it swaps elements in the list itself. To preserve the original, sort a copy, made with lista[:].

Why is the comparison > and not >=? With >=, equal values would be swapped needlessly, and the algorithm would do work for nothing. With >, equal values stay where they are.

Does selection sort always make the same number of comparisons? Yes: n * (n - 1) / 2, whatever the initial order of the list, as the counts showed. What changes is the number of swaps.

How long does it take to sort 100 elements? About 4950 comparisons, which on a computer is instantaneous. The point is how the work grows: with 1000 elements, it would be about 500 thousand. It is the subject of the article on complexity.

Where to go next

The challenges Reversed List, Largest in the List and Average of the List practice the walk through and the choice of elements that both algorithms use. To review the basics, it is worth going through the articles on lists, linear and binary search and tuples, and through the Logic with Python track.

The next article presents insertion sort, the third simple sorting algorithm, and shows when it is worth using sorted() instead of writing your own.