- •Общие соображения
- •Таблицы указателей
- •Объединение и сжатие ключей
- •Сортировка выбором
- •Рандомизация (можно пропустить)
- •Сортировка вставкой
- •Вставка в связных списках
- •Пузырьковая сортировка
- •Быстрая сортировка
- •Сортировка слиянием
- •Пирамидальная сортировка (Изучить самостоятельно)
- •Сортировка подсчетом (Самостоятельно)
- •Блочная сортировка (Самостоятельно)
- •Блочная сортировка с применением связного списка
- •Блочная сортировка на основе массива
21
Сортировка
Информатика и компьютерная техника
© Велигура А.В., кафедра экономической кибернетики, 2004
Сортировка — одна из наиболее активно изучаемых тем в компьютерных алгоритмах по ряду причин. Во-первых, сортировка — это задача, которая часть встречается во многих приложениях. Почти любой список данных будет нести больше смысла, если его отсортировать каким‑либо образом. Часто требуется сортировать данные несколькими различными способами.
Во-вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве.
Наконец, сортировка является одной из немногих задач с точными теоретическими ограничениями производительности. Можно показать, что время выполнения любого алгоритма сортировки, который использует сравнения, составляет порядка O(N * log(N)). Некоторые алгоритмы достигают теоретического предела, то есть они являются оптимальными в этом смысле. Есть даже ряд несколько алгоритмов, которые используют другие методы вместо сравнений, которые выполняются быстрее, чем за время порядка O(N *log(N)).
Общие соображения
Таблицы указателей
При сортировке элементов данных, программа организует из них некоторое подобие структуры данных. Этот процесс может быть быстрым или медленным в зависимости от типа элементов. Перемещение целого числа на новое положение в массиве может быть намного быстрее, чем перемещение определенной пользователем структуры данных. Если эта структура представляет собой список данных о сотруднике, содержащий тысячи байт информации, копирование одного элемента может занять достаточно много времени.
Для повышения производительности при сортировке больших объектов можно помещать ключевые поля данных, используемые для сортировки, в таблицу индексов. В этой таблице находятся ключи к записям и индексы элементов другого массива, в котором и находятся записи данных. Например, предположим, что вы собираетесь отсортировать список записей о сотрудниках, определяемый следующей структурой:
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).
Для того, чтобы сортировать данные в разном порядке, можно создать несколько различных таблиц индексов и управлять ими по отдельности. В приведенном примере можно было бы создать еще одну таблицу индексов, упорядочивающую сотрудников по фамилии. При добавлении или удалении записи необходимо обновлять каждую таблицу индексов независимо.
Объединение и сжатие ключей
Иногда можно хранить ключи списка в комбинированной или сжатой форме. Например, можно было бы объединить(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
Также иногда можно сжимать(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
Можно также кодировать строки, состоящие не только из заглавных букв. Строку из заглавных букв и цифр можно закодировать по основанию 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.