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

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

 

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 — при выполнении интерполяционного поиска.