Сортировка информационных массивов методом Шелла.

Цель работы: изучение процесса сортировки информационных машинных массивов методом Шелла.

Методические указания.

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

Для алгоритма сортировки, который каждый раз перемещает запись только на одну позицию (как в методе простых вставок), среднее время работы будет в лучшем случае пропорционально 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

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

Порядок выполнения работы.

1. Ознакомится с описанием лабораторной работы №4. Изучить алгоритм сортировки методом Шелла.

2. Изучить блок-схему данной сортировки.

3. Написать последовательность сортировки заданного массива методом Шелла в виде таблицы с указанием номеров просмотров (см. пример сортировки).

4. Произвести подсчет числа сравнений и количества пересылок, полученных при сортировке вашего варианта массива методом Шелла. Сравните полученные данные при сортировке этим методом с данными, полученными в лабораторных работах №1-3 проанализируйте все рассмотренные в лабораторных работах методы сортировок по эффективности на основе ваших данных.

5. Провести сортировку заданного массива на ЭВМ.

Содержание отчета.

1. Краткое изложение рассматриваемого метода сортировки, целей и задач лабораторной работы.

2. Блок-схема алгоритма рассмотренной сортировки.

3. Таблица последовательности сортировки заданного массива чисел.

4. Анализ эффективности алгоритма Шелла. Сравнительный анализ с теоретическими данными и с ранее рассмотренными методами сортировок.

5.  Результаты сортировки на ЭВМ (распечатка с комментариями).

Контрольные вопросы.

1. Является ли алгоритм Шелла алгоритмом устойчивой сортировки? Рассмотрите это на примере.

2. Что такое h-сортировка?

3. Какие имеются требования к выбору последовательности шагов при сортировке по методу Шелла?

4. Какова эффективность алгоритма Шелла?

5. В чем заключается основная идея метода Шелла?

Лабораторная работа № 5.