Этот метод основан на сравнениях ключей и обменах пар элементов, расположенных не в соседних позициях , а удалённых друг от друга в сортируемом массиве.
Быстрая сортировка позволяет сократить количество необходимых операций от величины O(n^2) в среднем до величины O(n*log2(n)). Но в худшем случае, если сортируются данные … то быстрая сортировка имеет O(n^2).
В основе быстрой сортировки лежит процедура разделения сортируемого массива на две части следующим образом:
A = (a1, a2, …, an) –сортируемый массив
Для его разделения на две части выбирается некоторый элемент x данного массива, называемый разделяющий элемент.
Пусть x = a1.
После выбора x элементы массива переупорядочиваются следующим образом
1. Разделяющий элемент размещается в некоторой позиции j: aj := x.
2. Все элементы первой части массива A1 = (a1, a2, …, aj-1) должны удовлетворять условию
f(ai)≤f(aj), i = 1, 2, .., j-1
3. Все элементы второй части массива A2 = (aj+1, aj+2, …, an) должны удовлетворять условию
f(aj)≤f(ai), i = j+1, j+2, .., n.
Если такое разделение выполнено, то исходный массив A можно представить следующим образом:
A = (a1, a2, …, aj-1) aj (aj+1, aj+2, …, an).
В этом массиве разделяющий элемент занимает такое место, в котором он должен находиться после полного упорядочивания. Далее чтобы построить алгоритм сортировки в целом нужно рекуррентно повторить процедуру разделения для вновь полученных массивов A1 и A2, а также для всех подмассивов, созданных при последнем разделении.
Рассмотрим процедуру разделения подробно.
Пусть A – исходный неупорядоченный массив. Введём два счётчика: i = 1, j = n для просмотра элементов слева и справа. Примем в качестве разделяющего x = ai.
1. Просматриваются элементы массива справа и их ключи сравниваются с ключами разделяющего элемента.
Если f(aj)≤f(ai), то выбирается следующий элемент, т.е. j = j – 1. иначе производится обмен местами элементов ai и aj; переменная i увеличивается на единицу i = i + 1; x=aj .
2. Выполняется аналогично, но просматриваются элементы массива слева и их ключи сравниваются с ключами разделяющего элемента.
3. Шаги 1 и 2 повторяются до тех пор, пока после некоторого из них не будет получено равенство значений i = j. Это означает что разделение закончено и разделяющий элемент находится в позиции i = j, x = ai = aj.
Алгоритм быстрой сортировки не является минимальным по памяти, так как для выполнения рекуррентной процедуры при её моделировании с помощью стека, требуются дополнительные затраты памяти в объёме O(log2n).
Рассмотрим реализацию алгоритма быстрой сортировки с помощью рекуррентной процедуры с именем SORT(L,R:integer), которая упорядочивает элементы одного массива с индексами от L до R.
Определим процедуру перестановки двух элементов.
procedure SW(I,j:integer);
var x:integer;
begin
x := a[i];
a[i] := a[j];
a[j] := x
end;
Приведём пример итеративной процедуры сортировки. В ней после каждого разделения массива левую часть будем разделять далее, а границы правой части будем сортировать в стеке для последующего разделения.
Top – указатель вершины стека;
STL, STR– левая и правая границы
procedure SORT;
var i,j,top,L,R:integer;
stL,stR:array[1..100] of integer;
begin
top := 1;
stL[top] := 1;
stR[top] := n;
repeat
L := stL[top];
R := stR[top];
top := top – 1;
repeat
i := L;
j := R;
repeat
while (i
if i
SW(i,j);
i := i + 1;
end;
while (i
if i
SW(i,j);
j := j - 1;
end;
until i=j;
if (i+1)
top := top + 1;
stL[top] := i+1;
stR[top] := R
end;
if L<(i-1) then R := i – 1
else R := L;
until L=R;
until top=0
end;
Быстрая сортировка является наиболее эффективным алгоритмом из всех известных методов сортировки, но все усовершенствованные методы имеют один общий недостаток – невысокую скорость работы при малых значениях n.
Рекурсивная реализация быстрой сортировки позволяет устранить этот недостаток путём включения прямого метода сортировки для частей массива с небольшим количеством элементов.
Анализ вычислительной сложности таких алгоритмов показывает, что если подмассив имеет девять или менее элементов, то целесообразно использовать прямой метод (сортировку простыми вставками).
|