Программирование на языке Pascal




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


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

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

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

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

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

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

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

1, 4, 13, 40, 121, _ (kt = 1+3*kt-1) 1, 3, 7, 15, 31, _ (kt = 1+2*kt-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




Содержание  Назад  Вперед