Step-by-step: bubble sort (part 126b)

Медленный разбор помогает понять код, а не просто скопировать его.

Задача

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

Решение

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) по памяти (без учёта копии).

Разбор по шагам

1. Шаг 1. Входные данные. Проверяем, что приходит в функцию, и какие значения считаются корректными.
2. Шаг 2. Основной цикл. Именно здесь происходит вся работа; следим за изменениями переменных на каждой итерации.
3. Шаг 3. Результат. Убеждаемся, что возвращаемое значение соответствует условию задачи, включая крайние случаи.

Читая чужой код, повторите тот же мысленный разбор по шагам — это самый быстрый способ научиться.

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

способ · значения · шагам · разбор · Читая · включая · условию · данные · python · возвращаемое · помогает · Результат · простейшим · самый · изменениями · список · каждой · повторите · самое · Проверяем · происходит · Именно · элементов