Быстрая Cортировка (QuickSort)

ИСТОРИЧЕСКАЯ СПРАВКА

В теории алгоритмов большинство методов сортировки базируется на одном из трех фундаментальных принципов: вставка, выбор или обмен. Если рассматривать простейшие реализации этих принципов, то обменная сортировка (cортировка пузырьком) на практике оказывается наихудшей из тройки. Казалось бы, от этого подхода сложно ожидать высокой производительности.

Однако, глубокое усовершенствование принципа обмена позволило создать метод, который по праву считается одним из лучших среди известных алгоритмов сортировки массивов. Его вычислительная эффективность оказалась настолько выдающейся, что автор алгоритма, сэр Чарльз Энтони Ричард Хоар, дал ему весьма громкое, но полностью оправданное название — быстрая сортировка (QuickSort).

начальная идея

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

QuickSort же придерживается совершенно иного подхода. Для достижения предельной эффективности обмены должны происходить между максимально удаленными друг от друга позициями.

Чтобы лучше понять эту концепцию, Никлаус Вирт предлагает рассмотреть идеализированный пример. Представьте массив из $n$ элементов, отсортированный в строго обратном порядке. Как упорядочить его с минимальными затратами? Очевидное решение — взять крайний левый и крайний правый элементы, поменять их местами, а затем сделать шаг навстречу друг другу. Продолжая этот процесс, мы отсортируем весь массив всего за $\frac{n}{2}$ обменов.

Конечно, в реальных задачах мы не можем рассчитывать на то, что массив всегда будет перевернут задом наперед. Эта простая процедура сработает только в одном специфическом случае. Тем не менее, именно эта идея легла в основу самого важного этапа алгоритма — процедуры разделения массива.

АЛГОРИТМ РАЗБИЕНИЯ

Как вы, вероятно, догадались алгоритм основан на принципе разделяй и властвуй. Этот метод заключается в рекурсивном разбиении задачи на две или более подзадачи того же типа, но меньшего размера. Каждая подзадача решается отдельно, а затем результаты комбинируются для получения решения исходной задачи.

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

выбор опорного элемента

Алгоритм начинается с выбора опорного элемента. Назовем его $x$. В реализации Вирта этот элемент выступает в роли своеобразного барьера. После выбора $x$ запускается процесс встречного сканирования массива:

Левый указатель (назовем его $i$) движется слева направо, пока не встретит элемент, который больше или равен $x$.
Правый указатель (назовем его $j$) движется справа налево, пока не встретит элемент, который меньше или равен $x$.

Как только оба указателя остановились — мы нашли нужные элементы. Левый элемент должен находиться в правой части массива, а правый — в левой. Далее, мы просто меняет их местами. Этот процесс продолжается до тех пор, пока указатели $i$ и $j$ не встретятся и не пересекутся где-то в массиве.

В результате мы получаем массив, четко разделенный на две части: слева от точки пересечения лежат ключи, меньшие или равные $x$, а справа — бóльшие или равные $x$.

пример разбиения

В качестве примера рассмотрим массив $$ \begin{bmatrix} 44 & 55 & 12 & 42 & 94 & 06 & 18 & 67 \end{bmatrix} $$ Положим опорный элемент $x = 42$

$i$ указывает на 44, $j$ указывает на 67.
Левый указатель останавливается сразу, т.к. 44 > 42. Правый указатель пропускает 67 и останавливается на 18 (18 < 42). Происходит обмен 44 ↔ 18.
Массив:
Указатель $i$ сдвигается вправо и останавливается на 55 (55 > 42). Указатель $j$ сдвигается влево и останавливается на 06 (06 < 42). Происходит обмен 55 ↔ 06.
Массив:
$i$ проходит 12 и останавливается на 42. $j$ проходит 94 и тоже останавливается на 42. Они указывают на один и тот же элемент, обменивают его самого с собой, после чего $i = 4$, а $j = 2$. Указатели пересеклись ($i > j$), цикл завершается.
Массив:

Таким образом, мы корректно разбили массив на две части. Все элементы до индекса $2$ включительно не превышают $42$, а все элементы, начиная с индекса $4$, не меньше $42$.

Программная реализация разбиения

Перенесём описанный выше алгоритм в код, придерживаясь классических методов структурного программирования.


procedure Partition(var a: array of integer; L, R: integer); // разбиение
var 
  i, j, x, w: integer;
begin
  i := L; 
  j := R;
  x := a[(L + R) div 2]; // выбор центрального элемента в качестве барьера

  repeat
    while a[i] < x do 
      i := i + 1;
    while x < a[j] do 
      j := j - 1;

    if i <= j then
    begin
      w := a[i]; 
      a[i] := a[j]; 
      a[j] := w;
      i := i + 1; 
      j := j - 1;
    end;
  until i > j;
end;

Обратите внимание, что в коде мы используем именно строгие неравенства в циклах while. Если бы мы написали while a[i] <= x, то в случае массива, состоящего из одинаковых элементов, указатель $i$ на первом же шаге вылетел бы за пределы массива (пришлось бы добавлять проверку выхода за границы, что увеличило бы время работы).

ПОЛНЫЙ АЛГОРИТМ БЫСТРОЙ СОРТИРОВКИ

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

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

сортировки