Step-by-step: quicksort

Пройдём задачу шаг за шагом — такой формат удобен для первого знакомства с алгоритмами.

Задача

Реализовать быструю сортировку — один из самых известных алгоритмов «разделяй и властвуй».

Решение

def quicksort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)


print(quicksort([3, 6, 8, 10, 1, 2, 1]))

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

Выбирается опорный элемент, массив делится на три части (меньше, равно, больше), затем части сортируются рекурсивно и склеиваются.

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

[1, 1, 2, 3, 6, 8, 10]

Сложность

O(n log n) в среднем, O(n²) в худшем случае.

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

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

Когда каждый шаг понятен, доработка решения перестаёт быть лотереей.

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

крайние · Когда · равно · [print(quicksort(3 · задачу · переменных · какие · алгоритмов · быструю · условию · первого · опорный · pivot · Основной · Результат · считаются · работы · части · изменениями · [listint · самых · корректными