Быстрая сортировка
Алгоритм
Быстрая сортировка заключается в том, что на каждом шаге мы находим опорный элемент(пивот), все элементы, которые меньше его кидаем в левую часть, остальные в правую. Заметим, что теперь у нас массив разделен пивотом и нам осталось только отсортировать левую и правую часть массива, для этого давайте запустимся рекурсивно в обе части.
Можно посмотреть тут красивую визуализацию (вкладка QUI).
Реализация
1 void quicksort(int l, int r){
2 if (l < r){
3 int index = (l + r) / 2; /* index - индекс опорного элемента для
4 начала сделаем его равным середине отрезка*/
5 index = divide(l, r, index); /* divide - функция разбивающие элементы
6 на меньшие и больше/равные a[index],
7 при этом функция возвращает границу разбиения*/
8 quicksort(l, index);
9 quicksort(index + 1, r);
10 }
11 }
Оценка времени работы
Давайте оценим асимптотику данной сортировки. На случайных данных она работает за $O(N\log{N})$ , так как каждый раз мы будем делить массив на две примерно равные части, то есть суммарно размер рекурсии будет около логарифма и при этом на каждом этапе рекурсии мы просмотрим не более, чем размер массива. Однако можно легко найти две проблемы, одна - одинаковые числа, а вторая - середина - минимум или максимум.
Существуют несколько выходов из этой ситуации :
1) Давайте если быстрая сортировка работает долго, то запустим любую другую сортировку за $NlogN$.
2) Давайте делить массив не на две, а на три части(меньше, равны, больше).
3) Чтобы избавиться от проблемы с максимумом/минимумом в середине, давайте брать случайный элемент .
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin