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

сек, независимо от первоначального порядка расположения элементов в списке.

Пузырьковая сортировка может превзойти этот результат, только если примерно

97 процентов списка было упорядочено до начала сортировки.

=====239

@Таблица 9.2. Время пузырьковой сортировки 2.000 элементов

Несмотря на то, что пузырьковая сортировка медленнее, чем многие другие

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

наилучшие результаты, если список изначально уже почти упорядочен. Если

программа управляет списком, который сортируется при создании, а затем к

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

выбором.

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

Быстрая сортировка (quicksort) — рекурсивный алгоритм, который использует

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

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

два подсписка, а затем рекурсивно вызывает себя для сортировки двух

подсписков.

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

проста. Если алгоритм вызывается для подсписка, содержащего не более одного

элемента, то подсписок уже отсортирован, и подпрограмма завершает работу.

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

разбиения списка на два подсписка. Она помещает элементы, которые меньше,

чем выбранный элементы в первый подсписок, а остальные — во второй, и затем

рекурсивно вызывает себя для сортировки двух подсписков.

Public Sub QuickSort(List() As Long, ByVal min as Integer, _

ByVal max As Integer)

Dim med_value As Long

Dim hi As Integer

Dim lo As Integer

‘ Если осталось менее 1 элемента, подсписок отсортирован.

If min >= max Then Exit Sub

‘ Выбрать значение для деления списка.

med_value = list(min)

lo = min

hi = max

Do

Просмотр от hi до значения < med_value.

Do While list(hi) >= med_value

hi = hi - 1

If hi = med_value.

lo = lo + 1

Do While list(lo) < med_values

lo = lo + 1

If lo >= hi Then Exit Do

Loop

If lo >= hi Then

lo = hi

list(hi) = med_value

Exit Do

End If

‘ Поменять местами значения lo и hi.

list(hi) = list(lo)

Loop

‘ Рекурсивная сортировка двух подлистов.

QuickSort list(), min, lo - 1

QuickSort list(), lo + 1, max

End Sub

=========240

Есть несколько важных моментов в этой версии алгоритма, которые стоит

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

один подсписок. Это означает, что в двух подсписках содержится на одни

элемент меньше, чем в исходном списке. Т.к. число рассматриваемых элементов

уменьшается, то в конечном итоге алгоритм завершит работу.

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

списке. В идеале, это значение должно было бы находиться где-то в середине

списка, так чтобы два подсписка были примерно равного размера. Тем не

менее, если элементы первоначально почти отсортированы, то первый элемент —

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

первый подсписок, и все элементы во второй. Последовательность действий

алгоритма будет примерно такой, как показано на рис. 9.4.

В этом случае каждый вызов подпрограммы требует порядка O(N) шагов для

перемещения всех элементов во второй подсписок. Т.к. алгоритм рекурсивно

вызывает себя N - 1 раз, время его выполнения будет порядка O(N2), что не

лучше, чем у ранее рассмотренных алгоритмов. Ситуацию еще более ухудшает

то, что уровень вложенности рекурсии алгоритма N - 1. Для больших списков

огромная глубина рекурсии приведет к переполнению стека и сбою в работе

программы.

=========242

@Рис. 9.4. Быстрая сортировка упорядоченного списка

Существует много стратегий выбора разделительного элемента. Можно

использовать элемент из середины списка. Это может оказаться неплохим

выбором, тем не менее, может оказаться и так, что это окажется наименьший

или наибольший элемент списка. При этом один подсписок будет намного

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

O(N2) и глубокому уровню рекурсии.

Другая стратегия может заключаться в том, чтобы просмотреть весь список,

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

качестве разделительного значения. Этот подход будет давать неплохие

результаты, но потребует дополнительных усилий. Дополнительный проход со

сложностью порядка O(N) не изменит теоретическое время выполнения

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

Третья стратегия — выбрать средний из элементов в начале, конце и середине

списка. Преимущество этого подхода в быстроте, потому что потребуется

выбрать всего три элемента. При этом гарантируется, что этот элемент не

является наибольшим или наименьшим в списке, и вероятно окажется где-то в

середине списка.

И, наконец, последняя стратегия, которая используется в программе Sort,

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

неплохим выбором. Даже если это не так, возможно на следующем шаге

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

наихудшего случая очень мала.

Интересно, что этот метод превращает ситуацию «небольшая вероятность того,

что всегда будет плохая производительность» в ситуацию «всегда небольшая

вероятность плохой производительности». Это довольно запутанное утверждение

объясняется в следующих абзацах.

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

вероятность того, что при определенной организации списка время сортировки

будет порядка O(N2), Хотя маловероятно, что подобная организация списка в

начале сортировки встретится на самом деле, тем не менее, время выполнения

при этом будет определенно порядка O(N2), неважно почему. Это то, что можно

назвать «небольшой вероятностью того, что всегда будет плохая

производительность».

===========242

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

влияет на производительность алгоритма. Существует небольшая вероятность

неудачного выбора элемента, но вероятность того, что это будет происходить

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

вероятность плохой производительности». Независимо от первоначальной

организации списка, очень маловероятно, что производительность алгоритма

будет порядка O(N2).

Тем не менее, все еще остается ситуация, которая может вызвать проблемы при

использовании любого из этих методов. Если в списке очень мало различных

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

подсписок при каждом вызове. Например, если каждый элемент в списке имеет

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

9.5. Это приводит к большому уровню вложенности рекурсии и дает

производительность порядка O(N2).

Похожее поведение происходит также при наличии большого числа повторяющихся

значений. Если список состоит из 10.000 элементов со значениями от 1 до 10,

алгоритм довольно быстро разделит список на подсписки, каждый из которых

содержит только одно значение.

Наиболее простой выход — игнорировать эту проблему. Если вы знаете, что

данные не имеют такого распределения, то проблемы нет. Если данные имеют

небольшой диапазон значений, то вам стоит рассмотреть другой алгоритм

сортировки. Описываемые далее в этой главе алгоритмы сортировки подсчетом и

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

находятся в узком диапазоне.

Можно внести еще одно небольшое улучшение в алгоритм быстрой сортировки.

Подобно многих другим более сложным алгоритмам, описанным далее в этой

главе, быстрая сортировка — не самый лучший выбор для сортировки небольших

списков. Благодаря своей простоте, сортировка выбором быстрее при

сортировке примерно десятка записей.

@Рис. 9.5. Быстрая сортировка списка из единиц

==========243

@Таблица 9.3. Время быстрой сортировки 20.000 элементов

Можно улучшить производительность быстрой сортировки, если прекратить

рекурсию до того, как подсписки уменьшатся до нуля, и использовать для

завершения работы сортировку выбором. В табл. 9.3 приведено время, которое

занимает выполнение быстрой сортировки 20.000 элементов на компьютере с

процессором Pentium с тактовой частотой 90 МГц, если останавливать

сортировку при достижении подсписками определенного размера. В этом тесте

оптимальное значение этого параметра было равно 15.

Следующий код демонстрирует доработанный алгоритм:

Public Sub QuickSort*List() As Long, ByVal min As Long, ByVal max As Long)

Dim med_value As Long

Dim hi As Long

Dim lo As Long

Dim i As Long

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

‘ завершить его сортировку процедурой SelectionSort.

If max - min < cutOff Then

SelectionSort List(), min, max

Exit Sub

End If

‘ Выбрать разделяющее значение.

i = Int((max - min + 1) * Rnd + min)

med_value = List(i)

‘ Переместить его вперед.

List(i) = List(min)

lo = min

hi = max

Do

‘ Просмотр сверху вниз от hi до значения < med_value.

Do While List(hi) >= med_value

hi = hi - 1

If hi = med_value.

lo = lo + 1

Do While List(lo) < med_value

lo = lo + 1

If lo >= hi Then Exit Do

Loop

If lo >= hi Then

lo = hi

List(hi) = med_value

Exit Do

End If

‘ Поменять местами значения lo и hi.

List(hi) = List(lo)

Loop

‘ Сортировать два подсписка.

QuickSort List(), min, lo - 1

QuickSort List(), lo + 1, max

End Sub

=======244

Многие программисты выбирают алгоритм быстрой сортировки, т.к. он дает

хорошую производительность в большинстве обстоятельств.

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

Как и быстрая сортировка, сортировка слиянием (mergesort) — это рекурсивный

алгоритм. Он также разделяет список на два подсписка, и рекурсивно

сортирует подсписки.

Сортировка слиянием делит список пополам, формируя два подсписка

одинакового размера. Затем подсписки рекурсивно сортируются, и

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

список.

Хотя этап слияния легко понять, это наиболее интересная часть алгоритма.

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

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

особенно если размер элементов велик. Если размер временного размера очень

большой, он может приводить к обращению к файлу подкачки и значительно

снижать производительность. Работа с временным массивом также приводит к

тому, что большая часть времени уходит на копирование элементов между

массивами.

Так же, как и в случае с быстрой сортировкой, можно ускорить выполнение

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

определенного минимального размера. Затем можно использовать сортировку

выбором для завершения работы.

=========245

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

ByVal min As Long, ByVal max As Long)

Dim middle As Long

Dim i1 As Long

Dim i2 As Long

Dim i3 As Long

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

‘ завершить его сортировку процедурой SelectionSort.

If max - min < CutOff Then

Selectionsort List(), min, max

Exit Sub

End If

‘ Рекурсивная сортировка подсписков.

middle = max \ 2 + min \ 2

Mergesort List(), Scratch(), min, middle

Mergesort List(), Scratch(), middle + 1, max

‘ Слить отсортированные списки.

i1 = min ‘ Индекс списка 1.

i2 = middle + 1 ‘ Индекс списка 2.

i3 = min ‘ Индекс объединенного списка.

Do While i1 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. Тогда полное

Страницы: 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