- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Сортировка прямым слиянием
Один из методов сортировки слиянием называется прямым (простым) слиянием и состоит в следующем:
исходная последовательность а разбивается на две половины b и с;
последовательности b и c сливаются при помощи объединения отдельных элементов в упорядоченные пары;
полученной после слияния последовательности присваивается имя а, и повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются в упорядоченные четверки;
предыдущие шаги повторяются: четверки сливаются в восьмерки, и весь процесс продолжается до тех пор, пока не будет упорядочена вся последовательность, при этом длины сливаемых последовательностей каждый раз удваиваются.
В качестве примера рассмотрим последовательность
a: 44, 55, 12, 42, 94, 18, 06, 67
На первом шаге разбиение дает последовательности
b: 44, 55, 12, 42
c: 94, 18, 06, 67
Разбиение предполагает, что длина всей последовательности известна и равна N. Тогда начальные N/2 элементов на ленте a последовательно переписываются на ленту b, а элементы второй половины на ленту c. После этого лента a очищается.
Затем выполняется фаза слияния. Поскольку в текущий момент доступен только один элемент на ленте, то слияние выполняется так: извлекаются начальные элементы с лент b и c (в примере это элементы 44 и 94). Эти элементы сравниваются друг с другом, и меньший элемент (44 из b) записывается на ленту a. Затем выполняется переход к следующему элементу (к 55 на b) на той ленте, откуда он был извлечен элемент, посланный на ленту a. Теперь второй извлеченный элемент может быть записан на ленту a вторым по порядку с гарантией того, что он больше ранее записанного. Поскольку извлечение сопровождается переходом на одну позицию, то на следующем шаге начальными становятся те элементы, которые раньше были вторыми на лентах b и c. Эти элементы (55 и 18) сливаются на a, образуя упорядоченную пару.
Слияние отдельных компонент (которые являются упорядоченными последовательностями длины 1) в упорядоченные пары дает
a: 44, 94, | 18, 55, | 06, 12, | 42, 67 .
После завершения фазы слияния ленты b и c очищаются.
Новое разбиение пополам и слияние упорядоченных пар дают
a: 06, 12, 44, 94, | 18, 42, 55, 67.
При втором слиянии учитывается то обстоятельство, что последовательные пары элементов упорядочены.
Третье разбиение и слияние приводят, наконец, к нужному результату:
a: 06, 12, 18, 42, 44, 55, 67, 94
Операция, которая однократно обрабатывает все множество данных, называется фазой, а наименьший подпроцесс, который, повторяясь, образует процесс сортировки, называется проходом или этапом. В приведенном выше примере сортировка производится за три прохода, каждый проход состоит из фазы разбиения и фазы слияния. Для выполнения сортировки требуются три ленты, поэтому процесс называется трехленточным слиянием.
Собственно говоря, фазы разбиения не относятся к сортировке, поскольку они никак не переставляют элементы; в каком-то смысле они непродуктивны, хотя и составляют половину всех операций переписи. Их можно удалить, объединив фазы разбиения и слияния. Вместо того чтобы сливать элементы в одну последовательность, результат слияния сразу распределяют на две ленты, которые на следующем проходе будут входными. В отличие от двухфазного слияния этот метод называют однофазным или сбалансированным слиянием. Он имеет явные преимущества, так как требует вдвое меньше операций переписи, но это достигается ценой использования четвертой ленты.
Разберем программу слияния подробно; предположим, что данные расположены в виде массива, который, однако, можно рассматривать только строго последовательно.
Вместо двух файлов можно легко использовать один массив, если рассматривать его как последовательность с двумя концами. Вместо того чтобы сливать элементы из двух исходных файлов, мы можем брать их с двух концов массива. Направление пересылки сливаемых элементов меняется (переключается) после каждой упорядоченной пары на первом проходе, после каждой упорядоченной четверки на втором проходе и т. д.; таким образом равномерно заполняются две выходные последовательности, представленные двумя концами одного массива (выходного). После каждого прохода два массива меняются ролями: входной становится выходным и наоборот.
Программу можно еще больше упростить, объединив два концептуально различных массива в один двойной длины. Итак, данные будут представлены следующим образом:
a: Аrray[1..2*N] Оf TElement;
Пусть индексы i и j указывают два исходных элемента, тогда как k и l обозначают два места пересылки. Исходные данные это элементы а[1], ..., а[N]. Очевидно, что нужна булевская переменная up для указания направления пересылки данных. Условие up=true будет означать, что на текущем проходе компоненты a[1], …, a[N] будут пересылаться «направо» в переменные a[N+1], …, a[2N]; если up=false, то a[N+1], …, a[2N] должны переписываться «налево» в a[1], …, a[N]. Значение up строго чередуется между двумя последовательными проходами. И наконец, вводится переменная р для обозначения длины сливаемых последовательностей (р-наборов). Ее начальное значение равно 1, и оно удваивается перед каждым очередным проходом. Для простоты мы будем считать, что N (число элементов в таблице) всегда степень двойки. Итак, программа простого слияния выглядит следующим образом:
Procedure Mergesort;
Var i, j, Jc, l, t: Word; uр: Вооlеап; p, h, m, q, r : Word ;
{а имеет индексы 1..2*N}
Begin
up:= true; p:= 1;
Repeat
h:= 1; m:= N;
If up Then Begin i:= 1; j:= N; k:= N+1; l:= 2*N End
Else Begin k:= 1; l:= N; i:= N+1; j:= 2*N End;
Repeat {слияние серий из i и j в k}
If m>=p Then q:= p Else q:= m;
m:= m-q;
If m>=p Then r:= p Else r:= m;
m:= m-r;
While (q<>0) And (r<>0) Do Begin {слияние}
If a[i].Key < a[j].Key Then Begin
a[k]:= a[i]; k:= k+h; i:= i+1; q:= q-1
End
Else Begin
a[k]:= a[j]; k:= k+h; j:=j-1; r:=r-1
End
End;
{копирование остатка серии из j}
While r<>0 Do Begin
a[k]:= a[j]; k:= k+h; j:= j-1; r:= r -1
End;
{копирование остатка серии из i}
While q<>0 Do Begin
a[k]:= a[i]; k:= k+h; i:= i+1; q:= q-l
End;
h:= -h; t:= k; k:= l; l:=t
Until m=0;
up:= -up; p:=2*p;
Until p>=n
If -up Then For i:=1 To N Do a[i]:=a[i+N];
End; {Mergesort}
Алгоритм сортировки прямым слиянием выдерживает сравнение даже с усовершенствованными методами внутренней сортировки. Но затраты на управление индексами довольно высоки, кроме того, существенным недостатком является использование памяти размером 2N элементов. Поэтому сортировка слиянием редко применяется при работе с массивами, т. е. данными, расположенными в оперативной памяти.