Алгоритм быстрой сортировки (QuickSort)

Алгоритм Шелла был значительным шагом в повышении эффективности сортировки по сравнению с простыми алгоритмами. Однако он явно уступает по скорости другому алгоритму, для которого его автор, Ч.Хоар, придумал несколько нескромное, но вполне заслуженное название QuickSort («быстрая сортировка»).

В основе этого алгоритма – операция разделения массива. Пусть x – некоторый произвольно выбранный элемент сортируемого массива (разделяющий элемент). Операция разделения имеет целью переставить элементы массива таким образом, чтобы сначала шли элементы, меньшие или равные x (не обязательно в порядке возрастания), а затем элементы, большие или равные x. При этом совершенно неважно, где именно окажется после разделения сам элемент x.

Чтобы выполнить разделение, начнем просматривать элементы массива слева направо и остановимся на первом из элементов, большем или равном x. Пусть индекс этого элемента равен i. Аналогичным образом, начав с правого конца массива, остановимся на самом правом элементе, меньшем или равном x (индекс элемента – j). Поменяем местами элементы i и j, а затем продолжим идти вправо от i и влево от j, меняя местами пары элементов, стоящих не на месте. Разделение окончится, когда будет i > j.

Алгоритм быстрой сортировки можно теперь описать таким образом. Возьмем произвольный элемент массива x и выполним для него операцию разделения. Если левый и/или правый отрезки массива содержат более одного элемента, то выполним для каждого из этих отрезков ту же операцию, что и для всего массива (т.е. выберем произвольный элемент, выполним разделение и т.д.). Сортировка заканчивается, когда все полученные отрезки содержат по одному элементу.

Организовать вышеописанное многократное выполнение операции разделения проще всего с помощью рекурсивного определения процедуры сортировки, как показано ниже.

procedure QuickSort(var A: TableType);

var

k :Integer;

z, tmp :KeyType;

procedure SortInterval(l, h :Integer);

{Рекурсивная процедура сортировки отрезка массива

от индекса l до h}

var

i, j :Integer;

begin

k := (l + h) div 2;

{разделяющий элемент – из середины отрезка}

z := A[k];

i := l; j := h;

repeat

while A[i] < z do begin

i := i + 1;

end;

while A[j] > z do begin

j := j - 1;

end;

if i <= j then begin

tmp := A[j]; A[j] := A[i]; A[i] := tmp;

i := i + 1;

j := j - 1;

end;

until i > j;

if l < j then

SortInterval(l, j);

{рекурсивный вызов для левой части отрезка}

if h > i then

SortInterval(i, h);

{и для правой части}

end; {SortInterval}

begin {QuickSort}

SortInterval(1, N);

end; {QuickSort}

Основная работа выполняется в рекурсивной процедуре SortInterval.

В некоторых местах программы напрашиваются улучшения. Например, хочется заменить условие цикла “while A[i] < z” на “while A[i] <= z” и аналогично для j. Однако следует быть крайне осторожным: данный алгоритм очень чуток к мелким неточностям программирования. Приведенный вариант хорош тем, что наверняка работает.

Нерекурсивное описание алгоритма оказывается сложнее, так как при необходимости сортировать два отрезка массива, образовавшиеся после разделения, приходится явно сохранять в стеке один из отрезков (точнее, два граничных значения его индексов), пока сортируется другой. В то же время нерекурсивный вариант обычно оказывается более эффективным и, что немаловажно, он позволяет уменьшить используемую глубину стека. Для этого следует всегда из двух отрезков массива, подлежащих сортировке, заносить в стек более длинный. При этом можно гарантировать, что максимальное количество отрезков, одновременно находящихся в стеке, не может превысить log₂(n).

На эффективность алгоритма быстрой сортировки влияет также выбор разделяющего элемента z. Было бы замечательно, если бы выбранный элемент z всегда оказывался средним по величине, так, чтобы при разделении получались два равных отрезка. Нетрудно оценить эффективность алгоритма сортировки в этом случае. Если при каждом разделении отрезки уменьшаются вдвое, то потребуется log₂(n) этапов разделения, чтобы длина отрезков стала равна 1. Каждый этап разделения требует по одному разу просмотреть каждый элемент массива, т.е. требует времени порядка O(n). Следовательно, на всю сортировку потребуется время T(n) = O(n×log(n)).

Беда в том, что мы не можем выбирать средний по величине элемент в качестве разделяющего. Отыскание такого элемента (он называется медианой массива), как будет показано в разделе 7, представляет собой задачу не намного проще, чем сама сортировка. Поэтому приходится применять более простые правила выбора. Обычно в качестве x выбирают либо элемент из середины массива, либо элемент со случайно выбранным индексом. При этом может оказаться, что сделан самый неудачный выбор, а именно – выбран максимальный либо минимальный элемент массива. В этом случае в результате разделения массива длиной n будет получен только один отрезок длиной n–1, а второй отрезок будет содержать только один элемент. Если невезение продолжится при следующих выборах, то придется выполнить n–1 разделение, просматривая в среднем по n/2 элементов. Очевидно, в этом худшем случае T_макс(n) = O(n²), т.е. алгоритм QuickSort ведет себя не лучше пузырька.

К счастью, можно доказать, что в среднем случае, когда элементы массива случайны, имеет место такая же оценка, как и в лучшем случае: T_ср(n) = O(n×log(n)). Это говорит о том, что худший случай для QuickSort является большой редкостью и может встретиться скорее в специально подобранном контрпримере, чем на практике.

Если исходный массив состоит из случайных элементов, то разделяющий элемент z может выбираться произвольным образом, можно даже всегда брать первый элемент массива в качестве разделяющего. Однако легко видеть, что выбор в качестве z первого или последнего элемента приводит к очень плохим результатам, если исходный массив оказывается уже сортированным или близким к сортированному. Поэтому, как было сказано выше, обычно выбирают элемент из середины массива или элемент со случайным номером. Иногда используют чуть более сложное правило: взять первый элемент массива, последний элемент, элемент из середины массива и выбрать в качестве x средний по величине из этих трех. В этом случае есть гарантия, что при разделении не будет получен отрезок длиной 1. Однако неясно, компенсирует ли это небольшое улучшение затраты времени на более сложное правило выбора.

Алгоритм QuickSort показал себя на практике как самый быстрый из известных алгоритмов сортировки массивов, несмотря на то, что в худшем случае он может потребовать времени порядка O(n²).