Методические указания. В данной лабораторной работе, последней из цикла, на примере сортировки Шелла вы получите представление о том

В данной лабораторной работе, последней из цикла, на примере сортировки Шелла вы получите представление о том, как можно на базе основного метода значительно усовершенствовать способ сортировки.

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

Такой метод впервые был предложен Л.Шеллом в 1959г. Метод Шелла часто называют “сортировкой с убывающим шагом”. Метод Шелла заключается в том, что сортируемый массив разбивается на группы, а затем каждая группа сортируется методом простых вставок. Процесс разбиения массива на группы уже большего размера и сортировка элементов в них, будут продолжаться до тех пор, пока все элементы не будут объединены в одну группу.

Алгоритм метода Шелла можно определить следующим образом. Для управления процессом сортировки используется вспомогательная последовательность убывающих шагов h_e, e = t, t-1, t-2, …, 1; причем последний шаг h₁ всегда равен единице h₁=1. Весь процесс сортировки разбивается на отдельные просмотры массива.

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

при

При 2-м просмотре методом простых вставок сортируются элементы, отстоящие друг от друга на h_t-1 позиций. В результате получаем упорядоченные подгруппы элементов, в каждой из которых ключи упорядочены, т.е. удовлетворяют соотношению при и так далее.

При последнем просмотре устанавливается шаг h₁ и производится сортировка массива простыми вставками, которая ничем не отличается от сортировки, рассмотренной в лабораторной работе №3.

Если назвать каждый просмотр “h – сортировкой”, то сортировка методом Шелла состоит из h_t сортировки, за которой следует h_t-1 сортировка, …, за которой следует h₁ сортировка. Подфайл, в котором K_i £ K_i+h при 1 £ i £ N-h, будем называть h-упорядоченным.

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

Последовательность шагов h_e может быть любой, в которой последний шаг h₁=1. От выбранной последовательности шагов зависит время работы алгоритма.

Для примеров будем пользоваться последовательностью: 8, 4, 2, 1. Лучшие результаты получаются при шагах: 7, 5, 3, 1. Если шаги выбирать из соотношения

при 1 £ e £ t = [log₂N] (2.11)

то максимальное время работы алгоритма Шелла (оценка) есть N^3/2.

Преимущества алгоритма Шелла проявляются при больших массивах.

Число сравнений и перемещений снижается примерно до C = N^{1, 3} для тех значений N, которые встречаются на практике; при Nà ¥ это число можно сократить до порядка C = N(log₂N)².

Приведем пример сортировки массива из 8 чисел (h_e=4, 2, 1):

Исходный массив: 7 3 5 1 2 8 4 6

1-й просмотр (4-сортировка)

h_t = h₄ – разбиение 7 3 5 1 2 8 4 6

7: 2

3: 8

5: 4

1: 6

после 1-го просмотра: 2 3 4 1 7 8 5 6

2-й просмотр (2-сортировка)

h_t-1 = h₂ – разбиение 2 3 4 1 7 8 5 6

2: 4

3: 1

2: 4: 7

1 3: 8

2 4 7: 5

1 3 8: 6

после 2-го просмотра: 2 1 4 3 5 6 7 8

3-й просмотр (1-сортировка)

h₁ – разбиение 2 1 4 3 5 6 7 8

2: 1

1 2: 4

1 2 4: 3

1 2 3 4: 5

1 2 3 4 5: 6

1 2 3 4 5 6: 7

1 2 3 4 5 6 7: 8

Массив упорядочен: 1 2 3 4 5 6 7 8

Дугами указано разбиение элементов (ключей) на группы. Знак “: ” означает сравнение, стрелкой показана пересылка элемента.

Алгоритм Шелла довольно просто программируется, использует минимальный объем памяти и эффективен при умеренно больших N (при N£ 1000).

Блок-схема сортировки методом Шелла представлена в приложении 4.

В блок-схеме сортировки методом Шелла использованы следующие обозначения: n – размер массива; hi – шаг в i-м этапе; j – текущий номер 1-го из сравниваемых элементов (пересылаемого в рабочую ячейку); k – текущий номер 2-го из сравниваемых элементов; j₀ – номер 1-го элемента упорядочиваемой последовательности; c – номер рабочей ячейки; M – идентификатор упорядочиваемого массива.

Блок 1 формирует шаг h₁ для первого этапа процедуры. Возможные варианты внутренней структуры блока 1 описаны ниже.

Блок 2 присваивает индексам j и j₀ исходные значения, равные 1 (для упорядочения 1-ой последовательности).

Блок 3 формирует номер j 1-го из двух сравниваемых элементов, подлежащего пересылке в рабочую ячейку.

Блок 4, сравнивая j с размером массива N, проверяет, не исчерпалась ли упорядоченная последовательность.

Блок 5, сравнивая элемент массива М[j] и элемент той же последовательности M[j-h] с соседним меньшим номером, проверяет, нужно или не нужно пересылать элемент M[j] в рабочую ячейку.

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

Последующие шаги процедуры упорядочения последовательности методом вставки выполняются блоками 8-11.

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

Блок 13, сравнивая номер 1-го элемнта этой последовательности с шагом h, проверяет, не закончился ли этап, и в случае, если он не закончился, осуществляет переход к блоку 3, начинающему упорядочение следующей последовательности. Если этап закончился, то осуществляется переход к блоку 14, сравнивающему шаг только что выполненного этапа с его конечным значением, равным 1, и проверяющему тем самым, не закончилась ли вся процедура упорядочения.

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

Рассмотрим два основных варианта внутренней структуры блоков 1 и 15, формирующих первый и очередной шаги.

Вариант № 1. Шаг h₁ формируется путем сдвига вправо на один разряд двоичного кода размера массива n: h = h₁: = n ¸ 2

Последующие шаги формируются путем сдвига вправо на один разряд кода предыдущего шага с установкой младшего его разряда в 1:

1) h: = h ¸ 2;

2) h: = h V a (a = 0…01 = 1, V – операция поразрядного логического сложения кодов). Тем самым обеспечивается некратный шаг после любого из этапов процедуры.

Вариант № 2. Шаг h₁ формируется путем сдвига вправо на один разряд кода размера массива с последующей установкой в 1 группы из семи его младших разрядов:

1) h: = h ¸ 2;

2) h: = h V b

b = 0…01111111 = 2⁸ – 1;

3) сравнение h c n. Если h < n, то выход из блока 1, в противном случае – сдвиг h на один разряд вправо.

h: = h ¸ 2

и переход к новому повторению пункта 3. Пункт 3 нужен для случая формирования первого шага для массива, по размеру меньшего чем 2⁸ – 1 элемент.

Последующие шаги формируются путем сдвига на один разряд вправо кода предыдущего шага: h: = h ¸ 2

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