Алгоритм 3. Сортировка шейкером

Алгоритм 3. Сортировка Шейкером.

Когда данные сортируются не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N — количество элементов. Реализация данного алгоритма выглядит так:

Program ShakerSort;
Var A       : array[1..1000] of integer;
    N,i,j,p    : integer;       
    Min, Max : integer;
Begin
 {Определение размера массива A — N) и его заполнение}
 …
 {сортировка данных}
 for i:=1 to n div 2 do
  begin
   if A[i]>A[i+1] then
   begin
    Min:=i+1;
    Max:=i;
   end
   else
   begin
    Min:=i;
    Max:=i+1;
   end;
   for j:=i+2 to n-i+1 do
   if A[j]>A[Max] then
    Max:=j
   else
   if A[j]<A[Min] then
    Min:=j; 
   {Обмен элементов}
    P:=A[i];
    A[i]:=A[min];
    A[min]:=P;
    if max=i then
    max:=min;
    P:=A[N-i+1];
    A[N-i+1]:=A[max];
    A[max]:=P;
  end;
 {Вывод отсортированного массива A}
 …
End.

Рассмотрев эти методы, сделаем определенные выводы. Их объединяет не только то, что они сортируют данные, но также и время их работы. В каждом из алгоритмов присутствуют вложенные циклы, время выполнения которых зависит от размера входных данных. Значит, общее время выполнения программ есть O(n2) (константа, умноженная на n2). Следует отметить, что первые два алгоритма используют также O(n2) перестановок, в то время как третий использует их O(n). Отсюда следует, что метод Шейкера является более выгодным для сортировки данных на внешних носителях информации.

Если вы думаете, что бравые «алгоритмщики» остановились на достигнутом, то вы ошибаетесь. Видите ли, временная оценка O(n2) показалась им слишком громоздкой, и они, жадины такие, решили еще потратить свое время, чтобы впоследствии сэкономить наше. Итак, давайте теперь рассмотрим более быстрые алгоритмы.