all Python 3Algorithms & data structuresterm

Bubble sort

sorting

O(n²). It compares neighboring items and swaps them. Easy to follow, but slow. It can be optimized with a swap flag.

Syntax

def bubble_sort(arr):

Nobody writes bubble sort in real code: sorted() and list.sort() run Timsort in C at O(n log n), and past a few thousand items the gap is embarrassing — bubble sort survives only as a teaching exercise. Two mistakes repeat endlessly: dropping the -i-1 in the inner loop, which either wastes passes over the already-sorted tail or walks j+1 off the end, and missing that the swap happens in place, so the caller's list changes even when the function returns nothing.

Examples

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
print(bubble_sort([64,34,25,12,22,11,90]))  # → [11,12,22,25,34,64,90]
# С флагом (оптимизация)
def bubble_opt(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break  # уже отсортирован
    return arr
print(bubble_opt([1,2,3,4,5]))  # → [1,2,3,4,5] (1 проход)
# Трассировка
def bubble_trace(arr):
    arr = arr[:]
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
        print(f'pass {i+1}: {arr}')
    return arr
bubble_trace([5,3,1,4,2])
# → pass 1: [3,1,4,2,5] / pass 2: [1,3,2,4,5] ...
# Число обменов
def bubble_count(arr):
    arr = arr[:]
    n = len(arr); swaps = 0
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swaps += 1
    return arr, swaps
print(bubble_count([3,2,1]))  # → ([1,2,3], 3)
# Worst case: обратно отсортированный
import time
arr = list(range(1000, 0, -1))
t = time.time()
bubble_sort(arr[:])
print(f'Bubble sort 1000 elements: {time.time()-t:.3f}s')

See also

Open in the full glossarydocs.python.orgReport an inaccuracy