§2. Алгоритм сортдерево

Оказывается, полученная оценка снизу для сложности алго­ритмов сортировки не может быть улучшена, а именно, сущест­вуют алгоритмы сортировки, имеющие сложность O(nlogn). Один из таких алгоритмов, называемый СОРТДЕРЕВО, мы сейчас раз­берем. Помимо того, что это полезный алгоритм упорядочения, к тому же теоретически наилучший, в нем используется интересная структура данных, полезная и в других ситуациях.

Алгоритм СОРТДЕРЕВО был предложен в 1964 году незави­симо Уильямсом (под названием Heapsort) и Флойдом (Treesort). Иногда, например, в [6], этот алгоритм называют алгоритмом пи­рамидальной сортировки.

В массиве А[1..n] введем структуру корневого двоичного де­рева. считая, что в корне находится элемент А[1], и элемент A[i] имеет двух сыновей: A[2i] (если 2i ≤ n) и A[2i+1] (если 2i+1 < n).- Такую структуру назовем двоичным деревом массива А.

Лемма 2.1. Двоичное дерево массива длины n имеет высоту .

□ Напомним (см. гл.2), что высота корневого дерева есть по определению длина самого длинного пути из корня до какого-нибудь листа. Например, на рис.3.2 это путь до листа, в котором находится число 7. Легко видеть, что длина этого пути равна 3.

Пусть k - высота двоичного дерена массива длины n. Для всех s < k в дереве имеется ровно 2^s вершин глубины s. Пусть h — количество вершин глубины k. Тогда справедливо неравен­ство 1 < h < 2^k. Поскольку число вершин равно n — длине масси­ва, то справедливо равенство:

n = 1 + 2 + ... + 2^k-1 + h = 2^k - 1 + h.

Учитывая, что h ≤ 2^k, получаем, что

n = 2^k - 1 + h ≤ 2^k - 1 + 2^k < 2^k+1.

Отсюда n < 2^k+1. С другой стороны, так как h ≥ 1, то

n= 2^k - 1 + h ≥ 2^k.

Таким образом, справедливо неравенство 2^k ≤ п ≤ 2^k+1. Отсюда, k ≤ logn ≤ k+1, то есть k = .

Двоичное дерево массива А называется сортирующим дере­вом массива А, если выполняются условия:

А[k] ≥ А[2 k] и А[k] ≥ А[2 k +1] для к = l,2,....(*)

Непосредственно из определения вытекает, что наибольший элемент массива находится в корне его сортирующего дерева. Легко видеть также, что двоичное дерево, изображенное на рис. 3.2, не является сортирующим.

Именно на представлении массива сортирующим деревом ос­нован один из теоретически наилучших алгоритмов сортировки данных — СОРТДЕРЕВО. Изложим вначале основные принципы работы этого алгоритма.

На первом этапе элементы массива А переставляются так, чтобы выполнялось свойство (*) сортирующего дерева, иначе говоря, двоичное дерево массива А преобразуется в сортирую­щее. Процедуру, осуществляющую это преобразование, будем называть ПСД.

Затем, поскольку по свойству сортирующего дерева, элемент в корне, а именно, А[1] является наибольшим в А, то, переставляя А[1] и А[n], и удаляя А[n] из дерева, получим массив А[1..п-1] и A[n] = max А[1..n]. Теперь преобразуем А[1..n-1] в сортирующее дерево, затем переставим А[1] и А[n-1] и удалим А[n-1]. Процесс продолжается до тех пор, пока в сортирующем дереве не оста­нется один элемент. Тогда А[1],...,А[n] — упорядоченная по не­убыванию последовательность.

Перейдем к формальному описанию алгоритма СОРТДЕРЕ­ВО. Начнем с описания процедуры ПСД (построение сортирующего дерева). В его основе лежит рекурсивная процедура ПЕРЕ­СЫПК(i,j), имеющая параметры i и j. Они задают область ячеек массива А, которая в результате процедуры ПЕРЕСЫПКА будет обладать свойством сортирующего дерева, при этом его корень помещается в вершину i.

Неформально можно сказать, что построение сортирующего дерева идет снизу вверх, начиная с листьев, и справа налево, строя при этом все большие и большие сортирующие поддеревья.

Действительно, все листья уже являются сортирующими под­деревьями. В общем случае, когда мы находимся в вершине i, поддеревья с корнями 2i и 2i+l уже являются сортирующими. Если выполняются неравенства

A[i] ≥ A[2i] и A[i] ≥ A[2i+1],

то дерево с корнем в i является сортирующим, и его построение с корнем в вершине i закончено.

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

Ниже дано формальное описание процедур ПЕРЕСЫПКА и ПСД. Без формального описания используется функция MAXCЫH(i), значением которой является тот сын i, который со­держит наибольший из элементов A[2i] и A[2i+1],

Структура этой процедуры следующая. В строке 2 осуществ­ляется проверка, является ли узел с номером i листом или нет. В строке 4 проверяется условие (*) для дерева с корнем в узле с номером i, и если оно не выполнено, то переставляется элемент в корне дерева с наибольшим из элементов в его сыновьях, и вновь вызывается процедура ПЕРЕСЫПКА, но уже с другим парамет­ром.

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

1. begin

2. if i ≤ then (* если i — не лист *)

3. begin k := MAXCЫH(i);

4. if A[i] < A[k] then

5. begin

6. A[i]↔ A[k]; ПЕРЕСЫПКА(k,j)

7. end;

8. end;

9. end;

Процедура ПСД, строящая сортирующее дерево массива А, выглядит следующим образом.

procedure ПСД;

1. begin

2. for i := downto 1 do ПЕРЕСЫПКА(i,n)

3. end

Разберем пример, иллюстрирующий работу обеих этих процедур

Пусть задан числовой массив А[1…10]:

I	1	2	3	4	5	6	7	8	9	10
А[I]	2	3	6	1	4	5	8	0	7	9

Все перестановки элементов массива, осуществляемые проце­дурой ПЕРЕСЫПКА, будем отображать в двоичном дереве изме­няющегося массива. Для краткости, на схеме вместо ПЕРЕСЫП­КА(i,10) будем писать П(i).

Обращаем внимание на работу процедур П(2) и П(1). В проце­дуре П(2) вначале были переставлены числа 3 и 9 в деревеd), за­тем была вызвана процедура 11(5), которая переставила 3 и 4. Процедура П( 1) в дереве е) переставила 9 и 2. затем вызвала про­цедуру П(2), которая переставила 2 и 7 и вызвала П(4), но П(4) уже ничего не переставляла.

Изобразим окончательный результат в виде таблицы:

i	1	2	3	4	5	6	7	8	9	10
A[I]	9	7	8	2	4	5	6	0	1	3

Алгоритм упорядочения, основанный на понятии сортирую­щего дерева, может быть формально записан следующим обра­зом:

АЛГОРИТМ 3.2. СОРТДЕРЕВО

Данные: массив элементов А[1..n].

Результат: массив элементов А[1..n], упорядоченный по неубы­ванию, то есть А[1] ≤ А[2] ≤ ... ≤ А[n].

1. begin

2. ПСД; (* вначале строится сортирующее дерево *)

3. for i := n downto 2 do

4. begin

5. A[l] ↔ A[i];

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

7. end;

8. end

Продолжим рассмотрение ранее начатого примера.

На рис.3.4 дерево f) является сортирующим деревом исходно­го массива А, полученным в результате работы процедуры ПСД. Затем происходит перестановка А[1] и А[10] (дерево g) ). К дере­ву g) применяется процедура ПЕРЕСЫПКА(1,9), в результате которой число 3 проходит путь по правым ветвям из корня дере­ва до листа. Затем вновь происходит перестановка корня с лис­том и т.д. В результате получится массив А, упорядоченный по возрастанию.

Теорема 3.3. Алгоритм упорядочения СОРТДЕРЕВО имеет вычислительную сложность O(nlogn).

□ Естественно считать размером задачи сортировки длину массива элементов — n. Найдем вначале сложность процедуры ПСД. Пусть k — высота двоичного дерева исходного массива А. По лемме 3.1 имеем равенство к =, в частности, отсюда следует, что 2^k ≤ n.

Через T(k-i) обозначим сложность процедуры ПЕРЕСЫПКА, выполняемой из всех вершин глубины k-i. Тогда сумма Σ = Т(k-1) + Т(k-2) + ... +Т(0) равна сложности всей процедуры, строящей сортирующее дерево, поскольку ПЕРЕСЫПКА начнет выполняться с вершин глубины k-1.

Пусть вершина i имеет глубину k-1 и (возможно) двух сыно­вей: 2i и 2i+l. Пересыпка из вершины заключается в сравнении трех чисел: A[i], A[2i], A[2i+1] и, если это необходимо, переста­новки A[i] с наибольшим из A[2i] и A[2i+1], Ясно, что сложность пересыпки из вершины i не зависит от п и оценивается сверху константой с. Тогда справедливо неравенство

Т(k — 1) ≤ с 2^k-1,

так как имеется ровно 2^k-1 вершина глубины k-1. Переходя на более высокий уровень, т.е. рассматривая вершины глубины k-2, заметим, что справедливо неравенство

Т(к - 2) ≤ с 2^k-2 + 1/2 Т(k — 1),

так как после сравнения этого элемента в вершине глубины k-2 с элементами в ее сыновьях дальнейшая пересыпка пойдет только не более, чем из одного сына. Аналогично,

T(k - i) ≤ с 2^k-1 + 1/2 Т(к - i + 1) для всех i ≤ k.

Отсюда, Σ = Т(k - 1) + Т(k - 2) +...+ Т(0) ≤ с 2^k-1 + с 2^k-2 +...+ с + +1 /2 Т(k - 1) + 1 /2 Т(k - 2)+...+1 /2 Т(1) ≤ с (2^k-1 +2^k-2+...+1)+1 /2Σ. Значит, Σ ≤ с (2^k-1 + 2^k-2 +...+1) < 2с 2^k < 2 с n, так как 2^k ≤ n.

Итак, доказано неравенство: Σ ≤ 2сn. Это означает, что слож­ность процедуры ПСД есть О(n), то есть она линейна.

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

Отсюда, сложность цикла в строках 3-7 есть O(nlogn). Окон­чательно, сложность алгоритма СОРТДЕРЕВО есть О(n) + O(logn) = O(nlogn). □

ЗАДАЧИ

1. (Алгоритм БЫСТРОСОРТ) Заданную последовательность элементов S = {а₁,а₂,...,а_n} можно упорядочить следующим обра­зом. Выбрать произвольный элемент а, разбить S на три последо­вательности S₁, S₂, соответственно меньших а, равных а и больших а. Затем повторить ту же процедуру к S₁ и к S₃ . Напишите на упрощенном Паскале рекурсивную и нерекур­сивную версии этого алгоритма. Докажите, что его сложность есть O(n²). Несмотря на то, что сложность алгоритма БЫСТРОСОРТ есть O(n²), то есть хуже, чем у алгоритма СОРТДЕРЕВО, БЫСТРО­СОРТ предпочтительней, вообще говоря, с точки зрения практи­ки. Дело в том, что сложность вычисляется в худшем случае, од­нако в среднем БЫСТРОСОРТ имеет сложность O(nlogn). Понятие сложности в среднем изложено в книге [6], там же дано де­тальное описание как рекурсивной, так и нерекурсивной версий этого алгоритма.

2. а) (Сортировка обменами) Последовательным просмотром элементов а₁,...,а_n найти первое к такое, что а_k > а_k+1. Поменять а_k и а_k+1 возобновить просмотр последовательности, начиная с а_k+1 и так далее. В результате наибольший элемент передвинется на последнее место. Следующие просмотры начинать с а₁ уменьшая на единицу количество просматриваемых элементов. Последова­тельность будет упорядочена после просмотра, в котором либо не произошло ни одной перестановки, либо участвовали первый и второй элементы.

б) (Сортировка простыми вставками) Просматривать последо­вательно а₂,...,а_n, и каждый новый элемент а_k вставлять на подхо­дящее место в уже упорядоченную последовательность a₁,...,a_k-1. Это место определяется последовательным сравнением а_k с эле­ментами a₁,...,a_k-1.

Напишите на упрощенном Паскале алгоритмы сортировки обменами и простыми вставками. Докажите, что сложности этих алгоритмов — О(n²).

3. Исследовать число сравнений и число перестановок эле­ментов a₁,...,a_n для алгоритмов сортировки выбором, обменами и простыми вставками. Докажите, что число перестановок в алго­ритме сортировки выбором есть О(n). В то же время и число сравнений для сортировки выбором, и обе указанные характери­стики для сортировок обменами и простыми вставками есть O(n²).

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

Например, такая ситуация имеет место в задаче: упорядочить строки заданной матрицы размером nm в порядке неубывания первых элементов.

4. Даны пять попарно различных чисел: а, b, с, d, е. Упоря­дочить их по возрастанию, используя для этого не более семи сравнений.

5. (Сортировка вычерпыванием). Дана последовательность целых чисел a₁,a₂,...,a_n, заключенных между 0 и m-1. Если т не очень велико, то ее можно упорядочить следующим образом:

1. Организуем m пустых очередей: по одной для каждо­го целого числа от 0 до m-1.

2. Последовательно просматривая исходную последова­тельность a₁,a₂,...,a_n, помещаем элемент а_k в очередь с номером k.

3. Сцепим очереди (содержимое (k+1)-ой очереди при­пишем к концу k-ой очереди). В результате получим упорядоченную по возрастанию последовательность.

Докажите, что этот алгоритм имеет сложность О(п).

6. Пусть двоичное дерево массива А[1..n] является его сор­тирующим деревом, и все А[k] попарно различны. Как найти второй по величине элемент этого массива? А третий? Какую глубину может иметь в сортирующем дереве вершина, содержа­щая k-ый по величине элемент массива А?