Добавлен: 16.05.2023
Просмотров: 72
Скачиваний: 3
Еще один способ усовершенствования – выполнять несколько перестановок за проход. Например, при движении вниз по массиву элемент (пусть он будет назван K) может сменить свою позицию не один раз, прежде чем займет нужное место. Можно сэкономите время, если он не будет передвигаться его по массиву, а сохранится во временной переменной и, при смещении других элементов вверх, будет найдена целевая позиция для K.
Предположим, что в массиве содержится наибольший элемент L, который стоит не на своем месте. Двигаясь вниз, алгоритм добирается до него (возможно, совершая другие перестановки) и затем перемещает вниз по списку, пока тот не достигнет конечной позиции. Во время последнего прохождения по массиву ни один элемент не может встать после L, поскольку этот элемент уже находится на нужном месте. Значит, алгоритм может остановиться, когда достигнет элемента L.
Если обобщить вышесказанное, получается, что алгоритм завершает прохождение через массив, добравшись до позиции последней перестановки, которую выполнил во время предыдущего прохождения. Таким образом, отследив последние перестановки при движении вниз и вверх по массиву, вы можете сократить путь. Рассмотренные усовершенствования проиллюстрированы на рисунке 4.
На крайнем левом фрагменте видно, что во время первого прохождения вниз по массиву алгоритм вставляет элемент 7 во временную переменную и меняет местами с элементами 4, 5, 6 и 3. Другими словами, алгоритму не требуется хранить элемент 7 в массиве до тех пор, пока он не займет конечную позицию.
Разместив 7 должным образом, алгоритм продолжает движение по массиву и не находит других элементов для перестановки. Теперь ему известно, что 7 и следующие за ним элементы стоят в своих конечных позициях и рассматривать их больше не нужно. Если бы какой-нибудь элемент, расположенный ближе к верху массива, оказался больше 7, то при первом же прохождении он переместился бы вниз, минуя 7.
На среднем фрагменте элементы на конечных позициях закрашены серым – во время последующих прохождений они не нуждаются в проверке.
На крайнем правом фрагменте алгоритм совершает второе прохождение по массиву вверх, начиная с элемента, стоящего перед 7. В нашем случае это 3. Алгоритм меняет его местами с элементами 6, 5 и 4, удерживая во временной переменной, пока не поставит на конечную позицию. Теперь 3 и предшествующие ему элементы находятся на своих местах – они закрашены серым цветом. Последнее прохождение осуществляется вниз по массиву, начиная со значения 4 и заканчивая значением 6. Во время него перестановки не выполняются, и алгоритм останавливается.
Рисунок 4 – Усовершенствованный алгоритм
Такие усовершенствования на практике ускоряют пузырьковую сортировку (время сортировки 10 000 элементов ускоряется в 4-5 раз). Но все же время работы подобного алгоритма остается O(), то есть он применим для списков с ограниченным размером.
Алгоритмы O(n log(n)) намного быстрее алгоритмов O(), по крайней мере, при работе с большими массивами. Например, если n = 1000, то время работы O(n log(n)) покажет результат 1 x , а – 1 x , то есть примерно в 100 раз больше. Такая разница в скорости делает алгоритмы первого рода более полезными на практике.
Пирамидальная сортировка подходит для работы с полными бинарными деревьями в массиве. В ней используется структура данных, называемая кучей.
Бинарное дерево – это дерево, в котором каждая вершина соединена с хотя бы двумя дочерними записями. Если все его уровни заполнены, кроме, возможно, последнего (где все вершины сдвинуты влево), то такое дерево называется полным.
На рисунке 5 показано полное бинарное дерево с 12 вершинами: первые три уровня полные, четвертый содержит пять вершин, сдвинутых влево.
Рисунок 5 – Бинарное дерево
Полные бинарные деревья легко сохранить в массив: присвойте корневому узлу индекс 0, а дочерним записям любого узла с индексом i — индексы 2i + 1 и 2i + 2 и т. д.
Если узлу присвоен индекс j, то родительская запись для него будет иметь индекс |(j – 1)/2|, где | | - означают округление результата до следующего меньшего целого числа. Например, |2,9| = 2 и |2| = 2.
На рисунке 6 показано дерево (рис. 5), переведенное в массив. Сверху указаны входные индексы. Так, узлу 6 присвоен индекс 4. Значит, его дочерние записи 5 и 12 будут иметь индексы 4 х 2 + 1 = 9 и 4 х 2 + 2 = 10 соответственно.
Рисунок 6 – Дерево, переведённое в массив
Если индекс какой-либо дочерней записи превышает наибольший индекс массива – такой записи в дереве нет. Например, узел 9 имеет индекс 5, тогда его дочерняя запись справа должна носить индекс 2 х 5 + 2 = 12. Но это число выходит за пределы массива, и если посмотреть на рисунок 5, то можно убедиться, что у элемента со значением 9 справа дочерней записи нет. Рассмотрим также получение индекса родительской записи для элемента со значением 12, которому присвоен индекс 10.
Согласно вышеприведенной формуле, родительская запись должна иметь индекс |(10 – 1)/2| = |4,5| = 4. В массиве ему соответствует элемент 6. На нашем дереве (рис. 5) это и есть родительский узел для вершины со значением 12.
Двоичная куча (рис. 7) – это полное бинарное дерево, где каждая вершина содержит значение, которое не меньше тех, что находятся в его дочерних записях. На рисунке 5 изображена не куча. Если взять для примера корневой узел 7, можно заметить, что его правая дочерняя запись имеет значение 10, то есть она больше родительской.
Рисунок 7 – Двоичная куча
На рисунке 8 показан процесс, в ходе которого к дереву, изображенному на рисунке 7, добавляют новую запись 12. Обновленную кучу можно увидеть на рисунке 9.
Рисунок 8 – Добавление нового элемента в кучу
Рисунок 9 – Новая куча
Если куча хранится в массиве, ее обновление выполнить еще проще. Очередной элемент, присоединяемый к концу дерева, автоматически занимает соответствующую позицию в массиве.
Следующий псевдокод превращает массив в кучу.
Листинг 4 – Псевдокод образования кучи
MakeHeap(Data: values[])
// Добавляем каждый элемент в кучу (по одному).
For i = 0 To <количество значений> - 1
// Начинаем с нового элемента и работаем до корня.
Integer: index = i
While (index != 0)
// Находим индекс родительской записи.
Integer: parent = (index - 1) / 2
// Если дочерняя запись меньше или равна родительской,
// мы закончили и выходим из цикла While.
If (values[index] <= values[parent]) Then Break
// Меняем местами родительскую и дочернюю записи.
Data: temp = values[index]
values[index] = values[parent]
values[parent] = temp
// Переходим к родительской записи.
index = parent
End While
Next i
End MakeHeap
Кучи хороши для создания очередей с приоритетом, поскольку чем больше элемент в дереве, тем ближе он к корневому узлу. Следовательно, при удалении элемента из очереди достаточно убрать тот, что является корневым. К сожалению, такая операция разрушает пирамидальную структуру кучи. Но ситуацию легко исправить, если переместить последний элемент дерева в корень. На следующем этапе понадобится восстановить основное свойство кучи. Для этого можно использовать тот метод, который фигурирует и при построении: если новое значение меньше какого-то дочернего, поменяйте их местами. Исправив текущий узел, проверьте тот, что идет на уровень ниже. Продолжайте перестановку узлов вниз по дереву, пока не найдете точку, в которой свойство кучи уже будет выполненным, либо не достигните конца дерева.
В следующем псевдокоде представлен алгоритм удаления элемента из кучи и восстановления ее основного свойства.
Листинг 5 – Псевдокод удаление элемента из кучи
Data: RemoveTopItem (Data: values[], Integer: count)
// Сохраняем верхний элемент, чтобы вернуться к нему позднее.
Data: result = values[0]
// Перемещаем последний элемент к корню.
values[0] = values[count - 1]
// Восстанавливаем свойство кучи.
Integer: index = 0
While (True)
// Находим индексы дочерних записей.
Integer: child1 = 2 * index + 1
Integer: child2 = 2 * index + 2
// Если индекс дочерней записи выпадает из дерева,
// используем индекс родительской записи.
If (child1 >= count) Then child1 = index
If (child2 >= count) Then child2 = index
// Если свойство кучи выполнено,
// мы закончили и выходим из цикла While.
If ((values[index] >= values[child1]) And
(values[index] >= values[child2])) Then Break
// Получаем индекс дочерней записи с большим значением.
Integer: swap_child
If (values[child1] > values[child2]) Then
swap_child = child1
Else
swap_child = child2
// Меняем местами с большим дочерним элементом.
Data: temp = values[index]
values[index] = values[swap_child]
values[swap_child] = temp
// Переходим на дочернюю ветку.
index = swap_child
End While
// Возвращаем значение, которое удалили из корня.
return result
End RemoveTopItem
Приведенный алгоритм в качестве параметра берет размер дерева, поэтому он может найти место, где заканчивается куча внутри массива. Значение сохраняется в корневом узле, чтобы потом была возможность к нему вернуться. Затем последний элемент дерева перемещается к корневому узлу. Для этого алгоритм назначает индексу корневого узла переменную index и вводит бесконечный цикл While. Внутри цикла алгоритм рассчитывает индексы дочерних записей текущего узла. Если они оба выпадают из дерева, то их значения приравниваются к родительскому. В таком случае дальнейшее сравнение индекса происходит с самим собой.
А поскольку любое значение больше или равно самому себе, подобный подход удовлетворяет свойству кучи и недостающий узел не заставляет алгоритм менять значения местами. После того как алгоритм рассчитает дочерние индексы, он проверяет, сохраняется ли свойство кучи в текущем месте. Если да, то алгоритм покидает цикл While.
То же самое происходит, если нет обеих дочерних записей или в отсутствии одной из них другая соответствует свойству кучи. Если свойство кучи не выполняется, алгоритм устанавливает swap_child на индекс дочерней записи, содержащий большее значение, и меняет местами значения родительского и дочернего узлов. Затем он обновляет переменную index, чтобы сдвинуть ее вниз к переставленному дочернему узлу, и продолжает спускаться по дереву.
Теперь, после описания кучи, следует рассмотреть алгоритм сортировки. Приведенный ниже алгоритм строит кучу. Он несколько раз меняет ее первый и последний элементы местами и перестраивает все дерево, исключая последний элемент. При каждом прохождении один элемент удаляется из кучи и добавляется в конец массива, где расположены элементы в отсортированном порядке.
Листинг 6 – Псевдокод сортировки
Heapsort(Data: values)
<Преобразуем массив в кучу.>
For i = <количество значений> - 1 To 0 Step -1
// Меняем местами корневой и последний элементы.
Data: temp = values[0]
values[0] = values[i]
values[i] = temp
<Определяем элемент в позиции i, который нужно удалить из
кучи. Теперь куча содержит i - 1 элементов. Опускаем значение
нового узла вниз, чтобы восстановить свойство кучи.>
Next i
End Heapsort
Представленный алгоритм начинает свою работу с того, что превращает массив в кучу. Затем он несколько раз удаляет верхний элемент, самый большой и перемещает его в конец кучи. Количество элементов в куче при этом сокращается и восстанавливается ее основное свойство, а переставленный элемент занимает правильную позицию в конце кучи.
На завершающем этапе алгоритм удаляет элементы из кучи в порядке от наибольшего к наименьшему и помещает их в конец постоянно сокращающейся кучи. Массив продолжает содержать значения в порядке возрастания. Объем памяти, требуемый для пирамидальной сортировки, легко рассчитать. Алгоритм хранит все данные внутри исходного массива и использует лишь определенное количество дополнительных переменных для расчета значений и их перестановки. Если в массиве содержится n значений, алгоритм использует O(n) памяти.
Сложнее определить время работы алгоритма. Чтобы построить исходную кучу, ему приходится прибавлять каждый элемент к растущей куче. Всякий раз он размещает его в конце дерева и просматривает структуру данных до самого верха, чтобы убедиться, что она является кучей. Поскольку дерево полностью бинарное, количество его уровней равно O(log(n)). Таким образом, передвижение элемента вверх по дереву может занять максимум O(log(n)) шагов. Алгоритм осуществляет шаг, при котором добавляется элемент и восстанавливается свойство кучи, n раз, поэтому общее время построения исходной кучи составит O(n log(n)).
Для завершения сортировки алгоритм удаляет каждый элемент из кучи, а затем восстанавливает ее свойства. Для этого он меняет местами последний элемент кучи и корневой узел, а затем передвигает новый корень вниз по дереву. Дерево имеет высоту O(log(n)) уровней, поэтому процесс может занять O(log(n)) времени. Алгоритм повторяет такой шаг n раз, отсюда общее количество нужных шагов – O(n log(n)). Суммирование времени, необходимого для построения исходной кучи и окончания сортировки, дает следующее: O(n log(n)) + O(n log(n)) = O(n log(n)).