наилучшую последовательность, по-видимому, отыскать не удалось. В общем случае на практике используются убывающие последовательности шагов, близкие к геометрической профессии, в результате чего число шагов находится в логарифмической зависимости от размеров файлов. Например, если размер следующего шага равен примерно половине предыдущего, то для сортировки файла, состоящего из 1 миллиона элементов, потребуется примерно 20 шагов, если такое соотношение примерно равно одной четвертой, то достаточно будет 10 шагов. Использование как можно меньшего числа шагов - это весьма важное требование, которое нетрудно учесть, но при этом в последовательности шагов необходимо вьщерживать различные арифметические соотношения, такие как величины их общих делителей и ряд других свойств.

Практический результат от обнаружения хорошей последовательности шагов, по-видимому, ограничен повышением быстродействия алгоритма на 25%, в то же время сама проблема представляет собой увлекательную загадку - примером того, какие сложные вопросы характерны для использования на первый взгляд простого алгоритма.

Программа 6.5. Сортировка методом Шелла

Если отказаться от использования сигнальных ключей, а затем заменить каждое появление 1 на Л в сортировке вставками, то полученная при этом программа реализует /7-сортировку файла. Добавление внешнего цикла, изменяющего значение шага, позволяет получить компактную программную реализацию сортировки методом Шелла, в которой используется последовательность шагов 1 413 40 121 364 1093 3280 9841 ...

template <class Item>

void shellsort (Item a[] , int 1, int r) { int h;

for (h = 1; h <= {r-l)/9; h = 3*h+l) ; for ( ; h > 0; h /= 3) for (int i = 1+h; i <= r; i++) { int j = i; Item v = a[i] ;

while (j >= 1+h ii V < a[j-h])

{ a[j] = a[j-h]; j -= h; } a[j] = v;

ASORTINGEXAMPLE A S О R T I NO EXAMPLE A E О R T I N Q E X A M P L S

A E A E A E A E A E A E A E >.E. A С

А <3

А Е А

А А Е

А А Е

А А Е

А А Е

А А Е

А А Е

L М N

L М N

L М N

L М N

L М N

L М N

L М N

AM А М А М А М А М

,Х S X S

РИСУНОК 6.9. ПРИМЕР СОРТИРОВКИ МЕТОДОМ ШЕЛЛА.

Сортировка файла при помощи \Ъ-сортировки (сверху), с последующими 4-сортировкой (в центре) и \-сортировкой (внизу), не требует выполнения большого объема операций сравнения (о чем можно судить по количеству незаштрихованных элементов). Завершающий проход есть ни что иное как сортировка вставками, но при этом ни один из элементов не должен далеко перемещаться благодаря порядку, установленному в файле на двух первых проходах.

Последовательность шагов 1 4 13 40 121 364 1093 3280 9841 используемая в программе 6.5, в которой соотношение соседних шагов составляет приблизительно одну треть, была рекомендована Кнутом в 1969 г. {см. раздел ссылок). Она просто вычисляется (начав с 1, получить значение следующего шага, умножив предыдущее значение на 3 и добавив 1) и обеспечивает реализацию сравнительно эффективной сортировки даже в случае относительно больших файлов (см. рис.6.10).

РИСУНОК 6.10. СОРТИРОВКА МЕТОДОМ ШЕЛЛА СЛУЧАЙНО РАСПРЕДЕЛЕННОЙ ПЕРЕСТАНОВКИ

Целью каждого прохода при сортировке методом Шелла состоит в том, чтобы привнести в файл как единое целое большую степень упорядоченности. Сначала файл подвергается 40-сортировке, затем 13-сортировке, далее 4-сортировке, и наконец, 1-сортировке. Каждый проход приближает порядок в файле к окончательному.

Многие другие последовательности шагов позволяют получить еще более эффективную сортировку, однако довольно трудно превзойти эффективность программы 6.5 более чем на 20% даже в случае сравнительно больших значений N. Одной из таких последовательностей является 1 8 23 77 281 1073 4193 16577 т.е. последовательность 4 + 3 2 + 1 для / > 0. Можно доказать, что приведенная последовательность обеспечивает повышенное быстродействие для самых трудных случаев сортировки (см. лемму 6.10). Рисунок 6.12 показывает, что эта последовательность, равно как и последовательность Кнута, а также многие другие последовательности шагов, обладают похожими динамическими характеристиками для файлов больших размеров. Вполне возможно, что существуют лучшие последовательности. Несколько идей по улучшению последовательностей шагов приводится в разделе упражнений.

С другой стороны, существуют и плохие последовательности шагов: например, 1 2 4 8 16 32 64 128 256 512 1024 2048 ... (первая последовательность шагов, предложенная Шеллом еще в 1959 г. {см. раздел ссылок)), скорее всего, служит причиной низкой эффективности сортировки, поскольку элементы на нечетных позициях не сравниваются с элементами на четных позициях влоть до последнего прохода. Этот эффект заметен на файлах с произвольной организацией, он становится катастрофическим в наихудших случаях: эффективность метода резко снижается и время выполнения сортировки становится пропорциональным квадрату Л, если, например, половина элементов файла с меньшими значениями находится в четных позициях, а другая половина элементов (с большими значениями) - в нечетных позициях (см. упражнение 6.36).

Профамма 6.5 вычисляет следующий шаг, разделив текущий шаг на 3 после инициализации с таким расчетом, чтобы всегда использовалась одна и та же последовательность шагов. Другой вариант заключается в том, что сортировка начинается с h=N/3 или для этой цели используется другая функция от N. Но лучше отказаться от стратегий подобного рода, ибо для некоторых значений N могут появиться плохие последовательности шагов наподобие описанной выше.

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

довательностей шагов, но и аналитическое сравнение сортировки методом Шелла с другими методами сортировки. Не известна даже функциональная форма для определения времени выполнения сортировки методом Шелла (более того, эта форма зависит от выбора последовательности шагов). Кнут обнаружил, что функциональные формы N(\o2,N) и Л довольно точно описывают ситуацию, а дальнейшие исследования показали, что для некоторых видов последовательностей подходят более сложные функции вида Vi

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

Лемма 6.7. Результатом h-сортировки к-упорядоченного файла есть h- и к-упорядочен-ный файл.

Этот факт кажется очевидным, однако чтобы его доказать, потребуются значительные усилия (см. упражнение 6.47).

Лемма 6.8. Сортировка методом Шелла выполняет менее N(h -\)(к- \ )/g операций сравнения при g-сортировке И- и к-упорядоченного файла при условии, что h и к взаимно просты.

Основа этого факта показана на рис. 6.11. Ни один элемент, расположенный дальше (А - l)( - 1) позиций слева от любого заданного элемента х, не может быть больше X, если h w к взаимно просты (см. упражнение 6.43). При -сортировке проверяются не более одного из g таких элементов.

Лемма 6.9. Сортировка методом Шелла выполняет менее 0(N) операций сравнения для последовательности шагов 1 4 13 40 121 364 1093 3280 9841...

Для больших шагов, когда имеются h подфайлов размером N/h, в наихудшем случае расходы составляют примерно N/h. При малых шагах из леммы 6.8 следует, что стоимость составляет приблизительно Nh. Все зависит от того, насколь успешно удастся вписаться в эти границы на каждом шаге. Это справедливо для каждой относительно простой последовательности, возрастающей экспоненциально.

Лемма 6.10. Сортировка методом Шелла выполняет менее 0(N) операций сравнения для последовательности шагов 1 8 23 77 281 1073 4193 16577...

Доказательство этой леммы практически не отличается от доказательства леммы 6.9. Из леммы, аналогичной лемме 6.8, следует, что стоимость сортировки при небольших значениях шагов принимает значение порядка УУЛ. Доказательство этой леммы требует привлечения аппарата теории чисел, что выходит за рамки данной книги (см. раздел ссылок).