Алгоритм Быстрая сортировка.

Как и в сортировке слиянием, массив разбивается на две части, с условием,

что все элементы первой части меньше любого элемента второй. Потом

каждая часть сортируется отдельно. Разбиение на части достигается

упорядочиванием относительно некоторого элемента массива, т. е. в первой

части все числа меньше либо равны этому элементу, а во второй,

соответственно, больше либо равны. Два индекса проходят по массиву с

разных сторон и ищут элементы, которые попали не в свою группу. Найдя

такие элементы, их меняют местами. Тот элемент, на котором индексы

пересекутся, и определяет разбиение на группы. Классическая реализация

алгоритма выглядит так:

Что же делает данный алгоритм таким быстрым? Ну во-первых, если массив

каждый раз будет делится на приблизительно равные части, то для него

будет верно то же соотношение, что и для сортировки слиянием, т. е. время

работы будет 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).

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.