Сортировка данных

Деревья

Конечное корневое дерево Т формально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m ³ 0 поддеревьев Т1, Т2, …, Тm.

Узлы, не имеющие поддеревьев, называют листьями, остальные узлы называются внутренними узлами.

Рис. 9.9. Дерево с 11 узлами

Узлы D, E, F, H, J, K — листья, А — корень, остальные — внутренние.

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

В описании соотношений между узлами дерева будем использовать терминологию генеалогических деревьев. Т.е. говорим, что в дереве (или поддереве) все узлы, являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Далее корень будем именовать отцом корней его поддеревьев, которые в свою очередь будем называть сыновьями корня. Например, на рис. 9.7 узел А является отцом узлов B, G, I; J и K — сыновья I, а C, E и F — братья и т.д.

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

считаются различными.

Определим лес как упорядоченное множество деревьев.

Важной разновидностью деревьев является класс бинарных деревьев. Бинарное дерево Т либо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого Tl и правого Tr.

Бинарные деревья, вообще говоря, не являются подмножеством множества

деревьев, они полностью отличаются своей структурой, поскольку есть разные бинарные деревья.

Различие между бинарным деревом и деревом состоит в том, что не бинарное дерево не может быть пустым, и каждый узел не бинарного дерева может иметь произвольное число поддеревьев. В то же время бинарное дерево может быть пустым и каждая его вершина может иметь 0, 1 или 2 поддерева, также существует различие между левым и правым поддеревьями.

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

Пусть имена x1, …, xn заданы в виде таблицы. Каждое имя xi принимает значение из пространства имен, на котором определен линейный порядок. Далее мы считаем, что никакие 2 имени не имеют одинаковых значений, т.е. любые xi, xj обладают тем свойством, что если i ¹ j, то либо xi предшествует xj, либо наоборот.

Ограничение xi ¹ xj при i ¹ j упрощает анализ без потери общности, т.е. корректность идей и алгоритмов не нарушается. Цель сортировки состоит в том, чтобы выполнить перестановку, для которой.

В задачах частичной сортировки требуется извлечь либо частичную информацию о П (например, Пi для нескольких значений i), либо полностью определить П по заданной частичной информации о ней.С каждой записью xi в последовательности x1, …, xn сопоставим некоторый ключ ‘k’. Ключом обычно является некоторое поле внутри записи. Говорят, что файл отсортирован по ключу, если для i < j следует, что ki предшествует kj при некоторой упорядоченной последовательности по ключам. В качестве примера рассмотрим телефонный справочник. Файл состоит из всех строчек этого справочника. Каждая строчка является записью. Ключом, по которому отсортирован этот файл, является поле фамилия в записи. Каждая запись содержит также поле для адреса и номера телефона.

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

Вполне возможно, что две записи в некотором файле имеют одинаковый ключ. Метод сортировки называется устойчивым, если для всех записей i и j таких, что k(i) = k(j), выполняется условие, что в отсортированном файле xi предшествует xj, если xi предшествует xj в первоначальном файле.

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

Пример.

а) первоначальный файл б) отсортированный файл

ключ	информация		ключ	информация
	DDD			AAA
	BBB			BBB
	AAA			CCC
	EEE			DDD
	CCC			EEE

Рис. 9.10. Сортировка записей по ключу

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

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

Рассмотрим некоторые из них.

Пример. Рассмотрим сортировку элементов массива {x1, x2, x3} с использованием бинарного дерева.

Рис. 9.11. Бинарное дерево решений для сортировки трех имен

В любом таком дереве решений каждая перестановка определяет единственный путь от корня к листу. Листья, соответствующие разным перестановкам, должны быть разными. Тогда ясно, что в дереве решений для сортировки n имен должно быть по крайней мере n! листьев (n! — количество перестановок из n).

Заметим, что высота дерева решений h равна числу сравнений, требующихся алгоритму в наихудшем случае.

Простая сортировка вставками

На этапе j имя xj вставляется на свое правильное место среди x1, x2, …, xn. При вставке xj временно размещается в ячейке X и просматриваются имена xj-1, xj-2, …, x1. Они сравниваются с Х и сдвигаются вправо, если обнаруживается, что они больше Х. Имеется фиктивное имя x0, значение которого –¥ служит для остановки просмотра слева.

Вставка

x0	x1	x2	x3	x4	x5
– ¥	8					j=2
– ¥	7					j=3
– ¥		7				j=4
– ¥			7			j=5
– ¥

Рис. 9.12. Простая сортировка вставками для пяти имен.

Пунктирные вертикальные линии таблицы разделяют уже отсортированную часть таблицы от еще не отсортированной.

Сортировка методом пузырька

Идея, лежащая в основе сортировки «методом пузырька» заключается в следующем. Файл просматривается несколько раз последовательно. Каждый просмотр состоит из сравнения каждого элемента xi файла со следующим за ним элементом xi+1 и «обмена» (транспозиции) этих элементов, если они располагаются не в нужном порядке.

Например, задан файл 25, 57, 48, 37, 12, 92, 86, 33. Требуется отсортировать записи, расположив их по возрастанию значений элементов файла. Действия сортировки оформим в виде таблицы.

Итерация	Файл
0	25, 57, 48, 37, 12, 92, 86, 33
	25, 48, 37, 12, 57, 86, 33, 92
	25, 37, 12, 48, 57, 33, 86, 92
	25, 12, 37, 48, 33, 57,86, 92
	12, 25, 37, 33, 48, 57, 86, 92
	12, 25, 33, 37, 48, 57, 86, 92

Эффективность «метода пузырька» считается следующим образом. Имеется в худшем случае n–1 просмотров файла и n–1 сравнений в каждом просмотре. Таким, образом, общее число сравнений равно (n–1) (n–1) = n2 – 2n +1, что составляет»n2.

Единственным плюсом «метода пузырька» является то, что для такой сортировки требуется мало дополнительного пространства (одна дополнительная запись для временного хранения той записи, для которой выполняется транспозиция, и несколько простых целых переменных).

Сортировка методом «турнира с выбыванием»

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

Такое дерево можно понимать следующим образом: Кейс играла в турнире с Гейл и проиграла, т.е. победила Гейл и ее имя помещается в узел дерева и т.д. То есть на представленном дереве показан турнир, в котором победила Гейл. А кто занял 2-е место? А 3-е место? Решение на основе просмотра дерева от листьев к корню позволяет сделать вывод, что 2-е место заняла Пэт, а Джордж с Фрэнком поделили 3-е место, т.е. Гейл выиграла 3 игры, а Пэт выиграла 2 игры, а Джорд с Фрэнком выиграли по 1 игре.

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

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

Пример. Задана последовательность чисел: 25, 57, 48, 37, 12, 92, 86, 33. Отсортировать ее методом «турнира с выбыванием».

Решение. Начинаем формировать дерево с листьев:

1 этап (в результате получили самое большое число 92. Его следует вывести из дерева.) 2 этап и т.д.