Python: пузырьковая сортировка списка

Принцип: на каждом проходе соседние элементы сравниваются и при необходимости меняются местами. Самый большой «всплывает» в конец, как пузырёк.

def bubble_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            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_sort([5, 2, 8, 1, 9, 3]))  # [1, 2, 3, 5, 8, 9]

Сложность: $O(n^2)$ в худшем и среднем случае, $O(n)$ в лучшем (когда массив уже отсортирован — флаг swapped остаётся False).

Пузырёк прост, но медленный — для больших массивов используют sorted() (Timsort, $O(n \log n)$).