"Быстрая" сортировка

характеристики	значения
сложность в лучшем	$O (n lo g n)$
сложность в среднем	$O (n lo g n)$
сложность в худшем	$O (n^{2})$ ¹
временная сложность	$O (n lo g n)$ или $O (n^{2})$ ¹
дополнительная память	$O (lo g n)$ или $O (n)$ ²
стабильная ли?	⛔️

¹ : При использовании детерминированного (не случайный выбор) опорного элемента можно легко построить массив, на котором быстрая сортировка будет работать за $O (n^{2})$ .

² : В обычном случае тратится память на сохранения стека рекурсии. Значит обычно будет $lo g n$ но в случае когда сортировка обрабатывает плохой массив.

Алгоритм

Quick sort - рекурсивный алгоритм, основанный на принципе ""разделяй и властвуй". Выбирается какая-то опорная точка (pivot point), относительно которой массив разбивается на подмассивы, после чего эта точка ставится на нужное место в массив.

Алгоритм состоит из трёх шагов:

Выбрать элемент из массива. Назовём его опорным.
Разбиение: перераспределение элементов в массиве таким образом, что элементы, меньшие опорного, помещаются перед ним, а большие или равные - после.
Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.

Существует два базовых разбиения — Ломуто и Хоара. Подробнее можете прочитать на википедии.

Преимущества алгоритма

Эффективен для массивов больших размеров
Занимает не много памяти

Недостатки

Худшая сложность по времени — $O (n^{2})$ . Попробуйте придумать такой тест.
Не лучший выбор для массивов небольших размеров.
Нестабильная сортировка.

Реализация алгоритма.

Опорная точка — середина. Разбиение Хоара.

void qsort(int* a, int b, int e) {
  int l = b, r = e;
  int piv = a[(l + r) / 2];
  while (l <= r) {
    while (a[l] < piv) {
      l++;
    }
    while (a[r] > piv) {
      r--;
    }
    if (l <= r) {
      swap(a[l++], a[r--]);
    }
  }
  if (b < r) {
    qsort(a, b, r);
  }
  if (e > l) {
    qsort(a, l, e);
  }
}

Запуск функции сортировки quickSort(array, 0, size - 1);

Ввод

5
9 74 -354 87 0

Работа алгоритма

Выбрали -354 как опорную точку, посчитали, ее индекс в итоговом массиве равен 0 - { -354 . . . . }
Поменяли местами 9 и -354 -- исходный массив: { -354 74 9 87 0 }
Разбили массив на два подмассива { } и { 74 9 87 0 } -- исходный массив: { -354 74 9 87 0 }
Меняем местами элементы, не удовлетворяющие условию (слева меньше, справа больше), всё подходит по условию, исходный массив не изменился -- исходный массив: { -354 74 9 87 0 }
В каждом из подмассивов выбрали опорную точку как первый элемент (ничего и 74 соответственно)
Первый подмассив состоит из 0 элементов, так что его не рассматриваем
Сортируем второй подмассив:
1. Разбиваем его еще на два подмассива относительно центра: { 74 } и { 87 0 }
2. Проверяем, выполняется ли условие: не выполняется, 74 > 9, 0 < 9. Исправляем: { 0 } { 87 74 } -- исходный массив: { -354 0 9 87 74}
3. { 0 } нет смысла разбивать на подмассивы, а вот { 87 74 } разбиваем, получаем еще два подмассива: { } и { 74 }, работаем с ними:
  1. Условие не выполняется, значит, 74 перекидываем влево: { 74 } и { } -- исходный массив: { -354 0 9 74 87}
  2. Дальше разбивать нельзя
Массив отсортирован: УРАА ПОБЕДА

Вывод

-354 0 9 74 87

На практике

В качестве опорного элемента следует выбирать случайный элемент массива (int piv = a[rand() % (r - l + 1) + l];), чтобы получить гарантированное время сортировки $Θ (n lo g n)$ в среднем.

is-algo