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

Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве.

Наконец, сортировка является одной из немногих задач с точными теоретическими ограничениями производительности. Можно показать, что время выполнения любого алгоритма сортировки, который использует сравнения, составляет порядка O(N * log(N)). Некоторые алгоритмы достигают теоретического предела, то есть они являются оптимальными в этом смысле. Есть даже ряд несколько алгоритмов, которые используют другие методы вместо сравнений, которые выполняются быстрее, чем за время порядка O(N * log(N)).

Общие соображения

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

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

Таблицы указателей

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

========225

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

Type Emloyee

    ID As Integer

    LastName As String

    FirstName As String

    <и т.д.>

End Type

‘ Выделить память под записи.

Dim EmloyeeData(1 To 10000)

Чтобы отсортировать сотрудников по идентификационному номеру, нужно создать таблицу индексов, которая содержит индексы и значения ID values из записей. Индекс элемента показывает, какая запись в массиве EmployeeData содержит соответствующие данные.

Type IdIndex

    ID As Integer

    Index As Integer

End Type

‘ Таблица индексов.

Dim IdIndexData(1 To 10000)

Проинициализируем таблицу индексов так, чтобы первый индекс указывал на первую запись данных, второй — на вторую, и т.д.

For i = 1 To 10000

    IdIndexData(i).ID = EmployeeData(i).ID

    IdIndexData(i).Index = i

Next i

Затем, отсортируем таблицу индексов по идентификационному номеру ID. После этого, поле Index в каждом элементе IdIndexData указывает на соответствующую запись данных. Например, первая запись в отсортированном списке — это EmployeeData(IdIndexData(1).Index). На рис. 9.1 показана взаимосвязь между индексом и записью данных до, и после сортировки.

=======226

@Рисунок 9.1. Сортировка с помощью таблицы индексов

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

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

Объединение и сжатие ключей

Иногда можно хранить ключи списка в комбинированной или сжатой форме. Например, можно было бы объединить (combine) в программе два поля, соответствующих имени и фамилии, в одни ключ. Это позволило бы упростить и ускорить сравнение. Обратите внимание на различия между двумя следующими фрагментами кода, которые сравнивают две записи о сотрудниках:

‘ Используя разные ключи.

If emp1.LastName > emp2.LastName Or _

    (emp1.LastName = emp2.LastName And _

        And emp1.FirstName > emp2.FirstName) Then

    DoSomething

 ‘ Используя объединенный ключ.

If emp1.CominedName > emp2.CombinedName Then

    DoSomething

========227

Также иногда можно сжимать (compress) ключи. Сжатые ключи занимают меньше места, уменьшая размер таблиц индексов. Это позволяет сортировать списки большего размера без перерасхода памяти, быстрее перемещать элементы в списке, и часто также ускоряет сравнение элементов.

Одни из методов сжатия строк — кодирование их целыми числами или данными другого числового формата. Числовые данные занимают меньше места, чем строки и сравнение двух численных значений также происходит намного быстрее, чем сравнение двух строк. Конечно, строковые операции неприменимы для строк, представленных числами.

Например, предположим, что мы хотим закодировать строки, состоящие из заглавных латинских букв. Можно считать, что каждый символ — это число по основанию 27. Необходимо использовать основание 27, чтобы представить 26 букв и еще одну цифру для обозначения конца слова. Без отметки конца слова, закодированная строка AA шла бы после строки B, потому что в строке AA две цифры, а в строке B — одна.

Код по основанию 27 для строки из трех символов дает формула 272 * (первая буква - A + 1) + 27 * (вторая буква - A + 1) + 27 * (третья буква - A + 1). Если в строке меньше трех символов, вместо значения (третья буква - A + 1) подставляется 0. Например, строка FOX кодируется так:

272 * (F - A + 1) + 27 * (O - A + 1) + (X - A +1) = 4803

Строка NO кодируется следующим образом:

272 * (N - A + 1) + 27 * (O - A + 1) + (0) = 10.611

Заметим, что 10.611 больше 4803, поскольку NO > FOX.

Таким же образом можно закодировать строки из 6 заглавных букв в виде числа в формате long и строки из 10 букв — как число в формате double. Две следующие процедуры конвертируют строки в числа в формате double и обратно:

Const STRING_BASE = 27

Const ASC_A = 65           ‘ ASCII код для символа "A".

‘ Преобразование строки с число в формате double.

‘

‘ full_len — полная длина, которую должна иметь строка.

‘ Нужна, если строка слишком короткая (например "AX" —

‘ это строка из трех символов).

Function StringToDbl (txt As String, full_len As Integer) As Double

Dim strlen As Integer

Dim i As Integer

Dim value As Double

Dim ch As String * 1

    strlen = Len(txt)

    If strlen > full_len Then strlen = full_len

    value = 0#

    For i = 1 To strlen

        ch = Mid$(txt, i, 1)

        value = value * STRING_BASE + Asc(ch) - ASC_A + 1

    Next i

    For i = strlen + 1 To full_len

        value = value * STRING_BASE

    Next i

End Function

‘ Обратное декодирование строки из формата double.

Function DblToString (ByVal value As Double) As String

Dim strlen As Integer

Dim i As Integer

Dim txt As String

Dim Power As Integer

Dim ch As Integer

Dim new_value As Double

    txt = ""

    Do While value > 0

        new_value = Int(value / STRING_BASE)

        ch = value - new_value * STRING_BASE

        If ch <> 0 Then txt = Chr$(ch + ASC_A - 1) + txt

        value = new_value

    Loop

    DblToString = txt

End Function

===========228

В табл. 9.1 приведено время выполнения программой Encode сортировки 2000 строк различной длины на компьютере с процессором Pentium и тактовой частотой 90 МГц. Заметим, что результаты похожи для каждого типа кодирования. Сортировка 2000 чисел в формате double занимает примерно одинаковое время независимо от того, представляют ли они строки из 3 или 10 символов.

========229

@Таблица 9.1. Время сортировки 2000 строк с использованием различных кодировок в секундах

Можно также кодировать строки, состоящие не только из заглавных букв. Строку из заглавных букв и цифр можно закодировать по основанию 37 вместо 27. Код буквы A будет равен 1, B — 2, … , Z — 26, код 0 будет 27, … , и 9 — 36. Строка AH7 будет кодироваться как 372 * 1 + 37 * 8 + 35 = 1700.

Конечно, при использовании большего основания, длина строки, которую можно закодировать числом типа integer, long или double будет соответственно короче. При основании равном 37, можно закодировать строку из 2 символов в числе формата integer, из 5 символов в числе формата long, и 10 символов в числе формата double.

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

Чтобы облегчить сравнение различных алгоритмов сортировки, программа Sort демонстрирует большинство алгоритмов, описанных в этой главе. Сортировка позволяет задать число сортируемых элементов, их максимальное значение, и порядок расположения элементов - прямой, обратный или расположение в случайном порядке. Программа создает список случайно расположенных чисел в формате long и сортирует его, используя выбранный алгоритм. Вначале сортируйте короткие списки, пока не определите, насколько быстро ваш компьютер может выполнять операции сортировки. Это особенно важно для медленных алгоритмов сортировки вставкой, сортировки вставкой с использованием связного списка, сортировки выбором, и пузырьковой сортировки.

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

В усредненном случае, алгоритму придется провести поиск примерно по половине отсортированного списка для того, чтобы найти местоположение элемента. При этом алгоритм выполняется примерно за 1 + 1 + 2 + 2 + … + N/2, или порядка O(N2) шагов.

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

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

=======235

Пузырьковая сортировка

Пузырьковая сортировка (bubblesort) — это алгоритм, предназначенный для сортировки списков, которые уже находятся в почти упорядоченном состоянии. Если в начале процедуры список полностью отсортирован, алгоритм выполняется очень быстро за время порядка O(N). Если часть элементов находятся не на своих местах, алгоритм выполняется медленнее. Если первоначально элементы расположены в случайном порядке, алгоритм выполняется за время порядка O(N2). Поэтому перед применением пузырьковой сортировки важно убедиться, что элементы в основном расположены по порядку.

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

На рис. 9.2 показано, как алгоритм вначале обнаруживает, что элементы 6 и 3 расположены не по порядку, и поэтому меняет их местами. Во время следующего прохода, меняются местами элементы 5 и 3, в следующем — 4 и 3. После еще одного прохода алгоритм обнаруживает, что все элементы расположены по порядку, и завершает работу.

Можно проследить за перемещениями элемента, который первоначально был расположен ниже, чем после сортировки, например элемента 3 на рис. 9.2. Во время каждого прохода элемент перемещается на одну позицию ближе к своему конечному положению. Он движется к вершине списка подобно пузырьку газа, который всплывает к поверхности в стакане воды. Этот эффект и дал название алгоритму пузырьковой сортировки.

Можно внести в алгоритм несколько улучшений. Во‑первых, если элемент расположен в списке выше, чем должно быть, вы увидите картину, отличную от той, которая приведена на рис. 9.2. На рис. 9.3 показано, что алгоритм вначале обнаруживает, что элементы 6 и 3 расположены в неправильном порядке, и меняет их местами. Затем алгоритм продолжает просматривать массив и замечает, что теперь неправильно расположены элементы 6 и 4, и также меняет их местами. Затем меняются местами элементы 6 и 5, и элемент 6 занимает свое место.

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