Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Способы записи алгоритмов).pdf

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

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

Компьютеризованный вариант этого алгоритма использует десять стопок:

RadixSort(List,N)

list сортируемый список элементов

N число элементов в списке

shift=l

for loop=l to keySize do

for entry=l to N do

bucketNumber=(list[entry].key/shift) mod 10

Append(bucket[bucketNumber], list[entry])

end for entry

list=CombineBuckets О

shift=shift*10

end for loop

При вычислении значения переменной bucketNumber из ключа вытаскивается одна цифра. При делении на shift ключевое значение сдвинется на несколько позиций вправо, а последующее применение операции mod оставляет лишь цифру единиц полученного числа.

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

При втором проходе значение переменной shift будет уже равно 10, поэтому целочисленное деление и последующее применение операции mod дают цифру десятков. При очередном проходе будет получена следующая цифра числа.

Функция CombineBuckets вновь сводит все стопки от bucket [0] до bucket [9] в один список. Тем самым переформированный список будет служить основой для следующего прохода. Так как переформирование стопок идет в определенном порядке, а числа добавляются к концу каждой стопки, то ключевые значения постепенно оказываются отсортированными.

Исходный список

313 217 021 131 016 308 225 037 202 112 329 005 334 104 232 125

Номер стопки Содержимое

0 313 131 334 125

1 308 202 112 232

2 225 037 005 104

3 217 021 016 329

Первый проход, разряд единиц

Список, полученный в результате первого прохода

313 131 334 125 308 202 112 232 225 037 005 104 217 021 016 329

Номер стопки Содержимое

0 308 202 005 104

1 313 112 217 016

2 125 225 021 329

3 131 334 232 037

Второй проход, разряд десятков

Список полученный в результате второго прохода

308 202 005 104 313 112 217 016 125 225 021 329 131 334 232 037

Номер стопки Содержимое

0 005 016 021 037

1 104 112 125 131

2 202 217 225 232

3 308 313 329 334

Третий проход, разряд сотен

На данном примере показана три прохода на списке трехзначных чисел. Чтобы упростить пример в ключах, использовались числа, которые начинались от 0 до 3, поэтому достаточно было всего лишь четырех стопок.

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

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

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

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

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

2.5 Пирамидальная сортировка

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

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

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

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

Результатом оказывается то, что в корне оказывается по второй величине элемент, который копируется в список, а сама процедура повторяется пока все элементы не окажутся возвращенными в список.

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

сконструировать пирамиду

for i=l to N do

скопировать корень пирамиды в список

переформировать пирамиду

end for

На рисунке 2 изображена пирамида и ее списочное представление.

Рисунок 2 Пирамида и ее списочное представление

Переформирование пирамиды.

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

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

FixHeap(list,root,key,bound)

list сортируемый список/пирамида

root номер корня пирамиды

key ключевое значение, вставляемое в пирамиду

bound правая граница (номер) в пирамиде

vacant = root

while 2*vacant <= bound do

larger-Child = 2*vacant

// поиск наибольшего из двух непосредственных потомков

if (largerChild<bound) and (list[largerChild+l]>

list[largerChild+l]) then

largerChild=largerChild+l

end if

// находится ли ключ выше текущего потомка?

if key>list[largerChild] then

// да, цикл завершается

break

else

// нет, большего непосредственного потомка

//следует поднять

list[vacant]=list[largerChild]

vacant=largerChild

end if e

nd while

list[vacant]=key

В данном алгоритме, корень пирамиды всегда должен быть первым элементом /6, с.92-95/.

2.6 Сортировка слиянием

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

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

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

MergeSort(list,first,last)

list сортируемый список элементов

first номер первого элемента в сортируемой части списка

last номер последнего элемента в сортируемой части списка

if first < last then

middle=(first+last)/2

MergeSort(list.first.middle)

MergeSort(list,middle+l,last)

MergeLists(list.first.middle,middle+l,last)

End if

Отсюда видно, что основную работу в алгоритме проделывает функция MergeLists /6, с.98-99/.

2.7 Быстрая сортировка

Быстрая сортировка является рекурсивным алгоритмом сортировки. Как и сортировка слиянием, быстрая сортировка, выбрав элемент делит с его помощью список на две части.

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

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

Если г – окончательное положение осевого элемента, то все значения в позициях с первой по г -1 меньше осевого, а значения с номерами г + 1 до N больше осевого. После чего алгоритм Quicksort вызывается рекурсивно на каждой из двух частей. Когда происходит вызов процедуры Quicksort на списке, который состоит из одного элемента, то он ничего не делает, так ка одноэлементный список уже отсортирован.

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

Ниже показан алгоритм быстрой сортировки:

Quicksort(list,first.last)

list упорядочиваемый список элементов

first номер первого элемента в сортируемой части списка

last номер последнего элемента в сортируемой части списка

if first < last then

pivot=PivotList(list,first,last)

Quicksort(list,first,pivot-1)

Quicksort(list,pivot+l,last)

end if

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

После того, как произведено сравнения части списка с осевым элементом, то список оказывается разбит на четыре части:

первая часть – состоит из первого осевого элемента списка;

вторая часть – начинается с положения first + 1, а кончается в положении PivotPoint, состоящих из всех просмотренных элементов, которые оказались меньше осевого;

третья часть – начинается в положении PivotPoint + 1 и заканчивается указателем параметра цикла index;

четвертая часть – состоит из еще не просмотренных значений.

Пример алгоритма PivotList:

PivotListdist , first .last)

list обрабатываемый список

first номер первого элемента

last номер последнего элемента

PivotValue=list [first]

PivotPoint=first

for index=f irst+1 to last do

if list [index] < Pivot Value then\

PivotPoint=PivotPoint+l

Swap(list [PivotPoint] , list [index] )

end if

end for

// перенос осевого значения на нужное место

Swap (list [first] , list [PivotPoint])

return PivotPoint /6, с.105-107/.

2.8 Внешняя многофазная сортировка слиянием

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

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