Метод сортировки Шелла

Общие сведения о сортировке данных

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

Сортировка является операцией расположения последовательной совокупности однотипных данных в необходимом порядке в соответствии с заданными правилами. Одной из главных характеристик алгоритмов сортировки выступает скорость работы и уровень оптимальности использования ресурсов памяти. Скорость работы или быстродействие сортировки может определяться количеством операций сравнения и количеством операций перестановки компонентов (операций обмена), которые реализуются при осуществлении алгоритма сортировки.

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

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

Метод сортировки Шелла

В пятьдесят девятом году прошлого века американский ученый Дональд Шелл создал алгоритм сортировки, в дальнейшем получивший наименование «Сортировка Шелла». Данный алгоритм можно рассматривать в качестве обобщения, как пузырьковой сортировки, так и сортировки вставками. Сущность метода состоит в сравнении разделенных на группы компонентов последовательности, которые находятся друг от друга на определенном расстоянии. Первоначально данное расстояние равняется d или N/2, где N является общим числом компонентов.

На первом этапе все группы включают в себя пару компонентов, которые расположены друг от друга на расстоянии N/2. Они должны сравниваться между собой, и, если это необходимо, должны меняться местами. На следующих этапах также должна выполняться проверка и обмен, но расстояние d следует сократить на d/2, и число групп, естественно, также станет меньше. Постепенно расстояние между компонентами сокращается, и на d=1 проход по массиву выполняется в последний раз.

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

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

При каждой итерации главного цикла это расстояние непрерывно сокращается и когда оно станет равным единице, то сортировка Шелла в данный момент фактически преобразуется в классическую сортировку простыми вставками, которой предоставили для обработки почти отсортированный массив. А практически отсортированный массив сортировка простыми вставками способна преобразовать в полностью отсортированный достаточно оперативно.

Рассмотрим конкретный пример. Предположим имеется следующий список:

$A= (32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68)$.

Требуется выполнить его сортировку при помощи метода Шелла, а в качестве значений d необходимо выбрать 5, 3, 1.

На первом этапе следует сортировать подсписки А, которые составлены из всех компонентов А, отличающихся на пять позиций, то есть подсписки:

$ А_{5,1} = (32, 66, 40), А_{5, 2} = (95, 35, 43), А_{5, 3} = (16, 19, 93), А_{5, 4} = (82, 75, 68), А_{5, 5} = (24, 54)$

В сформированном списке на втором этапе снова выполняется сортировка подсписков из отстоящих на три позиции компонентов. Процесс должен завершаться стандартной сортировкой вставками сформированного списка. Реализация этого алгоритма в псевдокоде приведена ниже.

Рисунок 1. Алгоритм в псевдокоде. Автор24 — интернет-биржа студенческих работ

Реализация данного алгоритма на языке Си:

Рисунок 2. Алгоритм на языке Си. Автор24 — интернет-биржа студенческих работ