Быстрая сортировка (сортировка Хора, Quick Sort)

Quick Sort (быстрая сортировка) — это один из самых эффективных алгоритмов сортировки, который использует метод "разделяй и властвуй". Он был разработан британским ученым Тони Хоаром в 1960 году. Quick Sort работает по принципу разделения массива на подмассивы и последующей сортировки этих подмассивов.

▎Основные шаги алгоритма Quick Sort:

1. Выбор опорного элемента (pivot):

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

2. Разделение массива:

• Массив разделяется на две части: элементы, меньшие опорного, и элементы, большие или равные опорному. Эти операции выполняются так, чтобы все элементы, меньшие опорного, оказались слева от него, а все элементы, большие или равные — справа.

3. Рекурсивная сортировка:

• Рекурсивно применяем Quick Sort к двум подмассивам (левому и правому) до тех пор, пока не останется подмассивы размером 1 или 0, которые уже считаются отсортированными.

▎Временная сложность:

• Средняя и лучшая временная сложность: O(n*log(n)), где n — количество элементов в массиве.

• Худшая временная сложность: O(n²), возникает при выборе неудачного опорного элемента (например, если массив уже отсортирован и мы всегда выбираем последний элемент).

▎Пространственная сложность:

• O(log(n)) для хранения рекурсивных вызовов.

▎Устойчивость:

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

Реализация алгоритма на C++:

Реализация алгоритма на Python: