Предыдущая страница реферата | 34  35  36  37  38  39  40  41  42  43  44 | Следующая страница реферата

Loop

‘ Обновить переменную max. max = last_swap - 1

‘ «Погружение». last_swap = max + 1

‘ То есть For i = max -1 To min Step -1 i = max - 1

Do While i >= min

‘ Найти «пузырек».

If List(i + 1) < List(i) Then

‘ Найти, куда его поместить. tmp = List(i + 1) j = i

Do

List(j + 1) = List(j) j = j - 1

If j < min Then Exit Do

Loop While List(j) > tmp

List(j + 1) = tmp last_swap = j + 1 i = j - 1

Else i = i - 1

End If

Loop

‘ Обновить переменную min.

Min = last_swap + 1

Loop
End Sub

==========238

Для того чтобы протестировать алгоритм пузырьковой сортировки при помощи программы Sort, поставьте галочку в поле Sorted (Отсортированные) в области
Initial Ordering (Первоначальный порядок). Введите число элементов в поле
#Unsorted (Число несортированных). После нажатия на кнопку Go (Начать), программа создает и сортирует список, а затем переставляет случайно выбранные пары элементов. Например, если вы введете число 10 в поле
#Unsorted, программа переставит 5 пар чисел, то есть 10 элементов окажутся не на своих местах.
Для второго варианта первоначального алгоритма, программа сохраняет элемент во временной переменной при перемещении на несколько шагов. Этот происходит еще быстрее, если использовать функцию API MemCopy. Алгоритм пузырьковой сортировки в программе FastSort, используя функцию MemCopy, сортирует элементы в 50 или 75 раз быстрее, чем первоначальная версия, реализованная в программе Sort.
В табл. 9.2 приведено время выполнения пузырьковой сортировки 2000 элементов на компьютере с процессором Pentium с тактовой частотой 90 МГц в зависимости от степени первоначальной упорядоченности списка. Из таблицы видно, что алгоритм пузырьковой сортировки обеспечивает хорошую производительность, только если список с самого начала почти отсортирован.
Алгоритм быстрой сортировки, который описывается далее в этой главе, способен отсортировать тот же список из 2000 элементов примерно за 0,12 сек, независимо от первоначального порядка расположения элементов в списке.
Пузырьковая сортировка может превзойти этот результат, только если примерно
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 = 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 = 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 NumItems Then

Search = 0 ' Элемент не найден.

Рекомендуем скачать другие рефераты по теме: доклад по химии, конспект зима.



Предыдущая страница реферата | 34  35  36  37  38  39  40  41  42  43  44 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки