АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета
8.4. Краткая теория
В предыдущей лабораторной работе оба разбиравшихся метода сортировки рассматривать как "обменные" сортировки. В данном разделе описан метод, где обмен местами двух элементов представляет собой характернейшую особенность процесса. Изложенный ниже алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.
Сортировка методом прямого обмена (Пузырьковая сортировка).
Как в методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Будем рассмтривать массив из n элементов, причем не горизонтальный, а вертикальный, тогда элементы можно интерпритировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. Массив проходится (n-1) раз сверху вниз, при этом элементы попарно сравниваются, если нижний элемент меньше верхнего, то элементы переставляются.
Рассмотрим еще один метод сортировки. Все вышерассмотренные сортировки производились на статистических структурах без динамического выделения памяти. Однако в некоторых случаях сортировка может быть более эффективной, если для ее реализации использовать динамические структуры данных. Естественно, в этом случае усложняется сам алгоритм сортировки. Одним из таких методов является сортировка с помощью бинарного дерева.
В лабораторной работе № 3 были подробно рассмотрены алгоритмы создания и обхода сбалансированного бинарного дерева. Если сортируемые элементы являются целыми числами, и при занесении их в память машины они будут являтся ключами создаваемого сбалансированного бинарного дерева, то при обходе полученного дерева слева направо получим отсортированный по возрастанию массив.
Пусть в первоначально пустой массив заносятся последовательно поступающие элементы: 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86.
При обходе дерева слева - направо получаем отсортированный массив 20, 30, 35, 45, 60, 70, 82, 85, 86, 87, 88, 90. Элемент дерева заносится в массив при втором заходе в него (на рисунке вторые заходы показаны зелеными стрелками).
Алгоритмы создания и обхода слева направо в псевдокоде и на языке С++ упорядоченного бинарного дерева здесь не представлены, поскольку они подробно описаны в лабораторной работе № 3.