503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

Сортировка через 8:

503 087 154 061 612 170 765 275 653 426 512 509 908 677 897 703

Сортировка через 4:

503 087 154 061 612 170 512 275 653 426 765 509 908 677 897 703

Сортировка через 2:

Сортировка через 1:

154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

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

Метод сортировки Шелла также известен под именем Shellsort и метода сортировки с "убывающим смещением" поскольку каждый проход характеризуется смещением h, таким, что сортируются записи, каждая из которых отстоит от предыдущей на h позиций. Последовательность значений смещений 8, 4, 2, 1 не следует считать незыблемой; можно пользоваться любой последовательностью ht-i,ht-2, ..., /iQ, но последнее смещение ho должно быть равно 1. Например, в табл. 4 продемонстрирована сортировка тех же данных со смещениями 7, 5, 3, 1. Как будет показано ниже, выбор значений смещений на последовательных проходах имеет весьма существенное значение для скорости сортировки.

Алгоритм D {Сортировка Шелла). Записи Ri, Ддг перекомпоновываются в том же адресном пространстве памяти. После завершения сортировки их ключи будут упорядочены: Ki < < К. Для управления процессом сортировки используется вспомогательная последовательность смещений ht-i, ht-2, ho, где ho = I; правильно выбрав эти значения в последовательности, можно значительно сократить время сортировки. При t = 1 этот алгоритм сводится к алгоритму S.

D1. [Цикл по S.] Выполнить шаг D2 при s = t-l,t-2, ...,0, после чего завершить процедуру.

D2. [Цикл по j.] Присвоить h (г- kg и выполнить шаги от D3 до D6 при h < j < N. (Для сортировки элементов, отстоящих один от другого на h позиций, воспользуемся методом простых вставок и в результате получим Ki < Ki+h. для 1 < г < N - h. Шаги от D3 до D6, по существу, такие же, как соответственно от S2 до S5 в алгоритме S.)

D3. [Установка г. К, R.] Присвоить i (г- j - h, К <- Kj, R <r- Rj.

D4. [Сравнение К : Ki.] Если К > Ki, то перейти к шагу D6.

503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

Сортировка через 7:

Сортировка через 5:

Сортировка через 3: Сортировка через 1:

275 087 426 061 509 170 677 503 653 512 154 908 612 897 765 703

154 087 426 061 509 170 677 503 653 512 275 908 612 897 765 703

061 087 170 154 275 426 512 503 653 612 509 765 677 897 908 703 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

Ri, затем i i- i ~ h. Если

D5. [Перемещение Ri, уменьшение г.] Присвоить Ri+h г > О, то возвратиться к шагу D4.

D6. [Перемещение R на место Ri+h] Присвоить Ri+h R- I

Соответствующая программа для MIX не намного длиннее, чем наша программа для метода простых вставок. Строки 08-19 этой программы перенесены из программы S в более общий контекст алгоритма D.

Программа D (Сортировка Шелла). Предполагается, что смещения для сортировки хранятся во вспомогательной таблице и находится по адресу Н -Ь s; все смещения сортировки меньше N. Содержимое регистров таково: гП = j - N; rI2 = г; тА = R = К; г13 = s; г14 = h. Обратите внимание на то, что эта программа сама себя изменяет. Это сделано для того, чтобы добиться более эффективного выполнения внутреннего цикла.

D1. Цикл по S. S t - 1. D2. Цикл по j. h hs. Модификация адресов в трех командах основного цикла.

tlHr-N - h.

D3. Присвоить i, K, R.

j-h.

[Изменяемая команда]

D5. Переписать Д,. уменьшить i.

Ri+h Ri- [Изменяемая команда]

г г - Л.

Перейти к шагу D4, если г > 0.

D6. Переместить R [Изменяемая команда]

на место Rj+h.

Перейти к шагу D3, если j < N. t> s>0. I

*Анализ метода Шелла. Для рационального выбора последовательности значений смещений сортировки ht-i,- ,ho для алгоритма D нужно проанализировать время выполнения как функцию от этих смещений. Такой анализ приводит к постановке очень красивых, но еще не до конца решенных математических задач; никому до сих пор не удалось найти наилучшую возможную последовательность смещений для больших Л. Тем не менее известно довольно много интересных свойств сортировки методом Шелла с убывающим смещением, и мы здесь их кратко изложим; подробности будут рассмотрены в приведенных ниже упражнениях. [Читателям, не склонным к пространным математическим выкладкам, лучше пропустить следующие несколько страниц вплоть до начала обсуждения метода вставки в список, который следует за формулой (12).]

Счетчики частот выполнения в программе D показывают, что на время выполнения влияют пять факторов: размер массива N, число проходов (т. е. число различных смещений) Т - t, сумма значений смещений в последовательности

S = ho + + ht-

число сравнений В + NT - S - А и число перезаписей В. Как и при анализе программы S, здесь А равно числу левосторонних минимумов, встречающихся при промежуточных операциях сортировки, а В равно числу инверсий в подмассивах. Основным фактором, от которого зависит время выполнения, является величина В, поэтому на нее мы в основном и обратим свое внимание. При анализе будет предполагаться, что ключи различны и первоначально расположены в случайном порядке.

Назовем операцию шага D2 Л-сортировкой. Тогда сортировка методом Шелла состоит из /1( 1-сортировки, за которой следует Л-г-сортировка, ..., за которой следует Лр-сортировка. Массив, в котором Ki < Ki+h при 1 < г < Л - Л, будем называть Л-упорядоченным.

Рассмотрим сначала простейшее обобщение простых вставок, когда имеется всего два смещения: hi = 2 и Ло = 1- Во время второго просмотра имеем 2-упорядочен-ную последовательность ключей KiK2--- Kf. Легко видеть, что число перестановок 01 02 ... а„ множества {1,2,..., п}, таких, что о» < aj+a при 1 < г < п - 2, равно

так как существует всего одна 2-упорядоченная перестановка для каждого выбора [n/2J элементов, расположенных в четных позициях аг 04 ...; тогда остальные \п/2] элементов попадают в позиции с нечетными номерами. После 2-сортировки случайного массива с одинаковой вероятностью может получиться любая 2-упорядоченная перестановка. Каково среднее число инверсий во всех таких перестановках?

Пусть А„ - суммарное число инверсий во всех 2-упорядоченных перестановках множества {1,2,..., п}. Ясно, что Ai = О, Аз = 1, Аз = 2; рассмотрев шесть случаев

1324 1234 1243 2134 2143 3142,

находим, что у14 = 1-1-0-1-1-1-1-1-2-1-3 = 8. Чтобы проанализировать А„ в общем случае, рассмотрим "решетчатую диаграмму" на рис. 11 для п = 15. На такой диаграмме 2-упорядоченную перестановку множества {1,2, ...,п} можно представить в виде пути из верхней левой угловой точки (0,0) в нижнюю правую угловую