Быстрая сортировка
Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем \(O(n\log n)\) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Быстрый метод сортировки функционирует
по принципу "разделяй и властвуй" (рекурсивное разбиение решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинирование их решений для получения ответа к исходной задаче
).
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (например, рассмотренной нами "Пузырьковой сортировки"), известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. (Таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.)
Преимущества QuickSort по сравнению с другими алгоритмами быстрой сортировки заключается в том, что он не использует дополнительных массивов, сортировка происходит "на месте".
Алгоритм состоит из трёх шагов:
- Выбор опорного элемента из массива (
X).
- Этап разделения. Перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные - после.
Теперь элементы расположены так, что ни один элемент из первой группы при сортировке не окажется во второй группе, и наоборот.
Поэтому достаточно отсортировать отдельно каждую часть массива - это и есть подход "разделяй и властвуй".
- Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один или отсутствуют элементы.
Процедура сортировки должна принимать три параметра:
- массив, который сортируем;
- индекс первого элемента сортируемого участка;
- индекс последнего элемента сортируемого участка.
Алгоритм на псевдокоде:
АЛГ QUICKSORT(A[], START, END)
// если условие выполняется, то в рабочей части массива
// меньше двух элементов,
// то есть сортировать уже ничего не нужно
ЕСЛИ START >= END, ТО ВЫЙТИ ИЗ ПРОЦЕДУРЫ
// в качестве опорного элемента можно брать
// случайное число на отрезке сортируемого участка,
// можно брать средний элемент
X = СЛУЧАЙНЫЙ ЭЛЕМЕНТ МАССИВА НА ОТРЕЗКЕ [START; END]
L = START, R = END
ПОКА L <= R
// ищем элементы для перестановки
ПОКА A[L] < X
L += 1
ПОКА A[R] > X
R -= 1
// если нужно делаем перестановку
ЕСЛИ L <= R, то
МЕНЯЕМ МЕСТАМИ A[L] И A[R]
L += 1
R -= 1
// осталось отсортировать отдельно первую и вторую части
QUICKSORT(A, START, R)
QUICKSORT(A, L, END)
Данная процедура может отсортировать любую часть массива, для этого достаточно верно указать параметры
START и
END.
Сравнение времени работы (в секундах) различных алгоритмов сортировки для массивов разного размера (
N):
| N |
Пузырьковая сортировка |
Сортировка вставками |
Быстрая сортировка |
| 5000 |
0,039 |
0,016 |
0,00031 |
| 15000 |
0,359 |
0,141 |
0,00078 |
| 50000 |
3,985 |
1,469 |
0,00297 |
Обратите внимание, что алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементам списка. При таких условиях, быстрая сортировка в худшем случае будет выполняться
O(n²).