Solving and testing bubble sort (part fcee)

Решение без тестов быстро ломается, поэтому добавим к задаче простые проверки.

Задача

Отсортировать список чисел по возрастанию простейшим алгоритмом — сортировкой пузырьком.

Решение

def bubble_sort(arr: list[int]) -> list[int]:
    a = arr[:]
    n = len(a)
    for i in range(n):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a


print(bubble_sort([5, 1, 4, 2, 8]))

Как это работает

На каждом проходе самое большое из оставшихся элементов «всплывает» в конец. Внутренний цикл сокращается на i, ведь хвост уже отсортирован.

Пример работы

[1, 2, 4, 5, 8]

Сложность

O(n²) по времени, O(1) по памяти (без учёта копии).

Проверка тестами

Хорошая привычка — проверять решение сразу на нескольких примерах, включая крайние случаи.

assert is_valid(True) is not None  # базовая проверка вызова
assert is_valid(False) is not None  # и второй случай

Такой минимум уже защищает от случайной ошибки при правках кода.

Тесты вида assert удобны для учебных задач: они короткие, наглядные и не требуют фреймворков.

Читайте также:

конец · удобны · len(a · сортировкой · [listint · Тесты · самое · случай · привычка · копии · список · включая · ошибки · решение · Задача · учебных · случайной · каждом · нескольких · отсортирован · Решение · памяти · оставшихся · правках · примерах · быстро · работы · случаи · добавим · требуют