IPB

> Лекция №4.2: Сортировки массивов
Навигация
Главная
Скачать Turbo Pascal
Скачать справочник
Turbo Pascal Онлайн
Форум | Группа ВК | Чат
Лекции
Алфавитный указатель
Содержание справки
Язык Turbo Pascal
Стандартные модули
Функции и процедуры
Директивы компилятора
Примеры программ
Меню Turbo Pascal
Ада-2020. Современный Паскаль
Адское программирование
Статьи по Ада-2020
Отзывы и идеи
Об этом сайте
Чат

Войти

Форум
Загрузка...
 

страницы: 1 2

Содержание

Улучшенные сортировки

В отличие от простых сортировок, имеющих сложность ~N2, к улучшенным сортировкам относятся алгоритмы с общей сложностью ~N*logN.

Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N < 100) эффективность быстрых сортировок не столь очевидна: выигрыш становится заметным только при больших N. Следовательно, если необходимо отсортировать маленький набор данных, то выгоднее взять одну из простых сортировок.

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

Эта сортировка1 базируется на уже известном нам алгоритме простых вставок ПрВст. Смысл её состоит в раздельной сортировке методом ПрВст нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок: для того, чтобы освободить «правильное» место для очередного элемента, приходится уже сдвигать меньшее количество элементов.

Алгоритм УлШелл

На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:

  1. вычленить все подпоследовательности, расстояние между элементами которых составляет kt;
  2. каждую из этих подпоследовательностей отсортировать методом ПрВст.

Нахождение убывающей последовательности расстояний kt, kt-1..., k1 составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить её обязательные свойства:

  • k1 = 1;
  • для всех t kt > kt-1;
  • желательно также, чтобы все kt не были кратными друг другу (для того, чтобы не повторялась обработка ранее отсортированных элементов).

Дональд Кнут предлагает две «хорошие» последовательности расстояний:

1, 4, 13, 40, 121, _ (kt  = 1+3kt-1)
1, 3, 7, 15, 31, _   (kt  = 1+2kt-1 = 2t-1)

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

Как же определить начальное значение для t (а вместе с ним, естественно, и для kt)?

Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т. д. между её элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления kt = 2t-1.

Итак, длина нашего массива (N) должна попадать в такие границы:

kt <= N - 1 < kt+1

или, что то же самое,

2t <= N < 2t+1

Прологарифмируем эти неравенства (по основанию 2):

t <= log N < t + 1

Таким образом, стало ясно, что t можно вычислить по следующей формуле:

t = Тrunc(log N))

К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придётся вспомнить знакомое из курса средней школы правило «превращения» логарифмов:

logmx =logzx/logzm

В нашем случае m = 2, z = e. Таким образом, для начального t получаем:

t := Trunc(Ln(N) / Ln(2))

Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть — и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить ещё на 1 шаг:

t := Trunc(Ln(N) / Ln(2)) - 1

Расстояние между элементами в любой подпоследовательности вычисляется так:

k := (1 shl t) - 1;
         { k = 2t-1 }

Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k + 1)–го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.

Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:

s := N div k;

Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких «удлинённых» подпоследовательностей совпадает с длиной «хвоста» — остатка от деления N на шаг k:

P:= N mod k;

Реализация алгоритма УлШелл

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

program shell_sort;
const
  n = 18;
  a : array[1 .. n] of Integer =
    (18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1);
var ii, m, x, s, p, t, k, r, i, j : Integer;
begin
  t := Trunc(Ln(n) / Ln(2));
 repeat
    t := t - 1;
    k := (1 shl t) - 1;
    p := n mod k;
    s := n div k;
   if p = 0 then
      p := k
   else
      s := s + 1;

   WriteLn(k, '-сортировка');
   for i := 1 to k do {берём и длинные, и короткие подпоследовательности}
   begin
     if i = p + 1 then
        s := s - 1; {для коротких — уменьшаем длину}
     for j := 1 to s - 1 do {метод ПрВст с шагом k}
       if a[i + (j - 1) * k] > a[i + j * k] then
       begin
          x := a[i + j * k];
          m := i + (j - 1) * k;
         while (m > 0) and (a[m] > x) do
         begin
            a[m + k] := a[m];
            m := m - k;
         end;
          a[m + k] := x;
       end;
     for ii := 1 to n do
       Write(a[ii], ' ');
     WriteLn;
   end;
 until k = 1;
end.

Результат работы

7–сортировки

4 17  16  15 14 13 12 11 10 9 8 7  6  5  18 3  2  1 
4 3   16  15 14 13 12 11 10 9 8 7  6  5  18 17 2  1 
4 3   2   15 14 13 12 11 10 9 8 7  6  5  18 17 16 1 
4 3   2   1  14 13 12 11 10 9 8 7  6  5  18 17 16 15 
4 3   2   1  7  13 12 11 10 9 8 14 6  5  18 17 16 15 
4 3   2   1  7  6  12 11 10 9 8 14 13 5  18 17 16 15  
4 3   2   1  7  6  5  11 10 9 8 14 13 12 18 17 16 15

3–сортировки

1 3 2 4 7 6 5 11 10 9 8  14 13 12 18 17 16 15  
1 3 2 4 7 6 5 8  10 9 11 14 13 12 18 17 16 15  
1 3 2 4 7 6 5 8  10 9 11 14 13 12 15 17 16 18

1–сортировка

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Эффективность алгоритма УлШелл

Довольно сложными методами, в изложение которых мы не будем углубляться, показано, что алгоритм Шелла имеет сложность ~N3/2. И хотя это несколько хуже, чем N*logN, всё–таки эта сортировка относится к улучшенным.

Пример сравнения сортировок: Вновь возьмём последовательность, для сортировки которой методом простых вставок ПрВст потребовалось 15 сдвигов (25 пересылок и 20 сравнений):

5  3  4  3  6  2  1

Теперь применим к ней метод Шелла.

Здесь N = 7, поэтому:

t = Тrunc(log 7) = 2
k = 22 - 1 = 3        {начнём с 3–сортировки}
p = 7 mod 3 = 1       {кол–во длинных подпоследовательностей}
s = (7 div 3) + 1 = 3 {длина длинной подпоследовательности}

  1. 3–сортировки:

    5 3 1 -> 1 3 5 {3 сдвига: 7 пересылок, 5 сравнений} 3 6 -> 3 6 {0 сдвигов: 0 пересылок, 1 сравнение} 4 2 -> 2 4 {1 сдвиг: 3 пересылки, 2 сравнения}

    Всего 4 сдвига: 10 пересылок, 8 сравнений Итог 3-сортировок: 1 3 2 3 6 4 5
  2. 1-сортировка:

            Состояние массива  Сдвиги  Сравнения  Пересылки данных
       
    0 шаг:        1323645       
    1 шаг:        1323645       0         1    0
    2 шаг:        1323645       1        1+1   1+2
    3 шаг:        1233645       0         1    0
    4 шаг:        1233645       0         1    0
    5 шаг:        1233645       1        1+1   1+2
    6 шаг:        1233465       1        1+1   1+2
    результат:    1233456       3         9    9

При сортировке методом Шелла в сумме получилось 7 сдвигов (19 пересылок и 17 сравнений). Выигрыш по сравнению с методом простых вставок составляет 53% (24% экономится на пересылках и 15% — на сравнениях)2. Если вместо метода простых вставок ПрВст использовать метод бинарных вставок БинВст, то выигрыш по количеству сравнений будет ощутимее.

Кроме того, не нужно забывать, что в нашем примере последовательность очень коротка: N = 7. Для больших N (скажем, N = 10000) преимущество метода Шелла станет ещё заметнее.

Пирамидальная сортировка

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.

Р. Флойд предложил перестроить линейный массив в пирамиду — своеобразное бинарное дерево, — а затем искать минимум только среди тех элементов, которые находятся непосредственно «под» текущим вставляемым.

Просеивание

Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент «опирается» на два меньших. Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц: на нескольких грохотах3 последовательно задерживаются сначала крупные, а затем всё более мелкие частицы.

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:

a[1]
a[2]a[3]
a[4]a[5]a[6]a[7]
a[8]a[9]a[10]a[11]a[12]

Видно, что любой элемент a[i] (1 <= i <= N div 2) «опирается» на элементы a[2 * i] и a[2 * i + 1]. И в каждой такой тройке максимальный элемент должен находиться «сверху». Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.

Начнём процесс просеивания «снизу». Половина элементов (с ((N div 2) + 1)–го по N–й) являются основанием пирамиды, их просеивать не нужно. А для всех остальных элементов (двигаясь от конца массива к началу) мы будем проверять тройки a[i], a[2 * i] и a[2 * i + 1] и перемещать максимум «наверх» — в элемент a[i].

При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо «навести порядок» — и так до самого «низа» пирамиды:

for i := (N div 2) downto 1 do
begin
  j := i;
 while j <= (N div 2) do
 begin
    k := 2 * j;
   if (k + 1 <= N) and (a[k] < a[k + 1]) then
      k := k + 1;
   if a[k] > a[j] then
   begin
      x := a[j];
      a[j] := a[k];
      a[k] := x;
      j := k
   end
   else
     Break
 end
end;

Пример результата просеивания

Возьмем массив [1, 7, 5, 4, 9, 8, 12, 11, 2, 10, 3, 6] (N = 12).

Его исходное состояние таково (серым цветом выделено «основание» пирамиды, не требующее просеивания):

1
75
49812
1121036

После первых трёх просеиваний (a[6], a[5], a[4]) получим такую картину (здесь и далее серым цветом выделяем участников просеивания):

1
75
49812
1121036
1
75
1110 9812
1129 1036
1
75
11 410812
4 112936

Просеивание двух следующих элементов (a[3] и a[2]) тоже не вызовет вопросов — для каждого из них будет достаточно только одного шага:

1
712 5
111085 12
42936
1
11 75
7 1110812
42936

А вот для просеивания последнего элемента (a[1]) понадобится целых три шага:

12 1
111 12
7 11085
42936
12
118 1
7101 85
42936
12
118
7106 15
42931 6

Итак, мы превратили исходный массив в пирамиду: в любой тройке a[i], a[2 * i] и a[2 * i + 1] максимум находится «сверху».

Алгоритм УлПир

Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:

0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).

1-й шаг: Для N - 1 элементов, начиная с последнего, производить следующие действия:

  • поменять местами очередной «рабочий» элемент с первым;
  • просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i–го по N–й).

Реализация алгоритма УлПир

Часть программы, реализующую нулевой шаг алгоритма УлПир, мы привели в пункте «Просеивание», поэтому здесь ограничимся только реализацией основного шага 1:

for i := N downto 2 do
begin
  x := a[1];
  a[1] := a[i];
  a[i] := x;
  j := 1;
 while j <= ((i - 1) div 2) do
 begin
    k := 2 * j;
   if (k + 1 <= i - 1) and (a[k] < a[k + 1]) then
      k := k + 1;
   if a[k] > a[j] then
   begin
      x := a[j];
      a[j] := a[k];
      a[k] := x;
      j := k
   end
   else
     Break
 end
end;

Пример. Продолжим сортировку массива, для которого мы уже построили пирамиду: [12, 11, 8, 7, 10, 6, 5, 4, 2, 9, 3, 1]. С целью экономии места мы не будем далее прорисовывать структуру пирамиды, оставляя это несложное упражнение читателям. Подчёркивание будет отмечать элементы, участвовавшие в просеивании, а полужирный шрифт — элементы, исключённые из дальнейшей обработки:

1)  Меняем местами a[1] и a[12]:  [1, 11, 8, 7, 10, 6, 5, 4, 2, 9, 3, 12];
2)  Просеиваем элемент a[1], получаем: [11, 10, 8, 7, 9, 6, 5, 4, 2, 1, 3, 12];
3)  Меняем местами a[1] и a[11]:  [3, 10, 8, 7, 9, 6, 5, 4, 2, 1, 11, 12];
4)  Просеиваем a[1], получаем:   [10, 9, 8, 7, 3, 6, 5, 4, 2, 1, 11, 12];
5)  Меняем местами a[1] и a[10]:  [1, 9, 8, 7, 3, 6, 5, 4, 2, 10, 11, 12];
6)  Просеиваем элемент a[1]:   [9, 7, 8, 4, 3, 6, 5, 1, 2, 10, 11, 12];
7)  Меняем местами a[1] и a[9]:  [2, 7, 8, 4, 3, 6, 5, 1, 9, 10, 11, 12];
8)  Просеиваем элемент a[1]:   [8, 7, 6, 4, 3, 2, 5, 1, 9, 10, 11, 12];
9)  Меняем местами a[1] и a[8]: [1, 7, 6, 4, 3, 2, 5, 8, 9, 10, 11, 12];
10) Просеиваем элемент a[1]:   [7, 4, 6, 1, 3, 2, 5, 8, 9, 10, 11, 12];
11) Меняем местами a[1] и a[7]:  [5, 4, 6, 1, 3, 2, 7, 8, 9, 10, 11, 12];
12) Просеиваем элемент a[1]:   [6, 4, 5, 1, 3, 2, 7, 8, 9, 10, 11, 12];
13) Меняем местами a[1] и a[6]:  [2, 4, 5, 1, 3, 6, 7, 8, 9, 10, 11, 12];
14) Просеиваем элемент a[1]:   [5, 4, 2, 1, 3, 6, 7, 8, 9, 10, 11, 12];
15) Меняем местами a[1] и a[5]:  [3, 4, 2, 1, 5, 6, 7, 8, 9, 10, 11, 12];
16) Просеиваем элемент a[1]:   [4, 3, 2, 1, 5, 6, 7, 8, 9, 10, 11, 12];
17) Меняем местами a[1] и a[4]:  [1, 3, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12];
18) Просеиваем элемент a[1]:   [3, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12];
19) Меняем местами a[1] и a[3]:  [2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
20) Просеивать уже ничего не нужно;
21) Меняем местами a[1] и a[2]:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
22) Просеивать ничего не нужно, сортировка закончена.

Эффективность алгоритма УлПир

Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N < 20) выгода от её применения может быть не слишком очевидна.

В среднем этот алгоритм имеет сложность, пропорциональную N*log N.

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

Существует ещё один метод улучшенной сортировки, имеющий среднюю сложность порядка N*log N: так называемая Быстрая сортировка4. Этот алгоритм является усовершенствованием обменных сортировок. Его реализация наиболее удобна в рекурсивном варианте, поэтому мы вернёмся к её изучению после того, как познакомимся с рекурсивными процедурами и функциями (см. лекцию 9).

страницы: 1 2

Примечания

  1. ^ Д. Л. Шелл назвал её «сортировкой вставками с убывающим шагом».
  2. ^ Для других входных данных это число может быть значительно меньше или же ещё больше
  3. ^ Грохот — техническое «сито».
  4. ^ В оригинале QuickSort.
 
 К началу страницы 
 

Код для вставки: :: :: :: ГОСТ ::
Поделиться: //
 



-
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"