Сортировка пузырьком

Сортировка пузырьком сравнивает соседние элементы и меняет их местами, если они стоят неправильно. После прохода самый большой элемент «всплывает» в конец. Это самая простая сортировка и хороший первый пример инвариантов и анализа O(n²). Свойства, о которых идёт речь ниже, описаны в уроке свойства сортировок.

Алгоритм

На проходе i сравниваем пары a[j], a[j + 1] для j до n - 1 - i, потому что последние i элементов уже на местах. Инвариант: после i проходов последние i элементов — i наибольших, в отсортированном порядке.

a = [5, 1, 4, 2, 8]
n = len(a)
for i in range(n - 1):
    swapped = False
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swapped = True
    print("pass", i + 1, a)
    if not swapped:
        break

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

Реализация с ранним выходом