Как работает алгоритм быстрой сортировки?

Алгоритм быстрой сортировки (QuickSort) — это рекурсивный алгоритм, который работает по принципу "разделяй и властвуй".

1. Выбор опорного элемента (pivot): Выбирается один элемент из массива. Способов выбора несколько: первый элемент, последний, медиана из трех, случайный.
2. Разбиение (partition): Элементы массива переставляются так, чтобы все элементы меньше опорного оказались перед ним, а все элементы больше — после него. Элементы, равные опорному, могут быть в любой из двух частей. После этого разбиения опорный элемент занимает свое окончательное отсортированное место.
3. Рекурсивная сортировка подмассивов: Алгоритм рекурсивно применяется к подмассиву элементов меньше опорного и к подмассиву элементов больше опорного.

Базовым случаем рекурсии является массив из одного или нуля элементов, который уже считается отсортированным.

Псевдокод:

plaintext

Функция разбиения (пример):

c

Сложность:

• Средняя: Пространственная O(log n) (из-за рекурсивных вызовов), временная O(n log n).
• Худшая: Пространственная O(n) (при несбалансированном разбиении), временная O(n^2) (когда каждый раз выбирается минимальный или максимальный элемент в качестве опорного). Этого можно избежать с помощью хорошего выбора опорного элемента.