Некоторые алгоритмы перемещают большие блоки памяти. Например, алгоритм сортировки вставкой перемещает элементы списка для того, чтобы можно было вставить новый элемент в середину списка. Для перемещения элементов программе, написанной на Visual Basic, приходится использовать цикл For. Следующий код показывает, как сортировка вставкой перемещает элементы с List(j) до List(max_sorted) для того, чтобы освободить место под новый элемент в позиции List(j):
For k = max_sorted To j Step -1
List(k + 1) = List(k)
Next k
List(j) = next_num
==========230
Интерфейс прикладного программирования системы Windows включает две функции, которые позволяют намного быстрее выполнять перемещение блоков памяти. Программы, скомпилированные 16‑битной версией компилятора Visual Basic 4, могут использовать функцию hmemcopy. Программы, скомпилированные 32‑битными компиляторами Visual Basic 4 и 5, могут использовать функцию RtlMoveMemory. Обе функции принимают в качестве параметров конечный и исходный адреса и число байт, которое должно быть скопировано. Следующий код показывает, как объявлять эти функции в модуле .BAS:
#if Win16 Then
Declare Sub MemCopy Lib "Kernel" Alias _
"hmemcpy" (dest As Any, src As Any, _
ByVal numbytes As Long)
#Else
Declare Sub MemCopy Lib "Kernel32" Alias _
"RtlMoveMemory" (dest As Any, src As Any, _
ByVal numbytes As Long)
#EndIf
Следующий фрагмент кода показывает, как сортировка вставкой может использовать эти функции для копирования блоков памяти. Этот код выполняет те же действия, что и цикл For, приведенный выше, но делает это намного быстрее:
If max_sorted >= j Then _
MemCopy List(j + 1), List(j), _
Len(next_num) * (max_sorted - j + 1)
List(j) = next_num
Программа FastSort аналогична программе Sort, но она использует функцию MemCopy для ускорения работы некоторых алгоритмов. В программе FastSort алгоритмы, использующие функцию MemCopy, выделены синим цветом.
Сортировка выбором (selectionsort) — простой алгоритм со сложность порядка O(N2). Идея состоит в поиске наименьшего элемента в списке, который затем меняется местами с элементом на вершине списка. Затем находится наименьший элемент из оставшихся, и меняется местами со вторым элементом. Процесс продолжается до тех пор, пока все элементы не займут свое конечное положение.
Public Sub Selectionsort(List() As Long, min As Long, max As Long)
Dim i As Long
Dim j As Long
Dim best_value As Long
Dim best_j As Long
For i = min To max - 1
‘ Найти наименьший элемент из оставшихся.
best_value = List(i)
best_j = i
For j = i + 1 To max
If List(j) < best_value Then
best_value = List(j)
best_j = j
End If
Next j
‘ Поместить элемент на место.
List(best_j) = List(i)
List(i) = best_value
Next i
End Sub
========231
При поиске I-го наименьшего элемента, алгоритму приходится перебрать N-I элементов, которые еще не заняли свое конечное положение. Время выполнения алгоритма пропорционально N + (N - 1) + (N - 2) + … + 1, или порядка O(N2).
Сортировка выбором неплохо работает со списками, элементы в которых расположены случайно или в прямом порядке, но несколько хуже, если список изначально отсортирован в обратном порядке. Для поиска наименьшего элемента в списке сортировка выбором выполняет следующий код:
If list(j) < best_value Then
best_value = list(j)
best_j = j
End If
Если первоначально список отсортирован в обратном порядке, условие list(j) < best_value выполняется большую часть времени. Например, при первом проходе оно будет истинно для всех элементов, поскольку каждый элемент меньше предыдущего. Алгоритм будет многократно выполнять строки с оператором If, что приведет к некоторому замедлению работы алгоритма.
Это не самый быстрый алгоритм из числа описанных в главе, но он чрезвычайно прост. Это не только облегчает его разработку и отладку, но и делает сортировку выбором достаточно быстрой для небольших задач. Многие другие алгоритмы настолько сложны, что они сортируют очень маленькие списки медленнее.
В некоторых программах требуется выполнение операции, обратной сортировке. Получив список элементов, программа должна расположить их в случайном порядке. Рандомизацию (unsorting) списка несложно выполнить, используя алгоритм, похожий на сортировку выбором.
Для каждого положения в списке, алгоритм случайным образом выбирает элемент, который должен его занять из тех, которые еще не были помещены на свое место. Затем этот элемент меняется местами с элементом, который, находится на этой позиции.
Public Sub Unsort(List() As Long, min As Long, max As Long)
Dim i As Long
Dim Pos As Long
Dim tmp As Long
For i - min To max - 1
pos = Int((max - i + 1) * Rnd + i)
tmp = List(pos)
List(pos) = List(i)
List(i) = tmp
Next i
End Sub
==============232
Т.к. алгоритм заполняет каждую позицию только один раз, его сложность порядка O(N).
Несложно показать, что вероятность того, что элемент окажется на какой‑либо позиции, равна 1/N. Поскольку элемент может оказаться в любом положении с равной вероятностью, этот алгоритм действительно приводит к случайному размещению элементов.
Результат зависит от того, насколько хорошим является генератор случайных чисел. Функция Rnd в Visual Basic дает приемлемый результат для большинства случаев. Следует убедиться, что программа использует оператор Randomize для инициализации функции Rnd, иначе при каждом запуске программы функция Rnd будет выдавать одну и ту же последовательность «случайных» значений.
Заметим, что для алгоритма не важен первоначальный порядок расположения элементов. Если вам необходимо неоднократно рандомизировать список элементов, нет необходимости его предварительно сортировать.
Программа Unsort показывает использование этого алгоритма для рандомизации отсортированного списка. Введите число элементов, которые вы хотите рандомизировать, и нажмите кнопку Go (Начать). Программа показывает исходный отсортированный список чисел и результат рандомизации.
Сортировка вставкой (insertionsort) — еще один алгоритм со сложностью порядка O(N2). Идея состоит в том, чтобы создать новый сортированный список, просматривая поочередно все элементы в исходном списке. При этом, выбирая очередной элемент, алгоритм просматривает растущий отсортированный список, находит требуемое положение элемента в нем, и помещает элемент на свое место в новый список.
Public Sub Insertionsort(List() As Long, min As Long, max As Long)
Dim i As Long
Dim j As Long
Dim k As Long
Dim max_sorted As Long
Dim next_num As Long
max_sorted = min -1
For i = min To max
‘ Это вставляемое число.
Next_num = List(i)
‘ Поиск его позиции в списке.
For j = min To max_sorted
If List(j) >= next_num Then Exit For
Next j
‘ Переместить большие элементы вниз, чтобы
‘ освободить место для нового числа.
For k = max_sorted To j Step -1
List(k + 1) = List(k)
Next k
‘ Поместить новый элемент.
List(j) = next_num
‘ Увеличить счетчик отсортированных элементов.
max_sorted = max_sorted + 1
Next i
End Sub
=======233
Может оказаться, что для каждого из элементов в исходном списке, алгоритму придется проверять все уже отсортированные элементы. Это происходит, например, если в исходном списке элементы были уже отсортированы. В этом случае, алгоритм помещает каждый новый элемент в конец растущего отсортированного списка.
Полное число шагов, которые потребуется выполнить, составляет 1 + 2 + 3 + … + (N - 1), то есть O(N2). Это не слишком эффективно, если сравнить с теоретическим пределом O(N * log(N)) для алгоритмов на основе операций сравнения. Фактически, этот алгоритм не слишком быстр даже в сравнении с другими алгоритмами порядка O(N2), такими как сортировка выбором.
Достаточно много времени алгоритм сортировки вставкой тратит на перемещение элементов для того, чтобы вставить новый элемент в середину отсортированного списка. Использование для этого функции API MemCopy увеличивает скорость работы алгоритма почти вдвое.
Достаточно много времени тратится и на поиск правильного положения для нового элемента. В 10 главе описано несколько алгоритмов поиска в отсортированных списках. Применение алгоритма интерполяционного поиска намного ускоряет выполнение алгоритма сортировки вставкой. Интерполяционный поиск подробно описывается в 10 главе, поэтому мы не будем сейчас на нем останавливаться.
Программа FastSort использует оба этих метода для улучшения производительности сортировки вставкой. С использованием функции MemCopy и интерполяционного поиска, эта версия алгоритма более чем в 15 раз быстрее, чем исходная.
Можно использовать вариант сортировки вставкой для упорядочения элементов не в массиве, а в связном списке. Этот алгоритм ищет требуемое положение элемента в растущем связном списке, и затем помещает туда новый элемент, используя операции работы со связными списками.
=========234
Public Sub LinkInsertionSort(ListTop As ListCell)
Dim new_top As New ListCell
Dim old_top As ListCell
Dim cell As ListCell
Dim after_me As ListCell
Dim nxt As ListCell
Set old_top = ListTop.NextCell
Do While Not (old_top Is Nothing)
Set cell = old_top
Set old_top = old_top.NextCell
‘ Найти, куда необходимо поместить элемент.
Set after_me = new_top
Do
Set nxt = after_me.NextCell
If nxt Is Nothing Then Exit Do
If nxt.Value >= cell.Value Then Exit Do
Set after_me = nxt
Loop
‘ Вставить элемент после позиции after_me.
Set after_me.NextCll = cell
Set cell.NextCell = nx
Loop
Set ListTop.NextCell = new_top.NextCell
End Sub
Т.к. этот алгоритм перебирает все элементы, может потребоваться сравнение каждого элемента со всеми элементами в отсортированном списке. В этом наихудшем случае вычислительная сложность алгоритма порядка O(N2).
Наилучший случай для этого алгоритма достигается, когда исходный список первоначально отсортирован в обратном порядке. При этом каждый последующий элемент меньше, чем предыдущий, поэтому алгоритм помещает его в начало отсортированного списка. При этом требуется выполнить только одну операцию сравнения элементов, и в наилучшем случае время выполнения алгоритма будет порядка O(N).