В своем новом положении элемент 4 обладает сыновьями 10 и 5. Так как они больше 4, то 4 переставляется с 10, большим сыном. После этого сыновьями элемента 4 в новом положении становятся 1 и 2. Поскольку 4 превосходит их обоих, дальнейшие перестановки не нужны.

Рисунок 3.6. а -- результат перестановки элементов 4 и 16 в сортирующем дерев

Рисунок 3.6; б -- результат перестройки сортирующего дерева и удаления элемента 16.

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

Теперь перейдем к формальному описанию алгоритма Сорт-деревом.

Пусть аг, а2, . . ., ап -- последовательность сортируемых эле-ментов. Предположим, что вначале они помещаются в массив А именно в этом порядке, т. е. A[i] = a,1in. Первый шаг состоит в построении сортирующего дерева, т. е. элементы в А перераспре-деляются так, чтобы удовлетворялось свойство сортирующего де-рева: A[i]A[2i] при 1 i n/2 и A[i]A[2i+1] при 1in/2. Это делают, строя, начиная с листьев, все большие и большие сор-тирующие деревья. Всякое поддерево, состоящее из листа, уже яв-ляется сортирующим. Чтобы сделать поддерево высоты h сортирую-щим, надо переставить элемент в корне с наибольшим из элементов, соответствующих его сыновьям, если, конечно, он меньше какого-то из них. Такое действие может испортить сортирующее дерево высоты h -- 1, и тогда его надо снова перестроить в сортирующее. Приведем точное описание этого алгоритма.

Алгоритм 3.3. Построение сортирующего дерева

Вход. Массив элементов A[i], 1i n

Выход. Элементы массива А, организованные в виде сортирую-щего дерева, т. е.A[i]A[] для 1<in.

Метод. В основе алгоритма лежит рекурсивная процедура пересыпка. Ее параметры i и j задают область ячеек массива А, обладающую свойством сортирующего дерева; корень строящегося дерева помещается в i.

procedure ПЕРЕСЫПКА ((i,j):

1. if i -- не лист и какой-то его сын содержит элемент, пре-восходящий элемент в i then begin

2. пусть k-- тот сын узла i, в котором хранится

наибольший элемент;

переставить А[i] и А[k];

ПЕРЕСЫПКА (k,j)

end

Параметр j используется, чтобы определить, является ли i листом и имеет он одного или двух сыновей. Если i > j/2, то i -- лист, и процедуре ПЕРЕСЫПКА(i,j) ничего не нужно делать, поскольку А[i] -- уже сортирующее дерево.

Алгоритм, превращающий весь массив А в сортирующее дерево, выглядит просто:

procedure ПОСТРСОРТДЕРЕВА:

for i п1) stер --1 until 1 do ПЕРЕСЫПКА (i,n)

Покажем, что алгоритм 3.3 преобразует А в сортирующее дере-во за линейное время.

Лемма 3.2. Если узлы i+1, i+2, . . ., n являются корнями сор-тирующих деревьев, то после вызова процедуры ПЕРЕСЫПКА (i, п) все узлы i, i+1, . . ., п будут корнями сортирующих деревьев.

Доказательство. Доказательство проводится возврат-ной индукцией по I.

Базис, т. е. случай i=п, тривиален, так как узел п должен быть листом и условие, проверяемое в строке 1, гарантирует, что ПЕ-РЕСЫПКА (п, п) ничего не делает.

Для шага индукции заметим, что если i -- лист или у него нет сына с большим элементом, то доказывать нечего (как и при обо-сновании базиса). Но если у узла i есть один сын (т. е. если 2i=n) и A[i]<A[2i], то строка 3 процедуры ПЕРЕСЫПКА переставляет А[i] и А[2i]. В строке 4 вызывается ПЕРЕСЫПКА (2i, n); поэто-му из предположения индукции вытекает, что дерево с корнем 2i будет переделано в сортирующее. Что касается узлов i+1, i+2, . . . . . ., 2i -- 1, то они и не переставали быть корнями сортирующих деревьев. Так как после этой новой перестановки в массиве А вы-полняется неравенство A[i]>A[2i], то дерево с корнем i также оказывается сортирующим.

Аналогично, если узел i имеет двух сыновей (т. е. если 2i+1n) и наибольший из элементов в А [2i] и в А [2i+1] больше элемента в A [i], то, рассуждая, как и выше, можно показать, что после вызова процедуры ПЕРЕСЫПКА(i,n) все узлы i, i+1,..., n будут кор-нями сортирующих деревьев.

Теорема 3.5. Алгоритм 3.3 преобразует А в сортирующее дере-во за линейное время.

Доказательство. Применяя лемму 3.2, можно с по-мощью простой возвратной индукции по i показать, что узел i становится корнем какого-нибудь сортирующего дерева для всех i, 1in

Пусть Т (h) -- время выполнения процедуры ПЕРЕСЫПКА на узле высоты h. Тогда Т (h)Т (h -- 1)+с для некоторой постоянной с. Отсюда вытекает, что Т (h) есть О (h).

Алгоритм 3.3 вызывает процедуру ПЕРЕСЫПКА, если не счи-тать рекурсивных вызовов, один раз для каждого узла. Поэтому время, затрачиваемое на ПОСТРСОРТДЕРЕВА, имеет тот же поря-док, что и сумма высот всех узлов. Но узлов высоты i не больше, чем . Следовательно, общее время, затрачиваемое процедурой ПОСТРСОРТДЕРЕВА, имеет порядок in/2, т.е O(n)

Теперь можно завершить детальное описание алгоритма СОРТДЕРЕВОМ. Коль скоро элементы массива А преобразованы в сор-тирующее дерево, некоторые элементы удаляются из корня по од-ному за раз. Это делается перестановкой А[1] и А[n] и последую-щим преобразованием A[1], А[2], ..., А[n - 1] в сортирующее дерево. Затем переставляются А[1] и А[n - 1], а A[1], А[2], ..., А [п - 2] преобразуется в сортирующее дерево. Процесс продол-жается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда А[1], А[2], ..., А[n] -- упорядоченная последова-тельность.

Алгоритм 3.4. Сортдеревом

Вход. Массив элементов А[i], 1in.

Выход. Элементы массива А, расположенные в порядке неубы-вания.

Метод. Применяется процедура ПОСТРСОРТДЕРЕВА, т. е. алгоритм 3.3. Наш алгоритм выглядит так:

begin

ПОСТРСОРТДЕРЕВА;

For in step -1 until 2 do

Begin

переставить А[1] и А[i];

ПЕРЕСЫПКА(i,i - 1)

End end

Теорема 3.6. Алгоритм 3.4 упорядочивает последовательность из п элементов за время 0(n log п).

Доказательство. Корректность алгоритма доказывает-ся индукцией по числу выполнений основного цикла, которое обозначим через m. Предположение индукции состоит в том, что по-сле m итераций список A[n-m+1], ..., А [n] содержит m наи-больших элементов, расположенных в порядке неубывания, а спи-сок A[1], ..., А[n-m] образует сортирующее дерево. Детали до-казательства оставляем в качестве упражнения. Время выполнения процедуры ПЕРЕСЫПКА(1, i) есть 0(log i)- Следовательно, ал-горитм 3.4 имеет сложность О (n log i ).

Следствие. Алгоритм Сортдеревом имеет временную сложность O(nlog n)

3.5. БЫСТРСОРТ -- УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ О(n log n)

До сих пор мы рассматривали поведение сортирующих алгорит-мов только в худшем случае. Для многих приложений более реа-листичной мерой временной сложности является усредненное вре-мя работы. В случае сортировки с помощью деревьев решений мы видим, что никакой сортирующий алгоритм не может иметь сред-нюю временную сложность, существенно меньшую n 1оg n. Однако известны алгоритмы сортировки, которые работают в худшем слу-чае сn2 времени, где с -- некоторая постоянная, но среднее время работы, которых относит их к лучшим алгоритмам сортировки. При-мером такого алгоритма служит алгоритм Быстрсорт, рассматривае-мый в этом разделе.

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

Общий метод состоит в том, чтобы поставить в соответствие каж-дому листу v дерева решений вероятность быть достигнутым при данном входе. Зная распределение вероятностей на входах, можно найти вероятности, поставленные в соответствие листьям. Таким образом, можно определить среднее число сравнений, производи-мых данным алгоритмом сортировки, если вычислить сумму взятую по всем листьям дерева решений данного алгоритма, в ко-торой рi -- вероятность достижения i-го листа, а d, - его глубина. Это число называется средней глубиной дерева решений. Итак, мы пришли к следующему обобщению теоремы 3.4.

Теорема 3.7. В предположении, что все перестановки п-элементной последовательности появляются на входе с равными вероят-ностями, любое дерево решений, упорядочивающее последователь-ность из п элементов, имеет среднюю глубину не менее log n!.

Доказательство. Обозначим через D (Т) сумму глубин листьев двоичного дерева Т. Пусть D (Т) -- ее наименьшее значение, взятое по всем двоичным деревьям Т с m листьями. Покажем индук-цией по m, что D(m)m log m.

Базис, т. е. случай /п=1, тривиален. Допустим, что предположе-ние индукции верно для всех значений m, меньших k. Рассмотрим дерево решений Т с и листьями. Оно состоит из корня с левым подде-ревом Т с k листьями и правым поддеревом T с k - 1 листьями при некотором i, 1ik. Ясно, что

D(T)=i+D(T)+(k-i)+D(T)

Поэтому наименьшее значение D (Т) дается равенством

D(k)= [k+D(i)+D(k-1)]. (3.1)

Учитывая предположение индукции, получаем отсюда

D(k)k+[i log i+(k-i)log(k-i)] (3.2)

Легко показать, что этот минимум достигается при i=k/2. Сле-довательно, D(k)k+k log =k log k

Таким образом, D (m)m log m для всех m1.

Теперь мы утверждаем, что дерево решений Т, упорядочивающее n случайных элементов, имеет не меньше /г! листьев. Более того, в точности п\ листьев появляются с вероятностью 1/n! каждый, а остальные -- с вероятностью 0. Не изменяя средней глубины дерева Т можно удалить из него все узлы, которые являются предками только листьев вероятности 0. Тогда останется дерево Т' с n! листь-ями, каждый из которых достигается с вероятностью 1/п!. Так как D(Т')n! log n!, то средняя глубина дерева Т' (а значит, и Т) не меньше (1/n!) n! log n! = log n!.

Следствие. Любая сортировка с помощью сравнений выполняет в среднем не менее сп log n сравнений для некоторой постоянной с>0.

Заслуживает упоминания эффективный алгоритм, называемый Быстрсорт, поскольку среднее время его работы, хотя и ограничено снизу функцией сn lоg n для некоторой постоянной с (как и у вся-кой сортировки с помощью сравнений), но составляет лишь часть времени работы других известных алгоритмов при их реализации на большинстве существующих машин. В худшем случае Быстрсорт имеет квадратичное время работы, но для многих приложений это не существенно.

Procedure БЫСТРСОРТ(S):

if S содержит не больше одного элемента then return S

else

begin выбрать произвольный элемент a из S;

пустьS1, S2 и S3 -- последовательности элементов из S,

соответственно меньших, равных и больших а;

return (БЫСТРСОРТ(S1), затем S2, затем БЫСТРСОРТ (S3))

end

Рисунок 3.7. Программа Быстрсорт.

Алгоритм 3.5. Быстрсорт

Вход. Последовательность S из n элементов aь a2, ... , aп.

Выход. Элементы последовательности S, расположенные по порядку.

Метод. Рекурсивная процедура БЫСТРСОРТ определяется на рис. 3.7. Алгоритм состоит в вызове БЫСТРСОРТ(S).

Теорема 3.8. Алгоритм 3.5. упорядочивает последовательность из п элементов за среднее время О (п log п).

Доказательство. Корректность алгоритма 3.5 доказы-вается прямой индукцией по длине последовательности S. Чтобы проще было анализировать время работы, допустим, что все элементы в S различны. Это допущение максимизирует размеры последова-тельностей S1 и S3, которые строятся в строке 3, и тем самым мак-симизирует среднее время, затрачиваемое в рекурсивных вызовах в строке 4. Пусть Т (n) -- среднее время, затрачиваемое алгоритмом БЫСТРСОРТ на упорядочение последовательности из n элементов. Ясно, что Т(0)=Т(1)=b для некоторой постоянной b.

Допустим, что элемент а, выбираемый в строке 2, является 1-м наименьшим элементом среди n элементов последовательности S. Тогда на два рекурсивных вызова БЫСТРСОРТ в строке 4 тратится среднее время Т(i - 1) и Т (n - i) соответственно. Так как i равно-вероятно принимает любое значение между 1 и n, а итоговое по-строение последовательности БЫСТРООРТ(S) очевидно занимает время cn для некоторой постоянной с, то

T(n)cn+[T(i-1)+T(n-1)] для n2 (3.3)

Алгебраические преобразования в (3.3) приводят к неравенству

T(n)cn+T(i) (3.4)

Покажем, что при n2 справедливо неравенство Т (n)<kn 1n n, где k=2с+2b и b=Т(0)=T(1). Для базиса (n=2) неравенство Т(2)2с+2b непосредственно вытекает из (3.4). Для проведения шага индукции запишем (3.4) в виде

Страницы: 1, 2, 3