Первый подсписок на этот раз содержит первый, пятый, девятый и тринадцатый элементы. Второй подсписок состоит из второго, шестого, десятого и четырнадцатого элементов. На рис. 3.1 (в) показаны два подсписка, состоящие из элементов с нечетными и четными номерами соответственно. На рис. 3.1 (г) мы вновь возвращаемся к одному списку.

Сортировка подсписков выполняется путем однократного применения сортировки вставками из § 3.1. В результате мы получаем следующий алгоритм:

Shellsort(list.N)

list сортируемый список элементов

N число элементов в списке

passes = [log_2 N]

while (passes>=l) do

increment=2*passes-1

for start=l to increment do

InsertionSort(list,N,start,increment)

end for

passes=passes-l

end while

Переменная increment содержит величину шага между номерами элементов подсписка. (На рис. 3.1 шаг принимает значения 8, 4, 2 и 1.) В алгоритме мы начинаем с шага, на 1 меньшего наибольшей степени двойки, меньшей, чем длина элемента списка. Поэтому для списка из

1000 элементов первое значение шага равно 511. Значение шага также равно числу подсписков. Элементы первого подсписка имеют номера 1 и 1+increment; первым элементом последнего подсписка служит элемент с номером increment. При последнем исполнении цикла while значение переменной passes будет равно 1, поэтому при последнем вызове функции InsertionSort

значение переменной increment будет равно 1. Анализ этого алгоритма основывается на анализе внутреннего алгоритма InsertionSort. (в наихудшем случае сортировка вставками списка из N элементов требует (N²-N)/2 операций, а в среднем случае она требует N²/4 элементов.)

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

В наихудшем случае A(N)=N^3/2

Корневая сортировка.

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

Подобная процедура используется при ручной сортировке карт. В некоторых библиотеках в докомпьютерные времена при выдаче книги заполнялась карта выдачи. Карты выдачи были занумерованы, а сбоку на них проделывался ряд выемок --в зависимости от номера карты.

При возвращении книги карта выдачи удалялась, и ее клали в стопку. Затем вся стопка прокалывалась длинной иглой на месте первой выемки, и иглу поднимали. Карты с удаленной выемкой оставались на столе, а остальные были наколоты на иглу. Затем две получившиеся стопки переставлялись так, что карточки на игле шли за карточками с отверстиями. Затем игла втыкалась в месте второй выемки и весь процесс повторялся. После прокалывания по всем позициям карты оказывались в порядке возрастания номеров. Эта процедура ручной обработки разделяет карты по значению младшего разряда номера на первом шаге и старшего разряда на последнем.

Если в самом длинном ключе М цифр, а число ключей равно N, то сложность корневой сортировки имеет порядок O(MN). Однако длина ключа невелика по сравнению с числом ключей. Например, при ключе из шести цифр число различных записей может быть равно миллиону. Длина ключа не играет роли и алгоритм имеет линейную по длине сложность O(N). Это очень эффективная сортировка, поэтому возникает вопрос, зачем вообще нужны какие-либо другие методы. Ключевым препятствием в реализации корневой сортировки служит ее неэффективность по памяти.

Быстрая сортировка.

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

сложность – в среднем О ( n log₂ n) и О(n²) в худшем случае.

Сортировка слиянием.

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

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

12. Основные вопросы анализа алгоритмов. Понятие алгоритмической сложности.

• описание анализа алгоритма;

• объяснение принципов выбора подсчитываемых операций;

• объяснение, как проводить анализ в наилучшем, наихудшем и среднем случае;

• работа с логарифмами, вероятностями и суммированием;

• описание функции θ(f), Ω(f), Ο ( f ) , скорости роста и порядка

алгоритма;

• использование дерева решений для определения нижней границы

сложности;

• приведение простого рекуррентного соотношения к замкнутому виду.

Определение Д.2.1. Трудоемкость алгоритма. Под трудоемкостью алгоритма для данной конкретной проблемы, заданной множеством D, будем понимать количество «элементарных» операций, задаваемых алгоритмом в принятой модели вычислений. Соответствующую функцию будем обозначать как f_a (D). Заметим, что значением функции трудоемкости является целое положительное число.

При более детальном анализе ряда алгоритмов оказывается, что не всегда количество элементарных операций задаваемых алгоритмом, т.е. значение f_a (D) на входе длины n, где n = \D\, совпадает с количеством операций на другом входе такой же длины.

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

Пусть DA — множество допустимых конкретных проблем данной задачи, решаемой алгоритмом A, D e DA — конкретная проблема (вход алгоритма А), представляющая собой упорядоченное множество элементов (слов) d:

В общем случае существует подмножество (для большинства алгоритмов собственное) множества DA, включающее все конкретные проблемы, имеющие размерность n, — обозначим его через D_n:

В предположении о том, что элементы d, представляют собой слова фиксированной длины в алфавите {0,1}, множество D_n„ является конечным — обозначим его мощность через M_Dn , т.е. M_Dn = \D_n\. Тогда алгоритм А, имея на входе различные множества D e D_n, будет, возможно, задавать в каком-то случае наибольшее, а в каком-то случае наименьшее количество операций.

Введем следующие обозначения, отметив, что соответствующая терминология является устоявшейся в литературе по анализу алгоритмов ([2, 3]).

1. f_A(n) — худший случай — наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n:

2. f_A(n) — лучший случай — наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n:

3. f_A(n) — средний случай — среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n: