Сортировка Шелла
Сортировку Шелла придумал Дональд Л. Шелл. Ее необычность состоит в том, что она рассматривает весь список как совокупность перемешанных подсписков. На первом шаге эти подсписки представляют собой просто пары элементов. На втором шаге в каждой группе по четыре элемента. При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков, соответственно, падает. На рис. 3.1 изображены подсписки, которыми можно пользоваться при сортировке списка из 16 элементов.
саму картинку вставлю когда обьяснять как это сделать
и еще б хотелось знать как делать отступы)
На рис. 3.1 (а) изображены восемь подсписков, по два элемента в каждом, в которых первый подсписок содержит первый и девятый элементы, второй подсписок — второй и десятый элементы, и так далее.
На рис. 3.1 (б) мы видим уже четыре подсписка по четыре элемента в каждом. Первый подсписок на этот раз содержит первый, пятый, девятый и тринадцатый элементы. Второй подсписок состоит из второго, шестого, десятого и четырнадцатого элементов. На рис. 3.1 (в) показаны два подсписка, состоящие из элементов с нечетными и четными номерами соответственно. На рис. 3.1 (г) мы вновь возвращаемся к одному списку.
Сортировка подсписков выполняется путем однократного применения сортировки вставками. В результате мы получаем следующий алгоритм:
Code
Shellsort(list,N)
list сортируемый список элементов
N число элементов в списке
passes = [log_2 N] //логарифм по основе 2 из N
while (passes>=1) do
increment=2^passes-1
for start=1 to increment do
InsertionSort (list, N, start, increment)
end for
passes=passes-1
end while
Добавлено (17.03.2008, 05:09)
---------------------------------------------
Переменная increment содержит величину шага между номерами элементов подсписка. (На рис. 3.1 шаг принимает значения 8, 4, 2 и 1.) В алгоритме мы начинаем с шага, на 1 меньшего наибольшей степени двойки, меньшей, чем длина элемента списка. Поэтому для списка из 1000 элементов первое значение шага равно 511. Значение шага также равно числу подсписков. Элементы первого подсписка имеют номера 1 и 1+increment; первым элементом последнего подсписка служит элемент с номером increment. При последнем исполнении цикла while значение переменной passes будет равно 1, поэтому при последнем вызове функции InsertionSort значение переменной increment будет равно 1.
Анализ этого алгоритма основывается на анализе внутреннего алгоритма InsertionSort. Прежде, чем перейти к анализу алгоритма ShellSort, напомним, что в расмотреной сортировке вставками мы подсчитали, что в наихудшем случае сортировка вставками списка из N элементов требует (N
2 — N)/2 операций, а в среднем случае она требует N
2/4 элементов.
Добавлено (17.03.2008, 05:14)
---------------------------------------------
Анализ алгоритма
Начнем анализ с подсчета числа вызовов функции InsertionSort и числа элементов в списке при каждом из этих вызовов. Обратимся к частному случаю списка длины 15. При первом проходе значение переменной increment равно 7, поэтому будет выполнено семь вызовов на списках длины 2. При втором проходе значение переменной increment равно 3, поэтому произойдет три вызова на списках длины 5. На третьем, и последнем, проходе мы делаем один вызов на списке длины 15. Из предыдущих результатов мы знаем, что на списке из двух элементов алгоритм InsertionSort делает одно сравнение в наихудшем случае. Число сравнений в наихудшем случае на списке из 5 элементов равно 10. Число сравнений в наихудшем случае на списке из 15 элементов равно 105. Сложив все эти числа, мы получаем всего 142 сравнения (7 • 1 + 3 • 10 + 1 • 105). Хорошую ли оценку мы получили, однако? Если вернуться к анализу из раздела 3.1.1, то можно вспомнить, что в наихуд шем для сортировки вставками случае каждый новый элемент добавляется в начало списка. При последнем проходе алгоритма ShellSort мы знаем, что этот наихудший случай не может осуществиться ввиду того, что на более ранних этапах также осуществлялась сортировка. Быть может, другой подход поможет подсчитать объем оставшейся работы?
При анализе алгоритмов сортировки мы будем иногда подсчитывать количество инверсий в списке. Инверсия — это пара элементов списка, идущих в неправильном порядке. Например, в списке [3,2,4,1] четыре инверсии, а именно, (3,2), (3,1), (2,1) и (4,1).
Добавлено (17.03.2008, 05:19)
---------------------------------------------
Больше всего инверсий, как нетрудно видеть, в списке, элементы которого идут в обратном порядке; их число равно (N2 — N)/2. Один из способов анализа алгоритма сортировки состоит в том, чтобы подсчитать число инверсий, отличающее начальное состояние списка от отсортированного списка. Каждая перестановка элементов в алгоритме уменьшает количество инверсий по крайней мере на одну. Если, например, пузырьковая сортировка обнаружила в результате сравнения пару соседних элементов, идущих в неправильном порядке, то их перестановка уменьшает количество инверсий в точности на единицу. То же самое справедливо и для сортировки вставками, поскольку сдвиг большего элемента на одну позицию вверх приводит к уничтожению инверсии, образованной сдвигаемым и вставляемым элементами.
Добавлено (17.03.2008, 05:21)
---------------------------------------------
[j]Поэтому в пузырьковой сортировке и сортировке вставками (обе сложности O(N2)) всякое сравнение может привести к удалению одной (или менее) инверсии. В основе сортировки Шелла лежит сортировка вставками, поэтому может показаться, что и для нее справедливо тоже самое утверждение. Однако, если принять во внимание, что в сортировке Шелла упорядочиваются перемешанные подсписки, вызванный отдельным сравнением обмен элементов местами может уменьшить число инверсий более, чем на одну. При первом проходе на рис. 3.1 сравнивались элементы 16 и 14; поскольку их порядок оказался неправильным, они были переставлены. Переместив элемент 16 с первого места на девятое, мы избавились от семи инверсий, содержащих этот элемент (вторые элементы этих инверсий расположены в позициях со второй по восьмую). Анализ сортировки Шелла вызывает сложности, поскольку та же самая перестановка элементов привела к появлению новых семи инверсий, содержащих элемент 14. Поэтому она уменьшила общее число инверсий лишь на единицу. Если посмотреть на перестановку элементов 7 и 4, то результат выглядит так же. Однако в целом ситуация улучшается. На первом проходе после восьми сравнений оказались удаленными 36 инверсий. На втором проходе выполнено 19 сравнений и удалено 24 инверсии. Наконец, на последнем шаге было сделано 19 сравнений и удалено 10 последних инверсий. Общее число сравнений равно 62. Даже если бы мы заменили худший случай при анализе вызовов сортировки вставками средним, мы все равно насчитали бы 152 сравнения.
[j]
Добавлено (17.03.2008, 05:33)
---------------------------------------------
Полный анализ сортировки Шелла чрезвычайно сложен, и мы не собираемся на нем останавливаться. Было доказано, что сложность этого алгоритма в наихудшем случае при выбранных нами значениях шага равна O(N3/2). Полный анализ сортировки Шелла и влияния на сложность последовательности шагов (которое мы обсуждаем в следующем разделе) можно найти в третьем томе книги Д. Кнута Искусство программирования, М., Мир, 1978.
Добавлено (17.03.2008, 05:37)
---------------------------------------------
Выбор последовательности шагов может оказать решающее влияние на сложность сортировки Шелла, однако попытки поиска оптимальной последовательности шагов не привели к искомому результату. Изучалось несколько возможных вариантов; здесь представлены результаты этого изучения.
Если проходов всего два, то при шаге порядка 1.72*N1/3 на первом проходе и 1 на втором проходе получим сортировку сложности О(N5/3). Другой возможный набор шагов имеет вид hj = (Зj — 1)/2 для всех тех j, при которых hj < N. Эти значения hj удовлетворяют равенствам hj+1 = 3*hj + 1 и hj = 1, поэтому определив наибольшее из них, мы можем подсчитать оставшиеся по формуле hj = (hj+1 — 1)/3. Такая последовательность шагов приводит к алгоритму сложности O(N3/2).
Добавлено (17.03.2008, 05:44)
---------------------------------------------
Еще один вариант предусматривает вычисление всех значений 2i*3j, меньших длины списка (при произвольных целых i и j); вычисленные значения используются, в порядке убывания, в качестве значений шагов. Например, при N — 40 имеется следующая последовательность шагов: 36 (2232), 32 (2530), 27 (2033), 24 (2331), 18 (2132), 16 (2430), 12 (2231), 9 (2032), 8 (2330), 6 (2131), 4 (2230), 3 (20З1), 2 (2130), 1 (2030). С помощью такой последовательности шагов сложность сортировки Шелла понижается до O(N*(logN)). Следует заметить, что большое число проходов значительно увеличивает накладные расходы, поэтому при небольших размерах списка применение этой последовательности не слишком эффективно.
Сортировка Шелла — это один общий вид сортировки, однако выбор параметров может существенно повлиять на ее эффективность.
