Справка:Пусть
дан массив , состоящий
из 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.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