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

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

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

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

Псевдокод:

plaintext

**Ф