СОРТИРОВКА

    Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= i.
    Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах.
    Основное отличие между сортировкой массивов и сортировкой последовательных файлов заключается в том, что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами. Напротив, в последовательном файле в каждый момент времени доступен лишь один элемент. Из-за этих отличий методы сортировки существенно отличаются для этих двух видов сортировки.
    В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки, который используется в сравнениях. Когда выполняется обмен, передается вся структура данных. Например, в списке почтовых отправлений в качестве ключа сортировки может использоваться почтовый индекс, а в операциях обмена к почтовому индексу добавляются полное имя и адрес. Для простоты в примерах, иллюстрирующих методы сортировки, используются символьные массивы. Затем будет показано, как эти методы можно адаптировать к любым структурам данных.

Классы алгоритмов сортировки

    Имеется три способа сортировки массивов:

• сортировка обменом;
• сортировка выбором;
• сортировка вставкой.

    Представьте, что перед вами лежит колода карт. Для сортировки карт обменом вы должны разложить карты на столе лицевой стороной вверх и затем менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.
    Для сортировки выбором вы должны разложить карты на столе, выбрать самую младшую карту и взять ее в свою руку. Затем вы должны из оставшихся на столе карт вновь выбрать наименьшую по значению карту и поместить ее позади той карты, которая уже имеется у вас в руке. Этот процесс вы должны продолжать до тех пор, пока все карты не окажутся у вас в руках. Поскольку каждый раз вы выбираете наименьшую по значению карту из оставшихся на столе, по завершению такого процесса карты у вас в руке будут отсортированы.
    Для сортировки вставкой вы должны держать карты в своей руке, поочередно снимая карту с колоды. Каждая взятая вами карта помещается в новую колоду на столе, причем она ставится на соответствующее место. Колода будет отсортирована, когда у вас в руке не окажется ни одной карты.

Оценка алгоритмов сортировки

    Для каждого метода сортировки имеется много алгоритмов. Каждый алгоритм имеет свои достоинства, но в целом оценка алгоритма сортировки зависит от ответов, которые будут получены на следующие вопросы:

• с какой средней скоростью этот алгоритм сортирует информацию?;
• какова скорость для лучшего случая и для худшего случая?;
• поведение алгоритма является естественным или является не естественным?;
• выполняется ли перестановка элементов для одинаковых ключей?

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

  type
  DataItem = char;
  DataArray = array [1..80] of DataItem;

    Следовательно, для изменения используемых в сортировках типов данных требуется изменить только эти два определения типов. Размерность массива выбрана произвольно и вы можете при необходимости их изменить.

Сортировка пузурьковым методом.

    Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок.
    Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ниже показана самая простая форма программы сортировки методом пузырька:

{ сортировка пузырьковым методом}

procedure Bubble(var item: DataArray; count:integer);
var
  i,j : integer;
  x : DataItem;
begin
  for i := 2 to count do
    begin
      for j := count downto i do
        if item[j-1]>item[j] then
          begin
            x := item[j-1];
            item[j-1] := item[j];
            item[j] := x;
          end;
    end;
end; {конец сортировки пузырьковым методом}

    В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве.
    Сортировка пузырьковым методом имеет два цикла. Поскольку число элементов массива задается переменной "count", внешний цикл вызывает просмотр массива count - 1 раз. Это обеспечивает нахождение каждого элемента в своей позиций после завершения процедуры. Внутренний цикл предназначен для фактического выполнения операций сравнения и обмена.
    Эта версия сортировки пузырьковым методом может сортировать символьный массив в порядке возрастания значений элементов. Например, следующая короткая программа сортирует строку, которая считывается с дискового файла "test.dat". Эта же программа может использоваться с другими подпрограммами сортировки.

program SortDriver;

{эта  программа  будет  считывать 80 или меньше символов с дискового файла 
"test.dat",  отсортирует их и выдаст pезультат на экран дисплея}
type
   DataItem = char;
   DataArray = array [1..80] of char;
var
  test: DataArray;
  t, t2: integer;
  testfile: file of char;

{сортировка пузырьковым методом}
procedure Bubble(var item: DataArray; count:integer);

var
  i,j: integer;
  x: DataItem;
begin
  for i := 2 to count do
    begin
      for j := count downto i do
        if item[j-1]>item[j] then
        begin
          x := item[j-1];
          item[j-1] := item[j];
          item[j] := x;
        end;
    end;
end;

begin
Assign(testfile, 'test.dat');
  Reset(testfile);
  t := 1;
   
  {считывание символов,которые будут сортироваться.}

  while not Eof(testfile) do begin
    read(testfile, test[t]);
      t := t+1;
  end;
  t := t-2; {скорректировать число считанных элементов}

  Bubble(test, t); {сортировать массив}

  {выдать отсортированный массив символов}
  for t2 := 1 to t do write(test[t2]);
  WriteLn;
end.

    Для иллюстрации работы сортировки пузырьковым методом ниже даны результаты каждого этапа сортировки массива "dcab":

исходное положение:   d c a b; 
первый проход:        a d c b; 
второй проход:        a b d c; 
третий проход:        a b c d. 
 

    При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худшем случаях. Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/ 2 (n²-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу.
    Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3/4 (n²-n), а для наихудшего случая будет равно 3/2 (n²-n) раз. Можно заметить, что по мере ухудшения упорядоченности исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует три операции обмена). Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива.
    Например, если не учитывать время операций обмена, выполняемых для перестановки неупорядоченных элементов, то тогда при выполнении одной операции сравнения в течение 0,001 секунд сортировка десяти элементов займет 0,05 секунд, сортировка ста элементов займет 5 секунд, а сортировка 1000 элементов займет 500 секунд. Сортировка 100 000 элементов (такой размер имеет небольшой телефонный справочник) потребовала бы 5 000 000 секунд или около 1400 часов (т.е. два месяца непрерывной работы)!
    Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым методом, получившая название "челночной сортировки" из-за соответствующего характера движений по массиву.
    Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

{челночная сортировка является улучшенной версией сортировки пузырьковым методом}
procedure Shaker(var item: DataArray; count:integer);
var
  j, k, l, r: integer;
  x: DataItem;
begin
  l := 2; r := count; k := count;
  repeat
    for j := r downto l do
      if item[j-1] then
      begin    { обмен }
        x := item[j-1];
        item[j-1] := item[j];
        item[j] := x;
        k := j;
      end;

    l := k+1;

    for j := l to r do
      if item[j-1]>item[j] then
      begin   { обмен }
        x := item[j-1];
        item[j-1] := item[j];
        item[j] := x;
        k := j;
      end;

    r := k-1;
  until l>r
end; {конец челночной сортировки}

    Ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

Сортировка выбором

    При сортировке выбором выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов. Например, если сортировку выбором применить для массива "bdac", то будут получены следующие проходы:

исходное положение:   b d a c; 
первый проход:        a d b c; 
второй проход:        a b b c; 
третий проход:        a b c d. 
 

    К сожалению как и в сортировке пузырьковым методом внешний цикл выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (n²-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3(n-1), а в худшем случае равно n²/4+3(n-1). В лучшем случае /когда исходный массив уже упорядочен/ потребуется поменять местами только n-1элементов,а каждая операция обмена требует три операции пересылки.

{сортировка выбором}
procedure Selekt(var item: DataArray; count:integer);
var
  i, j, k: integer;
  x: DataItem;
begin
  for i := i to count-1 do
  begin
    k := i;
    x := item[i];
    for j := i+1 to count do {найти элемент с наименьшим значением}
    if item[j]<x then
    begin
      k := j;
      x := item[j];
    end;
    item[k] := item[i];  {обмен}
    item[i] := x;
  end;
end; {конец сортировки выбором}

     В среднем число операций обмена равно n(ln+y), где "y" является константой Эйлера, приблизительно равной 0,577216. Это значит, что несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.

Сортировка вставкой

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

исходное положение:   d c a b;
первый проход:        c d a b; 
второй проход:        a c d b;  
третий проход:        a b c d.
 

    Ниже приводится алгоритм сортировки вставкой:

{ сортировка вставкой }
procedure Inser(var item: DataArray; count:integer);
var
  i, l: integer;
  x: DataItem;
begin
  for i := 2 to count do
    begin
      x := item[i];
      j := i-1;
      while (x<item[j]) and (j>0) do
      begin
        item[j+1] := item[j];
        j := j-1;
      end;
      item[j+1] := x;

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

    В отличие от сортировки пузырьковым методом и сортировки выбором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов. Если исходный массив уже упорядочен, то число операций сравнения равно n-1. Если массив упорядочен в обратном порядке, то число операций сравнения равно 1/2 (n² +n)-1,давая в среднем значение 1/4 (n²+n-2).
    Число операций обмена будет следующим:

• для лучшего случая: 2 (n-1);
• в среднем: 1/4 (n²+9n-10);
• для худшего случая: 1/2 (n²+3n-4).

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

Усовершенствованные алгоритмы сортировки

    Все рассматриваемые до сих пор алгоритмы сортировки обладают очень серьезным недостатком, а именно, время их выполнения пропорционально квадрату числа элементов. Для больших объемов данных эти сортировки будут медленными, а начиная с некоторой величины они будут слишком медленными, чтобы их можно было использовать на практике. Каждый программист слышал или рассказывал "страшные" истории о "сортировке, которая выполнялась три дня". К сожалению эти истории часто не являлись выдумкой.
    Если сортировка выполняется слишком долго, то причиной этого может быть используемый алгоритм. Однако, первая реакция на такое поведение сортировки выражается словами: "Давай напишем программу на ассемблере". Хотя использование ассемблера почти всегда позволяет повысить быстродействие программы в некоторое число раз с постоянным коэффициентом, но если выбранный алгоритм не является достаточно хорошим, то сортировка вне зависимости от оптимальности кода по-прежнему будет выполняться долго. Следует помнить, что при квадратичной зависимости времени выполнения программы от числа элементов массива повышение оптимальности кода или повышение быстродействия ЭВМ приведет лишь к незначительному улучшению, поскольку время выполнения программы будет увеличиваться по экспоненте. Следует помнить, что если какая-либо программа, написанная на языке Паскаль, выполняется недостаточно быстро, то она не станет выполняться достаточно быстро, если ее написать на ассемблере. Решение лежит в использовании лучшего алгоритма сортировки.
    В этой главе будут рассмотрены две очень хорошие сортировки. Первая носит название сортировки Шелла, а вторая называется быстрой сортировкой, алгоритм которой признан наилучшим. Эти сортировки выполняются очень быстро.

Сортировка Шелла

    Сортировка Шелла получила свое название по имени ее создателя Д.Л.Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морских ракушек друг на друга.
    Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами. На рис.1 показана схема выполнения сортировки Шелла для массива "f d a c b e". Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.

проход 1                   f   d   a   c   b   e
проход 2       		   c   b   a   f   d   e
проход 3      		   a   b   c   e   d   f
полученный результат       a   b   c   d   e   f
 

    Рис.1. Сортировка Шелла.

{ сортировка Шелла }
procedure Shell(var item: DataArray; count:integer);
const
  t = 5;
var
  i, j, k, s, m: integer;
  h: array[1..t] of integer;
  x: DataItem;
begin
  h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
  for m := 1 to t do
    begin

  k:=h[m];
  s:=-k;
  for i := k+1 to count do
  begin
    x := item[i];
    j := i-k;
    if s=0 then
    begin
      s := -k;
      s := s+1;
      item[s] := x;
    end;
    while (x<item[j]) and (j<count) do
      begin
        item[j+k] := item[j];
        j := j-k;
      end;
      item[j+k] := x;
    end;
  end;
end; { конец сортировки Шелла }

    При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
    Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в показанном выше примере. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. /Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно/.
    Внутренний цикл имеет два условия проверки. Условие "х<item[j]" необходимо для упорядочения элементов. Условия "j>0" и "j<=count" необходимы для того, чтобы предотвратить выход за пределы массива "item". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки.
    Анализ сортировки Шелла требует решения некоторых сложных математических задач. Время выполнения сортировки Шелла пропорционально n^1.2. Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.

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

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

исходное состояние:   f e d a c b;
первый проход:        d c a d e f;
второй проход:        a b c d e f.  
 

    Этот процесс продолжается для каждой части "abc" и "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 = ax
можно представить в виде
           x = logan.

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

Сортировка данных других типов

    До сих пор рассматривались сортировки для символьных массивов. Это позволяло представлять алгоритмы сортировки в более простом виде. Как указывалось ранее, при сортировке могут использоваться массивы любых встроенных типов данных. Для этого достаточно изменить определение типа данного "DataItem". Однако, часто приходится сортировать сложные типы данных, например, символьные строки или сгруппированные в записи данные. (Напомним, что в большинстве сортировках упорядочиваются элементы, имеющие ключ, с которым связаны другие данные). Для того, чтобы настроить алгоритмы сортировки на другие структуры данных достаточно изменить блок сравнений, блок обмена или оба эти блока. Основа алгоритма остается неизменной.
    Поскольку быстрая сортировка является одной из самых лучших, имеющихся в настоящее время сортировок, она будет использоваться в последующих примерах. Те же методы, однако, можно применять для любых ранее описанных сортировок.

Сортировка символьных строк

    Для сортировки символьных строк проще всего создать массив символьных строк, используя предусмотренный в языке Паскаль тип данных "string". Это дает вам простой способ индексирования и выполнения операций обмена при сохранении основного алгоритма сортировки неизменным. Приводимая ниже версия алгоритма быстрой сортировки позволяет упорядочивать символьные строки в алфавитном порядке:

type
  DataItem = string[80];
  DataArray = array [1..80] of DataItem;

{ алгоритм быстрой сортировки для символьных строк }
procedure QsString(var item: DataArray; count:integer);
  procedure qs(l, r: integer; var it:DataArray);
    var
    i, l: 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 i<=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; { конец быстрой сортировки }

    Следует отметить, что потребовалось изменить только определение типа данного "DataItem" для того, чтобы настроить алгоритм быстрой сортировки на упорядочивание символьных строк. Это оказывается возможным благодаря превосходной работе, проделанной фирмой Borland по обеспечению использования в Паскале данных типа символьных строк. На стандартном Паскале запись алгоритма сортировки символьных строк была бы значительно длинее.
    Следует учитывать, что операции сравнения символьных строк выполняются больше времени, чем операции сравнения символов, так как в первом случае каждый раз делается проверка нескольких элементов.

Сортировка записей

    По-видимому в большинстве прикладных программ, где используется сортировка, требуется сортировать группы данных. Хорошим примером этого является список почтовых корреспонденций, поскольку в этом случае фамилия, улица, город, страна и почтовый индекс составляют связанную группу данных. При сортировке таких групп данных используется ключ сортировки в операциях сравнения, но в операциях обмена участвует вся запись целиком. Для того, чтобы лучше понять этот процесс сначала создадим запись, которая будет содержать необходимую информацию. Если в качестве примера использовать почтовый адрес, то запись может иметь следующий вид:

type
  address = record
    name:   string[30];
    street: string[40];
    city:   string[20];
    state:  string[2];
    zip:    string[9];
  end;

    После описания адреса необходимо изменить следующим образом определение данного "DataItem":


    DataItem = address;


    После выполнения этих изменений нужно скорректировать блок сравнений в алгоритме быстрой сортировки, используя то поле, которое применяется в качестве ключа сортировки. В приводимой ниже версии быстрой сортировки в качестве ключа используется поле фамилии "name". Это означает, что список почтовых корреспонденций сортируется в алфавитном порядке фамилий.

{ быстрая сортировка записей с почтовым адресом }
procedure QsRecord(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].name < x.name do i := i+1;
          while x.name < it[j].name do j := j-1;
          if i<=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; {конец быстрой сортировки записей}

Сортировка дисковых файлов

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

Сортировка дисковых файлов произвольного доступа

    Дисковые файлы с произвольным доступом, которые используются в большинстве баз данных на микро-ЭВМ, обладают двумя основными преимуществами над последовательными дисковыми файлами. Во-первых, их легко поддерживать. Обновление информации может производиться без копирования всего списка. Во-вторых, их можно рассматривать как большие массивы, расположенные на диске, что в значительной мере упрощает сортировку.
    Последнее преимущество позволяет использовать алгоритм быстрой сортировки с некоторыми его модификациями для поиска различных записей на диске аналогично индексированию массива. В отличие от сортировки последовательного файла при сортировке дискового файла с произвольным доступом не требуется иметь на диске пространство одновременно как для отсортированного, так и для неотсортированного массива.
    В каждом конкретном случае алгоритм сортировки должен модифицироваться в соответствии со структурой сортируемых данных и выбранным ключом сортировки. Однако основные принципы сортировки дисковых файлов произвольного доступа можно понять, изучая программу сортировки записей с адресами почтовых корреспонденций /запись "address" определялась раньше/. В приводимом ниже примере, предполагается, что число элементов фиксированно и равно восьмидесяти. На практике счетчик записей должен поддерживаться динамически.

{ пример программы сортировки списка почтовых адресов }
programm MlistSort;
  type
    address = record
      name: string[30];
      street: string[40];
      sity: string[20];
      state: string[2];
      zip: string[9];
    end;
    str80 = string[80];
    DataItem = addres;
    DataArray = array [1..80] of DataItem
    recfil = file of DataItem

  var
    test: DataItem;
    t, t2:integer;
    testfile: recfil;

                 { найти запись в файле }
function Find(var fp:recfil; i:integer): str80
  var
    t:address;
begin
  i := i-1;
  Seek(fp, i)
  Read(fp, t)
  Find := t.name;
end;

procedure QsRand(var var fp:recfil; count:integer)
  procedure Qs(l, r:integer)
    var
      i, j, s:integer ;
      x, y, z:DataItem;
begin
  i := l; j := r;
  s := (l+r) div 2;
  Seek(fp,s-1); { получить запись }
  Read(fp,x);
  repeat
    while Find(fp, i) < x.name do i := i+1;
    while x.name < Find(fp, j) do j := j-1;
    if i<=j then
      begin
        Seek(fp,i-1);  Read(fp,y);
        Seek(fp,j-1);  Read(fp,z);
        Seek(fp,j-1);  Write(fp,y);
        Seek(fp,i-1);  Write(fp,z);
        i := i+1; j := j-1;
      end;
    until i>y;
    if l<j then qs(l, j)
    if l<r then qs(i, r)
end;
begin
  qs(1,count);
end; { конец быстрой сортировки файла произвольного доступа }
begin
  Assign(testfile, 'rectest.dat');
  Reset(testfile);
  t := 1;
  while not EOF(testfile) do begin
    Read(testfile,test); { подсчет числа записей в файле}
    t := t+1;
  end;
  t := t-1;

  QsRand(testfile,t)
end.

    Функция Find используется для того, чтобы оставить в основном неизменным программу быстрой сортировки. Результатом этой функции является символьная строка "name" из записи, расположенной на диске. Необходимо постоянно вычитать единицу из аргументов функций Seek и Find, так как записи дискового файла нумеруются начиная с нуля, а массивы нумеруются с единицы.

Сортировка последовательных файлов

    В отличие от файлов с прямым доступом последовательные файлы обычно не используют записи фиксированной длины и могут размещаться на устройствах памяти, на которых трудно организовать прямой доступ. Поэтому последовательные файлы на дисках используются в тех случаях, когда для решения конкретной задачи удобнее использовать записи переменной длины или когда устройство памяти ориентировано на последовательный доступ. Например, большинство текстовых файлов имеют последовательную организацию.
    Несмотря на то, что такой подход к сортировке, когда дисковый файл рассматривается как массив, имеет ряд преимуществ, его нельзя применить к последовательным файлам - быстрый доступ к произвольному элементу в этом случае невозможен. Например, нельзя быстро прочитать произвольную запись из последовательного файла, расположенного на магнитной ленте. По этой причине возникают трудности по применению любого ранее описанного метода сортировки массивов к сортировке последовательных файлов.
    Имеется два подхода к сортировке последовательных файлов. Первый подход предусматривает считывание информации в оперативную память и сортировку при помощи одного из стандартных методов сортировки массивов. Несмотря на то, что при таком подходе сортировка будет выполняться быстро, размеры оперативной памяти накладывают сильное ограничение на размер сортируемого файла.
    При использовании второго подхода, получившего название сортировки слиянием, весь файл делиться на две равные части. В процессе сортировки из каждого файла считывается по одному элементу, эта пара элементов упорядочивается и делается запись элементов в третий файл, расположенный на диске. Новый файл затем снова делится на два файла и упорядоченные пары элементов объединяются в упорядоченные группы элементов по четыре элемента в каждой. Затем полученный файл снова разделяется на два файла и вся процедура повторяется до тех пор, пока файл не будет отсортирован. Эту сортировку-слияние называют трехленточным слиянием, поскольку в этом случае одновременно требуется иметь три файла /т.е. три накопителя на магнитной ленте, если файл располагается на ленте/.
    Для того, чтобы лучше понять работу сортировки-слияние, рассмотрим следующую последовательность числе:
    1 4 3 8 6 7 2 5.
    В результате разбиения получаются следующие последовательности:
    1 4 3 8
    6 7 2 5.
    Затем производится слияние пар элементов:
    1 6 - 4 7 - 2 3 - 5 8.
    Новое разбиение дает следующие последовательности:
    1 6 - 4 7
    2 3 - 5 8.
    Результат следующего слияния:
    1 2 3 6 - 4 5 7 8.
    Последнее разбиение будет следующим:
    1 2 3 6
    4 5 7 8.
    И в результате получаем:
    1 2 3 4 5 6 7 8.
    При сортировке методом слияния, как возможно вы уже заметили, требуется выполнить log₂n операций доступа к каждому файлу, где "n" является числом сортируемых элементов.
    Ниже дается простая версия алгоритма сортировки методом слияния. Предполагается, что размер входного файла в два раза превышает объем содержащейся в нем информации. Поэтому в действтительности требуется иметь лишь один файл. Однако, по-существу, метод сортировки слиянием не изменяется. В этом примере данное "filtype" определяется как файл типа "DataItem". Функция "Find" используется для считывания конкретной записи из файла.

{ функция  "Find" используется в сортировке методом слияния для считывания из файла 
конкретной записи.}
function Find(var fp:filtype; i:integer):DataItem;
var
  t:DataItem;
begin
  Seek(fp, i-1);
  Read(fp, t);
  Find := t;
end;

procedure Mergesort(var fp: filetype; count:integer);
  var
    i, j, k, l, t, h, m, p, q, r: integer;
    ch1, ch2:DataItem
    up: Boolean;
begin
  up := TRUE;
  p := 1;
  repeat
    h := 1; m := count;
    if up then
    begin
      i := 1; j := count; k := count+1; l := 2*count;
    end else
    begin
      k := 1; l := count; i := count+1; j := 2*count;
    end;
    repeat
      if m>=p then q := p else q := m;
      m := m-q;
      if m>=p then r := p else r := m;
      m := m-r;
      while (q<>0) and (r<>0) do
      begin
        if Find(fp,i) < Find(fp,j) then
        begin
          Seek(fp, i-1); Read(fp,ch2);
          Seek(fp, k-1); Write(fp,ch2);
          k := k+h; i := i+1; q := q-1;
        end else
        begin
          Seek(fp, j-1); Read(fp,ch2);
          Seek(fp, k-1); Write(fp,ch2);
          k := k+h; j := j-1; r := r-1;
        end;
      end;
      while r<>0 do
      begin
        Seek(fp, j-1); Read(fp,ch2);
        Seek(fp, k-1); Write(fp,ch2);
        k := k+h; j := j-1; r := r-1;
      end;
      while q<>0 do
      begin
        Seek(fp, i-1); Read(fp,ch2);
        Seek(fp, k-1); Write(fp,ch2);
        k := k+h; i := i+1; q := q-1;
      end;
        h := -1; t := k;
        k := l;
        l := t;
    until m = 0:
    up := not up;
    p := p*2;
  until  p >= count;
  if not up then
    for i := 1 to count do
    begin
      Seek(fp, i-1+count); Read(fp,ch2);
      Seek(fp, i-1); Write(fp,ch2);
    end;
end; { кoнец сортировки методом слияния }

ПОИСК

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

МЕТОДЫ ПОИСКА

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

Последовательный поиск

    Алгоритм последовательного поиска имеет очень простой вид. Ниже представлена функция, которая выполняет поиск в символьном массиве заданной длины элемента с заданным значением ключа:

function SeqSearch(item: DataArray; count:integer; key:DataItem):integer;
var
  t:integer;
begin
  t:=1;
  while (key<>item[t]) and (t<=count) t:=t+1;
  if t>count then SeqSearch:=0
  else SeqSearch:=t;
end; { конец последовательного поиска }

    Эта функция выдает либо значение индекса для найденного элемента массива, либо нулевое значение, когда требуемый элемент не найден.
    При прямом последовательном поиске в среднем проверяются n/2 элементов. В лучшем случае будет проверяться только один элемент, а в худшем случае будут проверятся n элементов. Если информация размещается на диске, то поиск может быть очень долгим. Однако, если данные не отсортированы, то последовательный поиск является единственным возможным в данном случае методом поиска.

Двоичный поиск

    Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки.
    Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел 1 2 3 4 5. Здесь средним элементом является 3. Это значение меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел 4 5. На следующем шаге нужный элемент будет найден. При двоичном поиске число сравнений в худшем случае равно log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.
    Приводимую ниже функцию, которая реализует двоичный поиск для символьных массивов, можно использовать для поиска любой произвольной структуры данных, изменив блок сравнения и определение типа данного "DataItem".

function BSearch (item: DataArray; count:integer; key:DataItem):integer;
var
  low, high, mid: integer;
  found:boolean;
begin
  low:=1; high:=count;
  found:=false;         { не найден }
  while (low<=high) and (not found) do
  begin
    mid:=(low+high) div 2;
    if key<item[mid] then high:=mid-1
    else if key>item[mid] then low:=mid+1
    else found:=true;  { найден }
  end;
  if found then BSearch:=mid
  else BSearch:=0;  { не найден }
end; { конец поиска }