Смекни!
smekni.com

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

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

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 главе, можно улучшить производительность версии с использованием связных списков, так что обе версии станут практически эквивалентными по скорости.

Новую версию также можно сделать еще быстрее, используя функцию API MemCopy для копирования элементов из временного массива обратно в исходный список. Эта усовершенствованную версию алгоритма демонстрирует программа FastSort.

===========259-261

Резюме

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

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

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

* если более 99 процентов списка уже отсортировано, используйте пузырьковую сортировку;

* если список очень мал (100 или менее элементов), используйте сортировку выбором;

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

* если элементы в списке — целые числа, разброс значений которых невелик (до нескольких тысяч), используйте сортировку подсчетом;

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

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

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

@Таблица 9.4. Преимущества и недостатки алгоритмов сортировки

=========263

Глава 10. Поиск

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

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

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

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

Примеры программ

Программа Search демонстрирует все описанные в главе алгоритмы. Введите значение элементов, которые должен содержать список, и затем нажмите на кнопку Make List (Создать список), и программа создаст список на основе массива, в котором каждый элемент больше предыдущего на число от 0 до 5. Программа выводит значение наибольшего элемента в списке, чтобы вы представляли диапазон значений элементов.

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

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

=======265

На рис. 10.1 показано окно программы Search после поиска элемента со значением 250.000. Этот элемент находился на позиции 99.802 в списке из 100.000 элементов. Чтобы найти этот элемент, потребовалось проверить 99.802 элемента при использовании алгоритма полного перебора, 16 элементов — при использовании двоичного поиска и всего 3 — при выполнении интерполяционного поиска.

Поиск методом полного перебора