Метод древесной сортировки использует тот же подход, что и сортировка вставками.

При сортировке вставками каждой вставке предшествует поиск подходящего места. В типичном случае для поиска такого места требуется просмотреть примерно половину отсортированной части списка, а в наихудшем — всю эту часть. Этот этап можно ускорить с учётом того, что поиск места происходит в уже упорядоченной части списка. А что касается вставки, то её ускорить не получится. Ведь для того, чтобы освободить место для вставляемого элемента, придётся все элементы отсортированной списка, начиная с места вставки, переместить на одну позицию вправо. Таким образом, мы заключаем, что вставка нового элемента в список — дорогое удовольствие.

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

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

При древесной сортировке вместо массива используется другая структура данных, которая также, помимо самих элементов, содержит информацию об их порядке. И, в отличие от массива, добавление нового элемента в такую структуру происходит почти мгновенно. Естественно, платой за ускорение станут бо́льшие, чем при использовании массива, затраты памяти.

Как и следует из названия метода, подходящей структурой данных будет дерево, точнее упорядоченное двоичное (бинарное) дерево. Понятие бинарного дерева определим аксиоматически: бинарное дерево или пусто, или состоит из корня и двух ветвей, которые сами являются бинарными деревьями. Корень является ячейкой памяти для хранения элементов списка. Ветви дерева (если они есть), будем называть левым и правым поддеревьями.

Бинарное дерево называется упорядоченным, если:

На рисунке 18.6. «Упорядоченные бинарные деревья» показаны далеко не все возможные способы размещения шести элементов в упорядоченном бинарном дереве. Ветки, уходящие сверху вниз налево, означают «больше», а направо — «меньше или равно».

Добавление нового элемента в упорядоченное бинарное дерево становится тривиальным делом. Если дерево пусто, то добавляемый элемент становится его корнем. Если элемент меньше, чем корень дерева, он добавляется в левое поддерево. В противном случае добавление происходит в правое поддерево. Видно, что операция добавления нового элемента в непустое дерево сводится к добавлению в одно из поддеревьев, которые, конечно, и сами являются деревьями. Это наблюдение позволяют реализовать добавление рекурсивно.

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

Как только дерево будет построено, не составит труда получить его элементы в порядке неубывания. Чтобы получить все элементы дерева по порядку, нужно получить по порядку все элементы левого поддерева, затем получить корень дерева, а затем — по порядку элементы правого поддерева. Упорядоченность полученного списка гарантируется тем, что все элементы в левом поддереве меньше корня, а в правом — больше или равны. Операция получения упорядоченного списка элементов упорядоченного бинарного дерева тоже имеет рекурсивную природу.

В языке Perl отсутствует готовая к употреблению структура «упорядоченное бинарное дерево», поэтому придётся строить её самостоятельно на базе имеющихся. Самое простое решение — моделировать дерево как ссылку на трёхэлементный массив, в котором первый элемент предназначен для хранения данных (элементов списка). Второй и третий элементы будут хранить соответственно левое и правое поддеревья. Мы выбрали не массив, а ссылку на массив потому, что деревья могут размещаться как элементы массивов (для которых они являются поддеревьями). Массивы, как мы знаем, не могут быть элементами в других массивах, а ссылки — могут. Пустые деревья будут представляться как ссылки на пустые массивы.

Деревьям на рисунке 18.6, таким образом, в Perl соответствуют следующие структуры:

Теперь видно, какой ценой нам достанется быстродействие. Вместе с каждым элементом последовательности (корнем какого-то дерева) хранятся также две ссылки.

Видно также, что разные деревья, построенные для одного и того же набора элементов, не являются равноценными с точки зрения эффективности добавления в них новых элементов. Цепочка рекурсивных вызовов при добавлении нового элемента может иметь такую длину, какова высота дерева (которую было бы уместней назвать глубиной для деревьев, растущих вниз). Среди изображённых на рисунке среднее дерево является наилучшим, а дерево справа — наихудшим. В общем случае предпочтительнее деревья, у которых максимально заполнены все этажи, кроме, быть может, последнего. Максимально возможные количества элементов на этажах дерева равны $1$, $2$, $4$, $8$, так что максимальная вместимость $k$-этажного дерева равняется $1+2+4+\dots +2^{k-1}=2^k-1$ элементов (сумма геометрической прогрессии!). Поэтому для «хороших» $n$-элементных деревьев выполняются неравенства $2^{k-2}<n⩽2^{k-1}$, или $k-2<{\log }_{2}n⩽k-1$ (для тех, кто не знает: двоичный логарифм ${\log }_{2}n$ числа $n$ — это показатель степени, в которую нужно возвести двойку, чтобы получить $n$). Для «хороших» деревьев $k$ растёт крайне медленно с ростом $n$. Для «плохих», как видно на примере дерева справа на рисунке, $k=n$, и это никуда не годится.

Выходом из положения было бы построение из элементов списка так называемого сбалансированного дерева, у которого высоты левого и правого поддеревьев по возможности близки, и тем же свойством обладают оба поддерева. Ясно, что не во всех случаях удастся добиться равных по высоте поддеревьев, но можно пожелать, чтобы их высоты различались не больше, чем на единицу. Тогда после добавления нового элемента дерево придётся подвергнуть при необходимости ребалансировке, процедуре, которая сделает дерево более коренастым и вернёт утраченное свойство сбалансированности. Это, правда, усложнит структуру данных и алгоритмы работы с ней. Существует несколько вариантов деревьев с автоматической ребалансировкой. Среди них следует упомянуть AVL-деревья и красно-чёрные деревья.

Другой вариант — сразу строить дерево сбалансированным. Но для этого потребуется добавлять элементы в определённом порядке, а именно выбирая каждый раз из списка медиану. Медианой называется такой элемент, что количество элементов списка, меньших или равных медиане либо равно количеству больших или равных элементов, либо эти количества отличаются на единицу. К сожалению, изменить порядок добавления новых элементов бывает нелегко, особенно если список слишком большой, и к элементу, после того как он обработан, больше нет доступа (типичным примером является список строк, прочитанных из файла). Кроме того, поиск медианы — это задача не легче, чем сортировка списка. Ведь медианный элемент — это тот, который окажется в середине отсортированного списка (ну или рядом с серединой, если в списке чётное число элементов).

Медиану не следует путать со средним арифметическим элементов списка. Средняя температура по больнице не то же самое, что температура «среднего» пациента. Между прочим, вторая величина гораздо больше говорит об общем состоянии пациентов, чем первая. Так что отыскание медианы — очень даже насущная задача.

Мы выбираем третий, хорошо проторенный путь. Будем уповать на то, что подавляющее большинство из деревьев, содержащих элементы одного и того же списка, ближе к идеально сбалансированным, чем к вызывающе разбалансированным (это правда). Если список, подлежащий сортировке, составлен более-менее случайно, построенное дерево с большой вероятностью окажется невысоким. Увы, если сортировать список, уже упорядоченный по неубыванию или невозрастанию, мы как раз получим худший случай.

Другой подход к сортировке заключается в следующем. Извлечём из списка какой-нибудь элемент (проще всего — самый первый). Элемент при этом удаляется из списка. Такой элемент будем называть ключевым. Затем разделим получившийся список на два списка (назовём их левым и правым). В левый список отправятся элементы, строго меньшие ключевого элемента, а в правый — большие или равные ключевому. Затем отсортируем левый и правый списки и соединим их вместе, вставив между ними ключевой элемент. Для сортировки левого и правого списков используем тот же самый подход, что наводит на мысль о рекурсии.

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

Умные люди смутно догадываются, что в языке Perl, в котором так много встроенных процедур в том числе и для обработки списков, имеется готовое решение для сортировки. Так оно и есть.

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

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