logo search
tsvpis

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

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

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

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

  2. При третьем проходе получаем упорядоченные восьмерки, и т.д., пока длина серии не станет равно количеству элементов массива (на 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 составляет T(n) = n log2n .

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

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

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

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

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

T(n) ≥ log2(n!)

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

данные величины пренебрежимо малы по сравнению с nlog2n,

поэтому их во внимание не принимаем

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