ВУЗ:
Составители:
116
Метод Шелла. Данный метод, названный именем его создателя, широко
используется, требует минимальной памяти и обеспечивает высокую скорость
сортировки. В методе Шелла используются сравнения и перестановки элемен-
тов как и в методе вставок, однако в отличие от последнего, в сравнении участ-
вуют не соседние элементы, а элементы, отстоящие друг от друга
на определен-
ном расстоянии. При необходимости перестановки элементы перемещаются
скачком на это же расстояние.
Для проведения сортировки методом Шелла последовательность из N
элементов делится на N/2 групп или – на (N–1)/2 групп, если N нечетно. Каждая
группа содержит по 2 элемента. Если число элементов нечетно, то одна группа
будет содержать 3 элемента. Элементы, принадлежащие
одной группе, отстоят
на N/2 позиций. Это расстояние называется шагом.
На рис. 8.5 приведен пример сортировки методом Шелла исходной по-
следовательности A(i), содержащей 16 элементов. Последовательность A(i) раз-
делена на (N–1)/2=7 групп по 2 элемента в группе, первая группа содержит 3
элемента. Шаг первого прохода равен (N–1)/2=7. Элементы, принадлежащие
одной (первой) группе, затемнены
. В первом проходе упорядочение элементов в
группе осуществляется методом вставок. В результате элементы 14, 8 и 6 пер-
вой группы займут позиции 6, 8 и 14 соответственно. Поменяются местами так-
же элементы второй группы (11 и 10) и элементы пятой группы (12 и 2).
Для осуществления каждого последующего прохода Шелл предложил
устанавливать шаг, равный половине предыдущего шага (у дробных чисел
бе-
рется целая часть). Для рассматриваемого примера шаг второго прохода будет
равен ]7/2[=3. Во втором проходе будет упорядочиваться первая группа, содер-
жащая элементы 6, 9, 3, 15, 4 (элементы затемнены), вторая группа, содержащая
элементы 10, 2, 8, 13, 7, и третья группа, содержащая элементы 5, 1, 11, 12, 14. В
результате второго прохода элементы этих групп окажутся упорядоченными по
возрастанию их значений. На втором и последующих проходах
упорядочение
элементов в группе осуществляется методом обмена.
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A(i) 14 11 5 9 12 1 3 8 10 15 13 2 4 7 6
Проход 1 6 10 5 9 2 1 3 8 11 15 13 12 4 7 14
Проход 2 3 2 1 4 7 5 6 8 11 9 10 12 15 13 14
Проход 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Рис. 8.5. Пример сортировки методом Шелла
Для рассматриваемого примера шаг третьего прохода будет ]3/2[=1 и,
следовательно, в нем будет упорядочиваться единственная группа, содержащая
элементы 3, 2, 1, 4, 7, 5, 6, 8, 11, 9, 10, 12, 15, 13, 14 (элементы затемнены). В
результате попарных сравнений и обменов исходная последовательность оказы-
вается полностью упорядоченной после третьего прохода.
Страницы
- « первая
- ‹ предыдущая
- …
- 114
- 115
- 116
- 117
- 118
- …
- следующая ›
- последняя »
