2.1 Сортировка массивов

Справка:Пусть дан массив , состоящий из n элементов. Для всех элементов определены отношения <, >, =. Тогда сортировка – это процесс, в ходе которого элементы массива переставляются таким образом, что выполняется одно из следующих неравенств:

массив отсортирован по возрастанию (в прямом порядке) или

массив отсортирован по убыванию (в обратном порядке).

2.1.1 Пузырьковая сортировка (BubbleSort)

Пузырьковая сортировка – пример простейшего метода сортировки,

обладающего квадратичной трудоёмкостью.

Алгоритм: Двигаясь от конца массива к его началу, сравниваем между собой соседние элементы. Если правый элемент меньше, чем левый, то меняем их местами. Таким образом, при первом проходе массива самый маленький элемент переместится на первое место, и его можно не учитывать при сортировке оставшейся части массива. При втором проходе (его можно начинать не с первого, а со второго элемента массива), наименьший из оставшихся элементов переместится на второе место. Затем начинаем двигаться с третьего элемента, и так далее. Необходимо предусмотреть возможность выхода из алгоритма в случае, если мы прошли весь массив и не сделали ни одной перестановки. Для сортировки всего массива понадобится не более, чем (n-1) проходов.

Пузырьковая сортировка сильно зависит от упорядоченности массива.

Трудоемкость алгоритма (максимальная): .

В случае если исходный массив отсортирован по возрастанию, трудоемкость алгоритма составляет (n-1) сравнений.

2.1.2 Метод прямого выбора (SelectSort)

Метод прямого выбора – пример простейшего метода сортировки,обладающего квадратичной трудоёмкостью.

Алгоритм: Просматриваем весь массив, находим минимальный элемент, ставим его на первое место. Потребуется n–1 сравнений и одна перестановка. При втором проходе просматриваем массив, начиная со второго элемента, находим минимум среди просматриваемой ( не отсортированной) части и ставим его на второе место, и т.д. Потребуется n–2 сравнений и одна перестановка. Для полного упорядочивания придется совершить n–1 проходов не отсортированной части.

Трудоемкость алгоритма: .

2.1.3 Быстрая сортировка методом двоичных вставок (MergeSort)

Рассмотрим случай, когда количество элементов массива равно степени двойки n=2k

Алгоритм: 1. Разобьем массив на пары и упорядочим каждую. Получаем серии длины 2.

2. При втором проходе сливаем полученные на первом этапе пары в упорядоченные четверки. Получаем серии длины 4.

3. При третьем проходе получаем упорядоченные восьмерки, и т.д., пока длина серии не станет равной количеству элементов массива (на k-том проходе).

Оценим трудоемкость алгоритма:

Сначала оценим трудоемкость слияния двух упорядоченных массивов из k и l элементов (считаем только сравнения):

k:

2

3

8

10

14

l:

3

5

6

10

11

Минимальная трудоемкость – меньшее из k и l – min(k, l).

Максимальная трудоемкость: k + l – 1 (единицу вычитаем потому, что сравниваем все элементы, а самый последний просто дописываем к упорядоченной группе).

В MergeSort при получении упорядоченных пар потребуется действий. При получении упорядоченных четверок действий. Здесь есть количество четверок в массиве, а 3 – это максимальная трудоемкость получения упорядоченных четверок (считая только сравнения) . Таким образом суммарная трудоемкость сортировки составит:

Таким образом, трудоемкость MergeSort составляет

. Теорема: Сортировка на порядок быстрее, чем невозможна.

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

Напомним, что двоичное дерево – граф, у которого ветвление в каждой вершине не больше, чем на две ветви.

Тогда развилками дерева будут сравнения двух элементов массива; а листьями – все возможные варианты перестановки элементов массива (у массива длины n их будет n!).

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

Дерево с k листьями имеет высоту не меньше, чем log2k (т.к. дерево высоты h имеет не более, чем 2n листьев). Итак, трудоемкость произвольной сортировки будет не меньше, чем log2(n!).

Т(n)≥ log2(n!)

Воспользовавшись формулой Стирлинга, имеем:

Т(n)≥ log2(n!)

поэтому их во внимание не принимаем данные величины пренебрежимо малы по сравнению с

Теорема доказана.

2.2 Быстрое умножение

2.4.1 Быстрое умножение чисел

При обычном умножении столбиком нам потребуется n2 операций, где n – количество разрядов чисел. Попробуем произвести умножение чисел быстрее. Для этого поступим следующим образом:

Пусть и – два n-разрядных числа (n=2k).

Разобьем их двоичную запись пополам, т.е. на два отрезка длины k:

, где

Рассмотрим умножение по обычным формулам:

(2.7)

При перемножении по (2.7) получаем рекуррентную формулу, для вычисления трудоёмкости:

.

Таким образом, в (2.7) четыре произведения и одно сложение. Попробуем обойтись меньшим количеством произведений для умножения двух чисел по формуле (2.7). Рассмотрим модификацию формулы (2.7)формулу (2.8).

Тогда (2.8)

При перемножении чисел по (2.8) нам потребуется 3 умножения и 4 действия сложения и вычитания. Итого получаем трудоемкость:

Т(n)= 3 T(n/2)+4n (2.9)

Временно забудем, что числа (a+b) и (c+d) могут быть не k-разрядные, а k+1-разрядные. Организуем процесс умножения двух n-разрядных чисел по формуле (2.8) следующим образом: на входе имеем два длинных числа. Каждое из них разобьем пополам, и получается, что нам нужно 3 раза перемножить числа вдвое меньшей разрядности. Каждое из этих чисел снова делим пополам и перемножаем по формуле (2.8). Подобная процедура дробления осуществляется до тех пор, пока в результате очередного разделения не

получатся одноразрядные числа, которые перемножаем по обычной таблице умножения.

Оценим трудоемкость подобных вычислений по формуле (2.8). Она оценивается по рекуррентной формуле(2.9).

Теорема 2.2: Если трудоемкость некоторого алгоритма задается формулой

где: k – целое число, k>1

β < log kα, β >0

α – oбычно целое ( хотя это необязательно),

то существует следующая оценка трудоемкости данного алгоритма:

Без доказательства.

Комментарии: Что делать, если происходит переполнение разрядов при вычислении по формуле (2.8)?

Предположим, что при сложении (при вычислении u) у нас получились не k, а (k+1)- разрядные числа, т.е. а и b имеют k+1 разряд.

Выделим старший разряд: а1, b1 = 0 или 1,но один из них обязательно равен 1.

Тогда произведение можно осуществить следующим образом:

(2.10)

В случае, когда возникает переполнение, перемножение k+1 разрядных чисел выполняется по формуле 2.10. В ней по-прежнему одно умножение 2b2) и одно сложение, которое может и не понадобиться. На трудоемкости (рекуррентная формула 2.9) это существенно не отражается:

Т(n)= 3 T(n/2)+4n (2.9′)

или Т(n)= 3 T(n/2)+5n

Согласно Теореме 2.2, на трудоемкости перемножения по формуле 2.8 (формула быстрого умножения) это не сказывается. Получаем:

T(n) ≈ nlog 3 ≈ n1,58 << n2