Пузырьковая сортировка

Пузырьковая сортировка многократно проходит по массиву, меняя местами соседние элементы, если они стоят в неверном порядке. Большие значения «всплывают» к концу. Учебный, но неэффективный алгоритм.

Сложность: время O(n^2) в среднем и худшем случае, O(n) на уже отсортированных данных с флагом ранней остановки. Память: O(1), сортировка устойчивая и на месте.

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a