Bubble Sort

Bubble sort is a sorting algorithm that repeatedly compares neighbouring items in a list and swaps any pair that is in the wrong order. It keeps making passes through the list until a whole pass goes by with no swaps at all.

What happens in one pass

Start at the first item and compare it with the second. If they are the wrong way round, swap them. Then move one place along and compare the second item with the third, and so on to the end of the list, so each pass walks through the list one place at a time.

The biggest item in the unsorted section is swapped rightwards every time it meets something smaller, so after a pass it sits in its final position at the end, and later passes never need to swap it again. A pass that makes no swaps at all means the list is already in order, which is how the algorithm knows to stop.

Worked example

Sorting five sunflower seedling heights, in centimetres, into ascending order: 14, 11, 18, 9, 15.

For descending order you use exactly the same method, but reverse the comparison, so a pair is swapped when the left item is smaller than the right one.

A program can use a flag to remember whether a pass swapped anything, and stop once a pass makes no swaps:

scores = [6, 2, 9, 4]
swapped = True
# keep going while the last pass changed something
while swapped:
    swapped = False
    for position in range(len(scores) - 1):
        if scores[position] > scores[position + 1]:
            held = scores[position]
            scores[position] = scores[position + 1]
            scores[position + 1] = held
            swapped = True
print(scores)

Output:

[2, 4, 6, 9]