usch1_5

В данной теме мы рассмотрим некоторые методы сортировки массивов порядка n². Проведет анализ производительности алгоритмов. Покажем, как путем улучшений алгоритма можно добиться некоторого выигрыша в эффективности.
Сортировка

Сортировка - это процесс перегруппировки заданного множества объектов в некотором определенном порядке. Рассмотрим некоторые методы сортировки массивов.

Основное условие: выбранный метод должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте (в одном и том же массиве). Сначала разберем простые методы, их называют прямыми, где требуется порядка n² сравнений.

Методы сортировки "на том же месте" можно разбить на три основные категории:

- сортировки с помощью включения;
- сортировки с помощью выделения;
- сортировки с помощью обменов.
Все методы будем рассматривать на элементах массива
a:array[1..n] of integer.

Сортировка с помощью прямого включения.

Алгоритм: элементы массива мысленно делятся на уже "готовую" и исходную последовательности. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

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

Процесс просеивания может закончиться при выполнении одного из двух условий:

- найден элемент a_j с ключом, меньшим чем ключ у х;
- достигнут левый конец готовой последовательности.

Повторяющейся процесс с двумя условиями окончания позволяет воспользоваться приемом "барьера", поставив барьер a₀ со значением х.

for i:=2 to 10 do
   begin
    x:=a[i];a[0]:=x;j:=i;
     while x<a[j-1] do
      begin
       a[j]:=a[j-1];j:=j-1;
      end;
    a[j]:=x;
   end;

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

For i:=2 to 10 do
begin
    c:=a[i]; l:=1;r:=i;
    while l<r do
       begin
          m:=(l+r) div 2;
          if a[m]<=c then l:=m+1 else r:=m;
       end;
    for j:=i downto r+1 do
      a[j]:=a[j-1];
    a[r]:=c;
end;

Анализ методов прямого и двоичного включения.

Число сравнений (С) при i-м просеивании самое большее равно i-1, самое меньшее - 1. Число присваиваний элементов (М) равно C_i+2 (включая барьер). Поэтому общее число сравнений и число присваиваний:

Cmin=n-1 Mmin=3(n-1)
Cmax=(n²+n-4)/4 Mmax=(n²+3n-4)/2

Для двоичного включения: место включения обнаружено, если l=r. Таким образом, интервал должен быть единичной длины. Число сравнений фактически не зависит от начального порядка элементов. Однако, из-за того, что при делении происходит отбрасывание дробной части, истинное число сравнений может оказаться на единицу больше. В нижней части последовательности место включения отыскивается в среднем несколько быстрее, чем в верхней части, поэтому предпочтительна ситуация, в которой элементы немного упорядочены. Улучшения касаются лишь числа сравнения : C=n(log(n)-log(e)╠0.5). А число передвижений М продолжает оставаться порядка n². Сортировка с помощью прямого выбора.

Алгоритм:

- выбирается элемент с наименьшим ключом;
- он меняется местами с первым элементом a1;
- затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.

for i:=1 to n-1 do
    begin
      x:=a[i];k:=i;
        for j:=i+1 to n do
          if a[j]<x then begin k:=j; x:=a[k] end;
      a[k]:=a[i];a[i]:=x;
    end;

Анализ прямого выбора. Число сравнений С не зависит от начального порядка элементов. С=(n²-n)/2 Число перестановок минимально в случае изначально упорядоченных элементов и максимально, если первоначально они располагались в обратном порядке. Mmin=3(n-1) Mmax=n²/4+3(n-1) Сортировка с помощью прямого обмена.

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

for i:=2 to n do
    for j:=n downto i do
      if a[j-1]>a[j] then
         begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; end;

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

w:=true;
while w do
    begin
      w:=false;
      for j:=1 to n-1 do
        if a[j]>a[j+1] then begin w:=true; x:=a[j+1];
                            a[j+1]:=a[j]; a[j]:=x; end;
    end;

Улучшая "пузырьковую" сортировку (будем чередовать направление последовательных просмотров), получаем новый алгоритм - "шейкерную" сортировку.

   l:=2;r:=n;
   repeat
     for j:=r downto l do
        if a[j-1]>a[j] then begin x:=a[j-1]; a[j-1]:=a[j];
                                 a[j]:=x; k:=j;end;
     l:=k+1;
     for j:=l to r do
        if a[j-1]>a[j] then begin x:=a[j-1]; a[j-1]:=a[j];
                                 a[j]:=x; k:=j;end;
     r:=k-1;
   until l>r;

Анализ пузырьковой и шейкерной сортировок.

Число сравнений в пузырьковом алгоритме С=(n²-n)/2, а минимальное и максимальное число перемещений элементов (присваиваний) равно соответственно Mmin=0 и Mmax=3(n²-n)/4

Анализ же шейкерной сортировки довольно сложен. Минимальное число сравнений С=n-1. Обратим внимание на то, что усовершенствования не влияют на число перемещений, они лишь сокращают число излишних двойных проверок.

Обмен местами двух элементов - чаще всего более дорогостоящая операция, чем сравнение, поэтому улучшения дают не большой выигрыш, как мы ожидали.
Все строгие приемы сортировки фактически передвигают каждый элемент на всяком элементарном шаге на одну позицию. Поэтому они требуют порядка n² таких шагов. Следовательно, в основу улучшений должен быть положен принцип перемещения на каждом такте элементов на большие расстояния.
В следующей теме мы рассмотрим некоторые улучшенные методы сортировки, требующие шагов порядка n·log(n).

Литература:
1. Н.Вирт. Алгоритмы и структуры данных.
2. Д.Кнут. Искусство программирования для ЭВМ.
Упражнения:
1. Дан массив a:array [1..n] of integer. Отсортировать его различными методами и сравнить затраченное время.
2. Таблица выигрышей денежной лотереи представлена массивом выигравших билетов и соответствующим массивом выигрышей в рублях. Определить суммарный выигрыш, выпавший на билеты с номерами b(1),b(2),...,b(m) (номера не упорядочены).
3. Дан массив некоторых числовых данных. Удалить из него все повторяющиеся элементы, отсортировав его одним из методом.
4. Дан текст. Составить таблицу частот повторений различных символов этого текста.