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

Материал из Algocode wiki
Версия от 05:06, 13 сентября 2019; Глеб (обсуждение | вклад) (Новая страница: «==Алгоритм== Быстрая сортировка заключается в том, что на каждом шаге мы находим опорный...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Алгоритм

Быстрая сортировка заключается в том, что на каждом шаге мы находим опорный элемент(пивот), все элементы, которые меньше его кидаем в левую часть, остальные в правую. Заметим, что теперь у нас массив разделен пивотом и нам осталось только отсортировать левую и правую часть массива, для этого давайте запустимся рекурсивно в обе части.

Можно посмотреть тут красивую визуализацию (вкладка 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