Алгоритмы на Python

Быстрая сортировка (quick sort) в Python

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

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Быстрая сортировка - одна из самых распространённых идей сортировки, потому что в среднем она быстра и её легко выразить. Она показывает ещё один способ делить задачу: не пополам, а вокруг выбранного значения.

Пример из жизни

Быстрая сортировка похожа на сортировку книг по высоте вокруг одной выбранной книги. Все книги пониже кладутся в левую стопку, повыше - в правую, а книги той же высоты - в середину. Потом каждая боковая стопка сортируется так же, и стопки собираются вместе.

От стопок книг к коду
pivot = values[len(values) // 2]📕 Выбрать книгу для сравнения
lower = [... if value < pivot]⬅️ Книги пониже налево
higher = [... if value > pivot]➡️ Книги повыше направо
quick_sort(lower) + equal + quick_sort(higher)📚 Отсортировать каждую сторону, потом соединить стопки
Разделите вокруг опорного элемента, потом отсортируйте каждую сторону так же.
Одним предложением

Быстрая сортировка выбирает опорный элемент, делит остальные элементы на меньшие и большие него, рекурсивно сортирует каждую часть и соединяет их; в среднем это время O(n log n).

Главное

  1. if len(values) <= 1: - базовый случай: такой список уже отсортирован.
  2. pivot = values[len(values) // 2] берёт среднее значение как опорное.
  3. lower, equal и higher делят значения вокруг опорного; equal держит повторы вместе.
  4. quick_sort(lower) + equal + quick_sort(higher) сортирует две стороны и соединяет три списка.

Когда это нужно?

  • Знакомство с разбиением и рекурсией.
  • Универсальная сортировка на месте в языках и библиотеках (с аккуратным выбором опорного).
  • Задачи выбора, например поиск медианы (quickselect использует то же разбиение).

Когда это не нужно

  • Обычный код на Python: sorted() быстрее и устойчив.
  • Когда важен гарантированный худший случай: при плохих опорных быстрая сортировка становится O(n²), а сортировка слиянием - никогда.

Визуализация: Быстрая сортировка (quick sort) в Python

O(n log n)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Пример кода

Запустить код →
main.py
def quick_sort(values):
    if len(values) <= 1:
        return values
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

print(quick_sort([10, 7, 8, 9, 1, 5]))
Получить кнопку запуска для этого примера

Результат выполнения

[1, 5, 7, 8, 9, 10]

Разбор кода

Эта легко читаемая версия выбирает опорным средний элемент и с помощью генераторов списков создаёт три списка: lower, equal и higher. Результат складывается из quick_sort(lower), equal и quick_sort(higher). Средняя сложность O(n log n), но при неудачном выборе опорного элемента алгоритм может замедлиться до O(n²).

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Потеря значений, равных опорному

Если оставить только < и >, повторы опорного исчезнут.

Ошибка
return quick_sort(lower) + [pivot] + quick_sort(higher)
Исправление
return quick_sort(lower) + equal + quick_sort(higher)

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

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

Все задачи