Dyzzet|
C++ Data Science Алгоритмы Темы · Блог · YouTube
Быстрая сортировка
Интерактивная анимация
Авторы: Dyzzet, immsmoa

Быстрая сортировка (quicksort) иначе называется сортировкой Хоара. Её идея предельно проста: в массиве выбирают некий опорный элемент (pivot), разбивают массив на две части: слева элементы меньше опорного, справа — больше. Затем процесс рекурсивно повторяется для левой и правой частей массива.

Существуют разные модификации быстрой сортировки и способы её реализации. В данном варианте в функцию передаётся массив и индексы крайних элементов: quickSort(data, 0, n- 1);. В другом варианте можно было бы передавать адрес начала массива и его размер: quickSort(data, n);.

Обратим внимание на два фрагмента из кода, который расположен далее. В каждом рекурсивном вызове водятся l = left; и r = right;, они хранят индексы крайнего левого и крайнего правого элементов.

Такой цикл перебирает элементы слева направо и останавливается, когда встречает элемент, который больше либо равен опорному.

while (l <= r && data[l] < pivot) 
{
    ++l; 
}

Аналогичный цикл перебирает элементы справа налево и останавливается, когда встречает элемент, который меньше либо равен опорному.

while (r >= l && data[r] > pivot) 
{
    --r; 
}

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

Опорный элемент можно выбирать по-разному: элемент из центра массива, элемент с того или иного края, среднее арифметическое между крайними, случайный элемент и т. д. Обратите внимание, что переключатель ниже меняет одну строку в коде.

Центральный элемент

Крайний левый элемент

Крайний правый элемент

Случайный элемент

 
function quickSort(data[], left, right)
{
pivot = data[(left + right) / 2];
l = left, r = right;
while (l <= r)
{
while (l <= r && data[l] < pivot)
{
++l;
}
while (r >= l && data[r] > pivot)
{
--r;
}
if (l == r && l == left)
{
++l;
}
if (l == r && l == right)
{
--r;
}
if (l < r)
{
swap(data[l], data[r]);
++l;
--r;
} else {
break;
} }
if (r - left + 1 >= 2)
{
quickSort(data, left, r);
}
if (right - r >= 2)
{
quickSort(data, r + 1, right);
} }
9 апреля 2021
алгоритмы интерактив
Зарегистрируйтесь и войдите, чтобы оставлять комментарии и голосовать.

Сортировки
Сортировка пузырьком
Сортировка выбором
Гномья сортировка
Сортировка вставками
Сортировка Шелла
Быстрая сортировка
Быстрая сортировка. Вариант с указателем
Пирамидальная сортировка
Также может быть интересным
© MMXI—MMXXIII. RSS. Поддержать сайт
Светлая тема / тёмная тема