Тема 2. Улучшенные методы сортировки массивов

Метод Шелла

Метод Шелла является улучшенным вариантом метода вставок. Поскольку метод вставок дает хорошие показатели качества для небольших или почти упорядоченных наборов данных, метод Шелла использует эти свойства за счет многократного применения метода вставок.

Алгоритм метода Шелла состоит в многократном повторении двух основных действий:

· объединение нескольких элементов исходного массива по некоторому правилу

· сортировка этих элементов обычным методом вставок

Более подробно, на первом этапе группируются элементы входного набора с достаточно большим шагом. Например, выбираются все 1000-е элементы, т.е. создаются группы:

группа 1: 1, 1001, 2001, 3001 и т.д.

группа 2: 2, 1002, 2002, 3002 и т.д.

группа 3: 3, 1003, 2003, 3003 и т.д.

. . . . . . . . . . . . . . . . . . . . .

группа 1000: 1000, 2000, 3000 и т.д.

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

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

На третьем этапе элементы группируются с еще меньшим шагом, например – все десятые элементы. Выполняется сортировка, группировка с еще меньшим шагом и т.д.

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

Пример. Исходный набор: 15 – 33 – 42 – 07 – 12 - 19

Выполняем группировку с шагом 3, создаем три группы по 2 элемента и сортируем каждую из них отдельно:

группа 1: 15 – 07 => 07 – 15 (1 сравнение, 1 пересылка)

группа 2: 33 – 12 => 12 – 33 (1 сравнение, 1 пересылка)

группа 3: 42 – 19 => 19 – 42 (1 сравнение, 1 пересылка)

Новый набор чисел: 07 – 15 – 12 – 33 – 19 – 42

Группировка с меньшим шагом 2 дает 2 группы по 3 элемента, которые сортируются отдельно:

группа 1: 07 – 12 – 19 => уже упорядочена (2 сравнения, 0 пересылок)

группа 2: 15 – 33 – 42 => уже упорядочена (2 сравнения, 0 пересылок)

Новый набор чисел: 07 – 12 – 19 – 15 – 33 – 42

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

Итого – 12 сравнений и 4 пересылки, что в общем-то не лучше чем у простых методов. Однако, здесь надо учесть два фактора.

Фактор 1 (общий). Улучшенные методы показывают свою эффективность именно для больших наборов данных (сотни, тысячи и т.д. элементов). Для очень малых наборов (как в примере) они могут давать даже худшие результаты.

Фактор 2 (специфический). Эффективность метода Шелла существенно зависит от выбора последовательности шагов группировки. Эта последовательность обязательно должна быть убывающей, а последний шаг обязательно равен 1. В настоящее время неизвестна наилучшая последовательность шагов, обеспечивающая наименьшую трудоемкость. На основе многочисленных экспериментов установлено, что число шагов группировки надо выбирать по формуле [(log ₂ n)] – 1, где скобки [ ] используются для обозначения целой части числа, а в качестве самих последовательностей рекомендуется один из следующих наборов (обращаю внимание: для удобства восприятия шаги даются в обратном порядке):

1, 3, 5, 9, 17, 33, . . . (общая формула: t_k = (2* t_k-1) –1 )

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767 . . . (общая формула: t_k = (2* t_k-1) +1, а еще проще – (2^k – 1)).

В соответствии с этими рекомендациями, в предыдущем примере надо взять лишь 2 шага группировки со значениями 3 и 1. В этом случае потребуется лишь 8 сравнений и 5 пересылок.

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

for m := 1 to t do {t – число шагов группировки, m – номер шага}

Begin

k := h [m]; {выбор величины шага группировки из заданного массива}

for i := k + 1 to n do {сортировка вставками внутри каждой группы}

Begin

temp := a [i]; j := i – k;

while (j > 0) and (temp < a [j]) do

Begin

a [j + k] := a [j]; j := j – k;

end;

a [j + k] := temp;

end;

end;

Оценка трудоемкости метода Шелла выражается соотношением O(n^1,2), что лучше чем у простейших методов, особенно при больших n.