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

Быстрая сортировкасортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем \(O(n\log n)\) обменов при упорядочении \(n\) элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

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

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

Преимущества QuickSort по сравнению с другими алгоритмами быстрой сортировки заключается в том, что он не использует дополнительных массивов, сортировка происходит "на месте".

Алгоритм состоит из трёх шагов:

  1. Выбор опорного элемента из массива (X).
  2. Этап разделения. Перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные — после.
    A[i] < X A[i]>=X
    Теперь элементы расположены так, что ни один элемент из первой граппу при сортировке не окажется во второй группе, и наоборот.
    Поэтому достаточно отсортировать отдельно каждую часть массива - это и есть подход "разделяй и властвуй"
  3. Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один или отсутствуют элементы.
Процедура сортировки должна принимать три параметра:
- массив, который сортируем
- индекс первого элемента сортируемого участка
- индекс последнего элемента сортируемого участка

Алгоритм на псевдокоде:
АЛГ 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