4. Алгоритм быстрой сортировки (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²).