- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 2007
- •1. Структуры данных и алгоритмы 6
- •1.2. Информация и ее представление
- •1.2.1. Природа информации
- •1.2.2. Хранение информации
- •1.2.3. Классификация структур данных
- •1.3. Операции над структурами данных
- •1.4. Порядок алгоритма
- •1.5. Структурность данных и технологии программирования
- •Контрольные вопросы
- •2. Простые структуры данных
- •2.1. Порядковые типы
- •2.2. Целочисленный тип
- •2.3. Символьный тип
- •2.4. Перечисляемый тип
- •2.5. Интервальный тип
- •2.6. Логический тип
- •2.7. Битовый тип
- •2.8. Вещественный тип
- •2.9. Указательный тип
- •Контрольные вопросы
- •3. Объектные типы данных
- •3.1. Объявление и реализация классов
- •Interface
- •Implementation
- •3.2. Директивы видимости
- •3.3. Свойства классов
- •3.4. Структурированная обработка ошибок
- •3.5. Применение объектов
- •Контрольные вопросы
- •4. Статические структуры данных
- •4.1. Векторы
- •4.2. Массивы
- •4.3. Множества
- •4.4. Записи
- •4.5. Таблицы
- •4.6. Операции над статическими структурами
- •4.6.1. Алгоритмы поиска
- •4.6.2. Алгоритмы сортировки
- •Самые медленные алгоритмы сортировки
- •Быстрые алгоритмы сортировки
- •Самые быстрые алгоритмы сортировки
- •Сортировка слиянием
- •Контрольные вопросы
- •5. Полустатические структуры данных
- •5.1. Стеки
- •5.1.1. Стеки в вычислительных системах
- •5.2. Очереди fifo
- •5.2.1. Очереди с приоритетами
- •5.2.2. Очереди в вычислительных системах
- •5.3. Деки
- •5.3.1. Деки в вычислительных системах
- •5.4. Строки
- •5.4.1. Операции над строками
- •5.4.2. Представление строк в памяти
- •3 A b d 8 p q r s t u V w
- •V w ptr nil
- •1 8 П р е д с т а в
- •2 7 ? Л е н и е ?
- •1 8 С т р о к и з
- •1 8 В е н ь я м и
- •1 8 С у п р а в л
- •1 8 Я е м о й д л
- •1 4 И н о й ? ? ? ? nil
- •6.2. Связные линейные списки
- •6.2.1. Машинное представление связных линейных списков
- •Inf next
- •Inf next
- •Inf nil
- •6.2.2. Реализация операций над связными линейными списками
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •6.2.3. Применение линейных списков
- •6.3. Нелинейные разветвленные списки
- •6.3.1. Основные понятия
- •6.3.2. Представление списковых структур в памяти
- •6.3.3. Операции обработки списков
- •6.4. Язык программирования lisp
- •6.5. Управление динамически выделяемой памятью
- •Контрольные вопросы
- •7. Нелинейные структуры данных
- •7.1. Графы и деревья
- •(B) (a) (b) (a)
- •V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)
- •7.3. Бинарные деревья
- •7.3.1. Представление бинарных деревьев
- •7.3.2. Прохождение бинарных деревьев
- •7.4. Алгоритмы на деревьях
- •7.4.1. Сортировка с прохождением бинарного дерева
- •7.4.2. Сортировка методом турнира с выбыванием
- •7.4.3. Применение бинарных деревьев для сжатия информации
- •7.4.4. Представление выражений с помощью деревьев
- •7.5. Представление сильноветвящихся деревьев
- •Контрольные вопросы
- •8. Методы ускорения доступа к данным
- •8.1. Хеширование данных
- •8.1.1. Функции хеширования
- •8.1.2. Оценка качества хеш-функции
- •8.1.3. Методы разрешения коллизий
- •8.1.4. Переполнение таблицы и рехеширование
- •8.2. Организация данных для поиска по вторичным ключам
- •8.2.1. Инвертированные индексы
- •8.2.2. Битовые карты
- •Контрольные вопросы
- •Листинги рабочих примеров
- •1. Создание и управление списковыми объектами
- •Interface
- •Implementation
- •Interface
- •Implementation
- •3. Моделирование работы стека
- •Interface
- •Implementation
- •Interface
- •Implementation
- •4. Создание и редактирование бинарных деревьев
- •5. Создание и редактирование сильноветвящихся деревьев
- •Задания для самостоятельной работы
- •Литература
- •144Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
Сортировка слиянием
Алгоритмы сортировки слиянием привлекают простотой и наличием важных особенностей: они имеют порядок O(n·log2n), не имеют худших случаев, допускают сортировку содержимого файлов, размер которых слишком велик для полного размещения в памяти.
Для пояснения алгоритма сортировки поясним сначала принцип слияние. Пусть имеются два отсортированных в порядке возрастания массива p[1], p[2], ..., p[n] и q[1], q[2], ..., q[n] и имеется пустой массив r[1], r[2], ..., r[2n], который требуется заполнить значениями массивов p и q в порядке возрастания.
Для слияния выполняются следующие действия: сравниваются p[1] и q[1], и меньшее из значений записывается в r[1]. Предположим, это значение p[1]. Тогда p[2] сравнивается с q[1] и меньшее из значений заносится в r[2]. Предположим, это значение q[1]. Тогда на следующем шаге сравниваются значения p[2] и q[2] и т.д., пока не будет достигнута граница одного из массивов. Тогда остаток другого массива просто дописывается в конец результирующего массива r.
Такой алгоритм известен как алгоритм двухпутевого слияния. На практике элементы не удаляются из исходных массивов, а используются указатели на текущие начальные элементы, которые при копировании передвигаются на следующий элемент.
Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих массивах. Если в первом находится n элементов, а во втором – m, то в худшем случае потребуется (n+m) сравнений. Следовательно, алгоритм двухпутевого слияния принадлежит к классу O(n). Пример слияния двух массивов показан на рис. 4.2.
На основе алгоритма двухпутевого слияния можно прийти к рекурсивному определению сортировки слиянием: исходный массив следует разделить на две половины, применить к каждой половине алгоритм сортировки слиянием, а затем с помощью алгоритма двухпутевого слияния объединить подсписки в один отсортированный массив. Рекурсивные вызовы завершаются, когда подсписок n-ого уровня, переданный алгоритму сортировки, будет содержать всего один элемент, поскольку он, очевидно, уже отсортирован.
Сортировка слиянием обладает единственным недостатком – требуется наличие третьего списка, в котором будут храниться результаты слияния. Размер требуемой дополнительной памяти составляет до половины размера исходно массива.
Пример реализации алгоритма приведен ниже. Помимо известных параметров процедура требует передачи указателя на временный массив, который будет использоваться для выполнения процедуры слияния.
{ Сортировка слиянием }
procedure MSS(aList: TList; aFirst, aLast: Integer;
aCompare: TCompareFunc; aTempList: PPointerList);
var
Mid, i, j, ToInx,
FirstCount: Integer;
begin
{ Вычислить среднюю точку }
Mid:=(aFirst + aLast) div 2;
{ Рекурсивная сортировка слиянием первой и второй половин списка }
if aFirst < Mid then
MSS(aList, aFirst, Mid, aCompare, aTempList);
if (Mid+1) < aLast then
MSS(aList, Mid+1, aLast, aCompare, aTempList);
{ Скопировать первую половину списка во вспомогательный список }
FirstCount:=Mid-aFirst+1;
Move(aList.List[aFirst], aTempList[0], FirstCount*SizeOf(Pointer));
{ Установить значения индексов: i - индекс для вспомогательного списка
(т.е. первой половины); j - индекс для второй половины списка;
ToInx - индекс в результирующем списке, куда будут копироваться
отсортированные элементы }
i:=0; j:=Mid+1; ToInx:=aFirst;
{ Выполнить слияние двух списков; повторять
пока один из списков не опустеет }
while (i < FirstCount) and (j <= aLast) do
begin
{ Определить элемент с наименьшим значением из следующих
элементов в обоих списках и скопировать его; увеличить
значение соответствующего индекса }
if aCompare(aTempList[i], aList.List[j]) <= 0 then
begin
aList.List[ToInx]:=aTempList[i];
Inc(i);
end
else
begin
aList.List[ToInx]:=aList.List[j];
Inc(j);
end;
{ В объединенных списках есть еще один элемент }
Inc(ToInx);
end;
{ Если в первом подсписке остались элементы, скопировать их }
if i < FirstCount then
Move(aTempList[i], aList.List[ToInx], (FirstCount - i)*SizeOf(Pointer));
{ Если во втором списке остались элементы, то они уже находятся в нужных
позициях, т.е. сортировка завершена; если второй список пуст, сортировка
также завершена }
end;
procedure MergeSortStd(aList: TList;
aFirst, aLast: Integer; aCompare: TCompareFunc);
var
TempList: PPointerList;
ItemCount: Integer;
begin
{ Есть хотя бы два элемента для сортировки }
if aFirst < aLast then
begin
{ создать временный список указателей }
ItemCount:=aLast-aFirst+1;
GetMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));
try
MSS(aList, aFirst, aLast, aCompare, TempList);
finally
FreeMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));
end;
end;
end;
Процедура сортировки рекурсивно вызывает саму себя для сортировки первой и второй половин переданной ей части массива. Затем она копирует первую половину во вспомогательный массив и выполняется слияние двух списков. Поскольку элементы перемещаются только при выполнении процедуры слияния, устойчивость всей сортировки будет зависеть от устойчивости самого слияния двух половин.
Обратите внимание, если в обеих половинах имеются элементы с одинаковым значением, оператор сравнения гарантирует, что первым в результирующий список попадет элемент из первой половины списка. Следовательно, операция слияния сохраняет относительный порядок следования элементов, и сортировка слиянием является устойчивой.
Рис. 4.2. Пример слияния двух массивов.