Учебно-методическое пособие. Алматы, 2017 ббк

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

Метод быстрой сортировки был разработан Ч.Ф.Р.Хоаром и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки.

В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве "основы" и затем весь массив разбивается на две части. Одну часть составляют все элементы, равные или большие "основы", а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован. Например, для массива "fedacb" при использовании в качестве значения разбиения "d" будут получены следующие проходы при выполнении быстрой сортировки:

- исходное состояние: f e d a c b;

- первый проход: d c a d e f;

- второй проход: a b c d e f.

Этот процесс продолжается для каждой части "вса" и def". Фактически этот процесс имеет рекурсивную природу. И действтительно, наиболее "аккуратно" быстрая сортировка реализуется посредством рекурсивного алгоритма.

Выбор значения разбиения можно сделать двумя способами. Это значение можно выбирать случайным образом или путем усреднения небольшого числа значений, выбранных из массива. Для оптимальной сортировки требуется выбрать значение, которое будет находиться в точности посередине всех элементов. Однако, для большинства наборов данных это сделать нелегко. Однако, даже в худшем случае, когда выбирается одно из экстремальных значений, быстрая сортировка работает достаточно хорошо.

В приводимом ниже алгоритме быстрой сортировки в качестве значения разбиения используется среднее значение. Хотя такой подход не всегда является наилучшим, он достаточно прост и сортиров ка будет выполняться правильно.
procedure QuickSort(var item: DataArray; count:integer);
{ описание под процедуры }

procedure qs(l, r: integer; var it: DataArray);

var

i, j: integer;

begin

x:=it[(l+r) div 2];

repeat

while it[i]

while x

if y<=j then

begin

y := it[i];

it[j] := y;

i := i+1; j := j-1;

end;

if l

if l

end;

begin

end; { конец быстрой сортировки }

Вывод числа операций сравнения и числа операций обмена для быстрой сортировки выходит за рамки данной книги. Можно считать, что число операций сравнения равно n log n, а число операций обмена равно приблизительно n/6 log n. Эти характеристики значительно лучше характеристик рассмотренных ранее сортировок.

Равенство N = a^x можно представить в виде x = log_a n.

Это, например, будет означать, чо при сортировке ста элементов методом быстрой сортировки потребуется в среднем 100*2, т.е. 200 операций сравнений, так как log 100 равен 2. Это значение является вполне хорошим по сравнению со значением 990 для сортировки пузырьковым методом.

Однако, следует иметь в виду одно неприятное свойство быстрой сортировки. Если выбираемое для разбиения значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную с временем выполнения n . Однако, на практике этот случай не встречается.

Необходимо тщательно выбирать метод определения значения разбиения. Часто это значение определяется по фактическим данным, которые сортируются.