Home / Python / Example programs / Lists

Python program: Bubble sort

Sort a list by repeatedly swapping neighbours that are in the wrong order.

The code

def bubble_sort(items):
    items = items.copy()
    n = len(items)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:      # already sorted: stop early
            break
    return items

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

Output

[11, 12, 22, 25, 34, 64, 90]

How it works

After each pass the largest remaining item has "bubbled" to the end. It is slow for big lists (Python's own sorted is far faster), but it is the classic way to learn how sorting works.

Python features used

Learn the ideas behind it in the free lesson Loops.