Энциклопедия Turbo Pascal. Главы 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;
         x, y: DataItem;
       begin
         i:=l; j:=r;
         x:=it[(l+r) div 2];
         repeat
           while it[i]<x do i := i+1;
           while x<it[j] do j := j-1;
           if y<=j then
           begin
             y := it[i];
             it[i] := it[j];
             it[j] := y;
             i := i+1; j := j-1;
           end;
         until i>j;
         if l<j then qs(l, j, it);
         if l<r then qs(i, r, it)
       end;
     begin
       qs(1, count, item);
     end; { конец быстрой сортировки }

В данном примере процедура быстрой сортировки обращается к основной процедуре сортировки с именем  "qs".  Это обеспечивает доступ к данным "item" и "count" при всех вызовах "qs".

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

Равенство

          N = a**x

можно представить в виде

     x = loga  n.

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

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

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