Bubble Sort

Bubble sort is a sorting algorithm that compares items next to each other in a list. If they are in the wrong order for the sort you want, it swaps them.

How a pass works

A pass moves along the list from left to right. It compares each neighbouring pair in turn: the first and second items, then the second and third, and so on. When a pair is in the wrong order, the two items are swapped. In an ascending sort, each swap pushes a larger item one place to the right, so one item travels step by step towards its final position.

After one complete pass of an ascending sort, the largest item is in its final position at the end of the list. The next pass can ignore that item and work only on the remaining unsorted section. The section gets smaller after every pass, so later passes make fewer comparisons.

Worked example

Here is an ascending bubble sort of the list 5, 1, 4, 2. Each row after the start is one comparison. A swap happens only when the pair is out of order.

Pass 1 puts 5 at the end. Pass 2 puts 4 in place. Pass 3 makes no swaps, which tells the algorithm the list is in order, so it stops.

Memory and method

Bubble sort is an in-situ (in-place) algorithm. It rearranges the original list and needs only a small amount of temporary storage to hold an item during a swap. It is not a divide-and-conquer algorithm: it does not split the list into smaller sub-lists. Instead, it repeats passes over the list, comparing adjacent items until no swaps are needed.

This program bubble sorts a list of scores into ascending order.

scores = [42, 17, 93, 8, 55]
n = len(scores)
swapped = True
pass_number = 0
while swapped and pass_number < n - 1:
    swapped = False
    for i in range(n - 1 - pass_number):
        if scores[i] > scores[i + 1]:
            temp = scores[i]
            del scores[i]
            scores.insert(i + 1, temp)
            swapped = True
    pass_number = pass_number + 1
print(scores)

Output:

[8, 17, 42, 55, 93]