Алгоритм 6. Быстрая сортировка
Теперь переходим к самому интересному, а именно к одной из самых быстрых и эффективных из известных сортировок, которая так и называется — «быстрая сортировка».
Как и в сортировке слиянием, массив разбивается на две части, с условием, что все элементы первой части меньше любого элемента второй. Потом каждая часть сортируется отдельно. Разбиение на части достигается упорядочиванием относительно некоторого элемента массива, т. е. в первой части все числа меньше либо равны этому элементу, а во второй, соответственно, больше либо равны. Два индекса проходят по массиву с разных сторон и ищут элементы, которые попали не в свою группу. Найдя такие элементы, их меняют местами. Тот элемент, на котором индексы пересекутся, и определяет разбиение на группы. Классическая реализация алгоритма выглядит так:
Program QuickSort;
Var A : array[1..1000] of integer;
N,T : integer;
Procedure Sort(p,q : integer); {p,q — индексы начала и конца сортируемой части массива} Var i,j,r : integer;
Begin
if p<q then {массив из одного элемента тривиально упорядочен} begin r:=A[p];
i:=p-1;
j:=q+1;
while i<j do
begin
repeat
i:=i+1;
until A[i]>=r;
repeat
j:=j-1;
until A[j]<=r;
if i<j then
begin
T:=A[i];
A[i]:=A[j];
A[j]:=T;
end;
end;
Sort(p,j);
Sort(j+1,q);
end; End;
Begin
{Определение размера массива A — N) и его заполнение} … {запуск сортирующей процедуры} Sort(1,N); {Вывод отсортированного массива A} … End.
Program QuickSort;
Var A : array[1..1000] of integer;
N,T : integer;
Procedure Sort(p,q : integer); {p,q — индексы начала и конца сортируемой части массива} Var i,j,r : integer;
Begin if p<q then {массив из одного элемента тривиально упорядочен}
begin
r:=A[p];
i:=p-1;
j:=q+1;
while i<j do
begin
repeat
i:=i+1;
until A[i]>=r;
repeat
j:=j-1;
until A[j]<=r;
if i<j then
begin
T:=A[i];
A[i]:=A[j];
A[j]:=T;
end;
end;
Sort(p,j);
Sort(j+1,q);
end;
End; Begin {Определение размера массива A — N) и его заполнение}
… {запуск сортирующей процедуры}
Sort(1,N); {Вывод отсортированного массива A}
…
End. |
Что же делает данный алгоритм таким быстрым? Ну во-первых, если массив каждый раз будет делится на приблизительно равные части, то для него будет верно то же соотношение, что и для сортировки слиянием, т. е. время работы будет O(nlog2n). Это уже само по себе хорошо. Кроме того, константа при nlog2n очень мала, ввиду простоты внутреннего цикла программы. В комплексе это обеспечивает огромную скорость работы. Но как всегда есть одно «но». Вы, наверное, уже задумались: а что если массив не будет делится на равные части? Классическим примером является попытка «быстро» отсортировать уже отсортированный массив. При этом данные каждый раз будут делиться в пропорции 1 к n-1, и так n раз. Общее время работы при этом будет O(n2), тогда как вставкам, для того чтобы «понять», что массив уже отсортирован, требуется всего-навсего O(n). А на кой нам сортировка, которая одно сортирует хорошо, а другое плохо? А собственно, что она сортирует хорошо? Оказывается, что лучше всего она сортирует случайные массивы (порядок элементов в массиве случаен). И поэтому нам предлагают ввести в алгоритм долю случайности. А точнее, вставить randomize и вместо r:=A[p]; написать r:=A[random(q-p)+p]; т. е. теперь мы разбиваем данные не относительно конкретного, а относительно случайного элемента. Благодаря этому алгоритм получает приставку к имени «вероятностный». Особо недоверчивым предлагаю на своем опыте убедится, что данная модификация быстрой сортировки сортирует любые массивы столь же быстро.
А теперь еще один интересный факт: время O(nlog2n) является минимальным для сортировок, которые используют только попарное сравнение элементов и не использует структуру самих элементов. Тем, кому интересно, откуда это взялось, рекомендую поискать в литературе, доказательство я здесь приводить не намерен, не Дональд Кнут, в конце концов :-). Но вы обратили внимание, что для рассмотренных алгоритмов в принципе не важно, что сортировать — такими методами можно сортировать хоть числа, хоть строки, хоть какие-то абстрактные объекты. Следующие сортировки могут сортировать только определенные типы данных, но за счет этого они имеют рекордную временную оценку O(n).
