Суть: из коллекции выбирается некоторый опорный элемент (pivot) a[i], запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] – вправо. Рекурсивно запускаем процедуру для левой и правой частей.
Нет использования доп. памяти!
[https://triptonkosti.ru/7-foto/shema-algoritma-bystraya-sortirovka-81-foto.html ](https://lh7-us.googleusercontent.com/vwKT8ruE8bXehcBw8Ni69fQDm9cly3c3hJRBX09wRIR7HkWt7mGJNWSurAvRAtGacVZEOcxHn0e9U0CBAWmzzILAl0aCkeBqhqDStRnRA-5dwXXUTzqKcY4Jl-BhCvsM208JuT8eCYCkfH32774piw)
https://triptonkosti.ru/7-foto/shema-algoritma-bystraya-sortirovka-81-foto.html
1 шаг – выбираем опорный элемент (last for lomuto and middle for hoare partition)
2 шаг – partition: разделяем массив на две части: левая с элементами, меньшими pivot, правая – большими, чем pivot. 2 варианта:
3 шаг – рекурсией продолжаем повторять первые два шага, пока в массивах не останется по одному элементу => массив отсортирован
Сложность по времени:
Лучший случай: сортируемая часть всегда разделяется пополам O(n * log2(n))
Средний случай: О(n * log2(n))
Худший случай: за pivot всегда будем выбирать либо максимальный, либо минимальный элемент. Разделение будет неравномерным, и будем «отсчитывать» по одному элементу O(n^2)