Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

@Рис. 9.7. Представление пирамиды в виде массива

========248

@Рис. 9.8. Пирамида образуется из меньших пирамид

@Рис. 9.9. Неупорядоченный список в полном дереве

@Рис. 9.10. Поддеревья второго уровня являются пирамидами

=========249

@Рис. 9.11. Объединение пирамид в пирамиду большего размера

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

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

Следующий код перемещает элемент из положения List(min) вниз по пирамиде. Если поддеревья ниже List(min) являются пирамидами, то процедура сливает пирамиды, образуя пирамиду большего размера.

Private Sub HeapPushDown(List() s Long, ByVal min As Long, _

    ByVal max As Long)

Dim tmp As Long

Dim j As Long

    tmp = List(min)

    Do

        j = 2 * min

        If j <= max Then

            ‘ Разместить в j указатель на большего потомка.

        If j < max Then

        If List(j + 1) > List(j) Then _

           j = j + 1

        End If

        If List(j) > tmp Then

           ‘ Потомок больше. Поменять его местами с родителем.

           List(min) = List(j)

           ‘ Перемещение этого потомка вниз.

                   min = j

               Else

                   ‘ Родитель больше. Процедура закончена.

               Exit Do

           End If

        Else

           Exit Do

        End If

    Loop

    List(min) = tmp

End Sub

Полный алгоритм, использующий процедуру HeapPushDown для создания пирамиды из дерева элементов, необычайно прост:

Private Sub BuildHeap()

Dim i As Integer

    For i = (max + min) \ 2 To min Step -1

        HeapPushDown list(), i, max

    Next i

End Sub

Приоритетные очереди

Приоритетной очередью (priority queue) легко управлять при помощи процедур BuildHeap и HeapPushDown. Если в качестве приоритетной очереди используется пирамида, легко найти элемент с самым высоким приоритетом — он всегда находится на вершине пирамиды. Но если его удалить, получившееся дерево без корня уже не будет пирамидой.

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

Public Function Pop() As Long

    If NumInQueue < 1 Then Exit Function

    ' Удалить верхний элемент.

    Pop = Pqueue(1)

    ' Переместить последний элемент на вершину.

    PQueue(1) = PQueue(NumInPQueue)

    NumInPQueue = NumInPQueue - 1

    ' Снова сделать дерево пирамидой.

    HeapPushDown PQueue(), 1, NumInPQueue

End Function

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

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

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

Private Sub HeapPushUp(List() As Long, ByVal max As Integer)

Dim tmp As Long

Dim j As Integer

    tmp = List (max)

    Do

        j = max \ 2

        If j < 1 Then Exit Do

        If List(j) < tmp Then

           List (max) = List(j)

           max = j

        Else

           Exit Do

        End If

    Loop

    List(max) = tmp

End Sub

Подпрограмма Push добавляет новый элемент к дереву и использует подпрограмму HeapPushDown для восстановления пирамиды.

Public Sub Push (value As Long)

    NumInPQueue = NumInPQueue + 1

    If NumInPQueue > PQueueSize Then ResizePQueue

    PQueue(NumInPQueue) = value

    HeapPushUp PQueue(), NumInPQueue

End Sub

========252

Анализ пирамид

При первоначальном превращении списка в пирамиду, это осуществляется при помощи создания множества пирамид меньшего размера. Для каждого внутреннего узла дерева строится пирамида с корнем в этом узле. Если дерево содержит N элементов, то в дереве O(N) внутренних узлов, и в итоге приходится создать O(N) пирамид.

При создании каждой пирамиды может потребоваться продвигать элемент вниз по пирамиде, возможно до тех пор, пока он не достигнет концевого узла. Самые высокие из построенных пирамид будут иметь высоту порядка O(log(N)). Так как создается O(N) пирамид, и для построения самой высокой из них требуется O(log(n)) шагов, то все пирамиды можно построить за время порядка O(N * log(N)).

На самом деле времени потребуется еще меньше. Только некоторые пирамиды будут иметь высоту порядка O(log(N)). Большинство из них гораздо ниже. Только одна пирамида имеет высоту, равную log(N), и половина пирамид — высоту всего в 2 узла. Если суммировать все шаги, необходимые для создания всех пирамид, в действительности потребуется не больше O(N) шагов.

Чтобы увидеть, так ли это, допустим, что дерево содержит N узлов. Пусть H — высота дерева. Это полное двоичное дерево, следовательно, H=log(N).

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

Для построения этих пирамид может потребоваться передвигать элемент вниз до тех пор, пока он не достигнет концевого узла. Перемещение элемента вниз по пирамиде с высотой I требует до I шагов. Для пирамид с высотой I полное число шагов, которое потребуется для построения 2H-I пирамид, равно I*2H-I.

Сложив все шаги, затрачиваемые на построение пирамид разного размера, получаем 1*2H-1+2*2H-2+3*2H-3+…+(H-1)* 21. Вынеся за скобки 2H, получим 2H*(1/2+2/22+3/23+…+(H-1)/2H-1).

Можно показать, что (1/2+2/22+3/23+…+(H-1)/2H-1) меньше 2. Тогда полное число шагов, которое нужно для построения всех пирамид, меньше, чем 2H*2. Так как H — высота дерева, равная log(N), то полное число шагов меньше, чем 2log(N)*2=N*2. Это означает, что для первоначального построения пирамиды требуется порядка O(N) шагов.

Для удаления элемента из приоритетной очереди, последний элемент перемещается на вершину дерева. Затем он продвигается вниз, пока не займет свое окончательное положение, и дерево снова не станет пирамидой. Так как дерево имеет высоту log(N), процесс может занять не более log(N) шагов. Это означает, что новый элемент к приоритетной очереди на основе пирамиды можно добавить за O(log(N)) шагов.

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

======253

Алгоритм пирамидальной сортировки

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

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

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

Public Sub Heapsort(List() As Long, ByVal min As Long, ByVal max As Long)

Dim i As Long

Dim tmp As Long

    ' Создать пирамиду (кроме корневого узла).

    For i = (max + min) \ 2 To min + 1 Step -1

        HeapPushDown List(), i, max

    Next i

    ' Повторять:

    '   1. Продвинуться вниз по пирамиде.

    '   2. Выдать корень.

    For i = max To min + 1 Step -1

        ' Продвинуться вниз по пирамиде.

        HeapPushDown List(), min, i

        ' Выдать корень.

        tmp = List(min)

        List(min) = List(i)

        List(i) = tmp

    Next i

End Sub

Предыдущее обсуждение приоритетных очередей показало, что первоначальное построение пирамиды требует O(N) шагов. После этого требуется O(log(N)) шагов для восстановления пирамиды, когда элемент продвигается на свое место. Пирамидальная сортировка выполняет это действие N раз, поэтому требуется всего порядка O(N)*O(log(N))=O(N*log(N)) шагов, чтобы получить из пирамиды упорядоченный список. Полное время выполнения для алгоритма пирамидальной сортировки составляет порядка O(N)+O(N*log(N))=O(N*log(N)).

=========254

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

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

Сортировка подсчетом

Сортировка подсчетом (countingsort) — специализированный алгоритм, который очень хорошо работает, если элементы данных — целые числа, значения которых находятся в относительно узком диапазоне. Этот алгоритм работает достаточно быстро, например, если значения находятся между 1 и 1000.

Если список удовлетворяет этим требованиям, сортировка подсчетом выполняется невероятно быстро. В одном из тестов на компьютере с процессором Pentium с тактовой частотой 90 МГц, быстрая сортировка 100.000 элементов со значениями между 1 и 1000 заняла 24,44 секунды. Для сортировки тех же элементов сортировке подсчетом потребовалось всего 0,88 секунд — в 27 раз меньше времени.

Выдающаяся скорость сортировки подсчетом достигается за счет того, что при этом не используются операции сравнения. Ранее в этой главе отмечалось, что время выполнения любого алгоритма сортировки, использующего операции сравнения, порядка O(N*log(N)). Без использования операций сравнения, алгоритм сортировки подсчетом позволяет упорядочивать элементы за время порядка O(N).

Сортировка подсчетом начинается с создания массива для подсчета числа элементов, имеющих определенное значение. Если значения находятся в диапазоне между min_value и max_value, алгоритм создает массив Counts с нижней границей min_value и верхней границей max_value. Если используется массив из предыдущего прохода, необходимо обнулить значения его элементов. Если существует M значений элементов, массив содержит M записей, и время выполнения этого шага порядка O(M).

For i = min To max

    Counts(List(i)) = Counts(List(i)) + 1

Next i

В конце концов, алгоритм обходит массив Counts, помещая соответствующее число элементов в отсортированный массив. Для каждого значения i между min_value и max_value, он помещает Counts(i) элементов со значением i в массив. Так как этот шаг помещает по одной записи в каждую позицию в массиве, он требует порядка O(N) шагов.

new_index = min

For i = min_value To max_value

    For j = 1 To Counts(i)

        sorted_list(new_index) = i

        new_index = new_index + 1

    Next j

Next i

======255

Алгоритм целиком требует порядка O(M)+O(N)+O(N)=O(M+N) шагов. Если M мало по сравнению с N, он выполняется очень быстро. Например, если M<N, то O(M+N)=O(N), что довольно быстро. Если N=100.000 и M=1000, то M+N=101.000, тогда как N*log(N)=1,6 миллиона. Шаги, выполняемые алгоритмом сортировки подсчетом, также относительно просты по сравнению с шагами быстрой сортировки. Все эти факты объединяются, обеспечивая вместе невероятно высокую скорость выполнения сортировки подсчетом.

С другой стороны, если M больше, чем O(N*log(N)), тогда O(M+N) будет больше, чем O(N*log(N)). В этом случае сортировка подсчетом может оказаться медленнее, чем алгоритмы со сложностью порядка O(N*log(N)), такие как быстрая сортировка. В одном из тестов быстрая сортировка 1000 элементов со значениями от 1 до 500.000 потребовал 0,054 сек, в то время как сортировка подсчетом потребовала 1,76 секунд.

Сортировка подсчетом опирается на тот факт, что значения данных — целые числа, поэтому этот алгоритм не может просто сортировать данные других типов. В Visual Basic нельзя создать массив с границами от AAA до ZZZ.

Ранее в этой главе в разделе «объединение и сжатие ключей» было продемонстрировано, как можно кодировать строковые данные при помощи целых чисел. Если вы может закодировать данные при помощи данных типа Integer или Long, вы все еще можете использовать сортировку подсчетом.

Блочная сортировка

Как и сортировка подсчетом, блочная сортировка (bucketsort) не использует операций сравнения элементов. Этот алгоритм использует значения элементов для разбиения их на блоки, и затем рекурсивно сортирует полученные блоки. Когда блоки становятся достаточно малыми, алгоритм останавливается и использует более простой алгоритм типа сортировки выбором для завершения процесса.

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

Для деления списка на блоки, алгоритм предполагает, что значения данных распределены равномерно, и распределяет элементы по блокам равномерно. Например, предположим, что данные имеют значения в диапазоне от 1 до 100 и алгоритм использует 10 блоков. Алгоритм помещает элементы со значениями 1‑10 в первый блок, со значениями 11‑20 — во второй, и т.д. На рис. 9.12 показан список из 10 элементов со значениями от 1 до 100, которые расположены в 10 блоках.

@Рис. 9.12. Расположение элементов в блоках.

=======256

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

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

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

Блочная сортировка с применением связного списка

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

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

Public Sub LinkBucketSort(ListTop As ListCell)

Dim count As Long

Dim min_value As Long

Dim max_value As Long

Dim Value As Long

Dim item As ListCell

Dim nxt As ListCell

Dim bucket() As New ListCell

Dim value_scale As Double

Dim bucket.num As Long

Dim i As Long

    Set item = ListTop.NextCell

    If item Is Nothing Then Exit Sub

    ' Подсчитать элементы и найти значения min и max.

    count = 1

    min_value = item.Value

    max_value = min_value

    Set item = item.NextCell

    Do While Not (item Is Nothing)

        count = count + 1

        Value = item.Value

        If min_value > Value Then min_value = Value

        If max_value < Value Then max_value = Value

        Set item = item.NextCell

    Loop

    ' Если min_value = max_value, значит, есть единственное

    ' значение, и список отсортирован.

    If min_value = max_value Then Exit Sub

    ' Если в списке не более, чем CutOff элементов,

    ' завершить сортировку процедурой LinkInsertionSort.

    If count <= CutOff Then

        LinkInsertionSort ListTop

        Exit Sub

    End If

    ' Создать пустые блоки.

    ReDim bucket(1 To count)

    value_scale = _

    CDbl(count - 1) / _

    CDbl(max_value - min_value)

    ' Разместить элементы в блоках.

    Set item = ListTop.NextCell

    Do While Not (item Is Nothing)

        Set nxt = item.NextCell

        Value = item.Value

        If Value = max_value Then

           bucket_num = count

        Else

           bucket_num = _

               Int((Value - min_value) * _

                   value_scale) + 1

        End If

        Set item.NextCell = bucket (bucket_num).NextCell

        Set bucket(bucket_num).NextCell = item

        Set item = nxt

    Loop

    ' Рекурсивная сортировка блоков, содержащих

    ' более одного элемента.

    For i = 1 To count

        If Not (bucket(i).NextCell Is Nothing) Then _

           LinkBucketSort bucket(i)

    Next i

    ' Объединить отсортированные списки.

    Set ListTop.NextCell = bucket(count).NextCell

    For i = count - 1 To 1 Step -1

        Set item = bucket(i).NextCell

        If Not (item Is Nothing) Then

           Do While Not (item.NextCell Is Nothing)

               Set item = item.NextCell

           Loop

           Set item.NextCell = ListTop.NextCell

           Set ListTop.NextCell= bucket(i).NextCell

        End If

    Next i

End Sub

=========257-258

Эта версия блочной сортировки намного быстрее, чем сортировка вставкой с использованием связных списков. В тесте на компьютере с процессором Pentium с тактовой частотой 90 МГц сортировке вставкой потребовалось 6,65 секунд для сортировки 2000 элементов, блочная сортировка заняла 1,32 секунды. Для более длинных списков разница будет еще больше, так как производительность сортировки вставкой порядка O(N2).

Блочная сортировка на основе массива

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

Public Sub ArrayBucketSort(List() As Long, Scratch() As Long, _

    min As Long, max As Long, NumBuckets As Long)

Dim counts() As Long

Dim offsets() As Long

Dim i As Long

Dim Value As Long

Dim min_value As Long

Dim max_value As Long

Dim value_scale As Double

Dim bucket_num As Long

Dim next_spot As Long

Dim num_in_bucket As Long

    ' Если в списке не более чем CutOff элементов,

    ' закончить сортировку процедурой SelectionSort.

    If max - min + 1 < CutOff Then

        Selectionsort List(), min, max

        Exit Sub

    End If

    ' Найти значения min и max.

    min_value = List(min)

    max_value = min_value

    For i = min + 1 To max

        Value = List(i)

        If min_value > Value Then min_value = Value

        If max_value < Value Then max_value = Value

    Next i

    ' Если min_value = max_value, значит, есть единственное

    ' значение, и список отсортирован.

    If min_value = max_value Then Exit Sub

    ' Создать пустой массив с отсчетами блоков.

    ReDim counts(l To NumBuckets)

    value_scale = _

        CDbl (NumBuckets - 1) / _

        CDbl (max_value - min_value)

    ' Создать отсчеты блоков.

    For i = min To max

        If List(i) = max_value Then

           bucket_num = NumBuckets

        Else

           bucket_num = _

               Int((List(i) - min_value) * _

                   value_scale) + 1

        End If

        counts(bucket_num) = counts(bucket_num) + 1

    Next i

    ' Преобразовать отсчеты в смещение в массиве.

    ReDim offsets(l To NumBuckets)

    next_spot = min

    For i = 1 To NumBuckets

        offsets(i) = next_spot

        next_spot = next_spot + counts(i)

    Next i

    ' Разместить значения в соответствующих блоках.

    For i = min To max

        If List(i) = max_value Then

           bucket_num = NumBuckets

        Else

           bucket_num = _

               Int((List(i) - min_value) * _

                   value_scale) + 1

        End If

        Scratch (offsets (bucket_num)) = List(i)

        offsets(bucket_num) = offsets(bucket_num) + 1

    Next i

    ' Рекурсивная сортировка блоков, содержащих

    ' более одного элемента.

    next_spot = min

    For i = 1 To NumBuckets

        If counts(i) > 1 Then ArrayBucketSort _

           Scratch(), List(), next_spot, _

           next_spot + counts(i) - 1, counts(i)

        next_spot = next_spot + counts(i)

    Next i

    ' Скопировать временный массив назад в исходный список.

    For i = min To max

        List(i) = Scratch(i)

    Next i

End Sub

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33