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

Хотя идея Шелла значительно улучшает сортировку вставками, резервы еще остаются. Один из наиболее известных алгоритмов сортировки - быстрая сортировка, предложенная Ч.Хоором.

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

Построение быстрой сортировки исходит из того, что для достижения максимальной эффективности желательно выполнять обмены между максимально удалёнными позициями. Пусть у нас есть элементов, расставленных в обратном порядке. Можно отсортировать их всего лишь за обменов, сначала обменяв крайний левый и крайний правый элементы, а потом постепенно продвигаясь внутрь массива с обеих сторон. Разумеется, этот метод сработает, только если элементы в массиве упорядочены в обратном порядке. Но тем не менее именно на этой идее построен рассматриваемый метод.

Попробуем реализовать такой алгоритм: случайно выберем любой элемент (назовём его). Будем просматривать массив слева, пока не найдём элемент, а затем справа, пока не найдём элемент Затем выполним обмен двух найденных элементов и будем продолжать такой процесс, пока оба просмотра не встретятся где-то в середине массива. В результате получим массив, разделённый на две части: левую, с ключами меньшими (или равными), и правую с ключами большими (или равными). Сформулируем процесс разделения в виде процедуры:

procedure partition;

var

i,j: integer;

w,x: integer;

begin

i:=1;

j:=n;

// выбрать наугад значение x

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;

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

procedure sort(L,R: integer);

var

i,j: integer;

w,x: 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;

if L<j then

sort(L,j);

if i<R then

sort(i,R);

end;

procedure QuickSort;

begin

sort(1,N);

end;

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

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

Даже у алгоритма быстрой сортировки есть недостатки. При малых его производительность можно оценить как удовлетворительную, но его преимущество заключается в лёгкости подключения простого метода для обработки сегментов. Ещё остаётся проблема наихудшего случая. Предположим, что каждый раз в качестве разделяющего элемента выбирается наибольшее значение в разделяемом сегменте. Тогда каждый шаг будет разделять фрагмент из элементов на две последовательности из и элементов, соответственно. Очевидно, что в наихудшем случае поведение оценивается величиной. Чтобы избежать наихудшего случая, было предложено выбирать элемент, как медиану из трёх значений разделяемого сегмента. Такое дополнение не ухудшает алгоритм в общем случае, но сильно улучшит его поведение в наихудшем случае.

Дата добавления: 2014-01-15