Bubble sort in Python

Bubble sort walks through the list and swaps any two neighbours that are in the wrong order. After each pass, the largest remaining value has moved to the end, like a bubble rising. It repeats until no swaps are needed.

The program

def bubble_sort(items):
    items = items.copy()               # leave the caller's list unchanged
    n = len(items)
    for end in range(n - 1, 0, -1):
        swapped = False
        for j in range(end):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break                      # no swaps: the list is sorted
    return items

numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers))
print(numbers)
print(bubble_sort([]))
print(bubble_sort([5, -2, 5, 0]))

[11, 12, 22, 25, 34, 64, 90]
[64, 34, 25, 12, 22, 11, 90]
[]
[-2, 0, 5, 5]

How it works

• end is the last position the inner loop needs to look at. Each pass puts one more large value in its final place at the end, so end gets 1 smaller every pass.
• items[j], items[j + 1] = items[j + 1], items[j] swaps two neighbours in one line.
• swapped records whether the pass changed anything. If a whole pass makes no swaps, the list is already sorted and the loop stops early. On an already sorted list, that means only one pass.
• items.copy() makes the function return a new sorted list, as sorted() does, instead of changing the list you passed in.

Watching the passes

Printing the list after each pass shows the large values moving to the end:

items = [5, 1, 4, 2, 8]
for end in range(len(items) - 1, 0, -1):
    for j in range(end):
        if items[j] > items[j + 1]:
            items[j], items[j + 1] = items[j + 1], items[j]
    print(items)

[1, 4, 2, 5, 8]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]

Bubble sort is good for learning how sorting works, but it is slow on long lists: the number of comparisons grows with the square of the list length. In real code, use sorted(items) or items.sort().