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

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

Идея заключается в переупорядочении файла таким образом, чтобы придать ему следующее свойство: совокупность r-ых элементов исходного файла (начиная с любого) образует отсортированный файл. В таком случае говорят, что файл h-упорядочен (h-sorted). Другими словами, h-упорядоченный файл представляет собой h независимо отсортированных взаимно проникающих друг в друга файлов. В процессе h-сортировки при достаточно больших значениях h можно менять местами элементы массива, расположенные достаточно далеко друг от друга, и тем самым ускорить последующую h-сортировку при меньших значениях h. Использование такого рода процедуры для любой последовательности значений h, которая заканчивается единицей, завершается получением упорядоченного файла: именно в этом и заключается суть сортировки методом Шелла.

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

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

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