Основы дискретной математики

Федеральное агентство по образованию

Новомосковский институт (филиал)

Государственного образовательного учреждения высшего профессионального образования

«Российский химико-технологический университет имени Д.И. Менделеева»

T.П. Тюрина, В.И. Емельянов

Практикум по дискретной математике

(часть 1)

Учебно-методическое пособие

Новомосковск 2007

Оглавление

• Введение 5
• Практическая работа № 1 Изучение методов сортировки данных 6
• 1.1 Теоретическая часть 6
• 1.2 Методы, используемые при поиске и сортировке 9
• 1.2.1 Основные понятия 9
• 1.2.2 Поиск 10
• 1.2.3 Оценки времени исполнения 18
• 1.2.4 Сортировки 19
• 1.3 Практическая часть 40
• 1.3.1 Содержание отчёта по практической работе 40
• 1.3.2 Приложение на Delphi, в котором представлена работа некоторых методов сортировки и поиска 40
• 1.3.3 Пример выполнения 51
• 1.3.4 Варианты заданий 53
• 1.4 Вопросы для самопроверки 62
• Практическая работа № 2 Представление множеств в компьютере 64
• 2.1 Теоретическая часть 64
• 2.1.1 Множества и операции над ними 64
• 2.1.2 Представление множеств и отношений в программах 67
• 2.1.4 Представление множеств в приложениях на Delphi 82
• 2.1.5 Характеристический вектор множества 83
• 2.2 Практическая часть 85
• 2.2.1 Задание к работе 85
• 2.2.2 Примеры выполнения 86
• 2.2.3 Варианты заданий 90
• 2.3 Вопросы для самопроверки 92
• Практическая работа № 3 Элементы теории графов 94
• 3.1 Теоретическая часть 94
• 3.2 Практическая часть 111
• 3.2.1 Задание к работе 111
• 3.2.2 Примеры выполнения 111
• 3.2.3 Вариантв заданий 117
• Практическая работа № 4 Элементы теории множеств и алгебры логики 122
• 4.1 Указание к выполнению 122
• 4.2 Задание к работе 122
• 4.3 Практическая часть 122
• 4.4 Вопросы для самопроверки 133
• Практическая работа № 5 Исследование логических функций 135
• 5.1 Задание к работе 135
• 5.2 Практическая часть 135
• 5.2.1 Пример выполнения 135
• 5.2.2 Варианты заданий 138
• 5.3 Вопросы для самопроверки 140
• Практическая работа № 6 Изучение методов минимизации логических функций 142
• 6.1 Краткие теоретические сведения 142
• 6.2 Практическая часть 144
• 6.2.1 Задание к работе 144
• 6.2.2 Примеры выполнения 144
• 6.3 Вопросы для самопроверки 147
• Практическая работа № 7 Моделирование работы узлов компьютера с помощью Еxcel 149
• 7.1 Теоретическая часть 149
• 7.2 Практическая часть 152
• 7.2.1 Схемы сравнения кодов 153
• 7.2.2 Дешифраторы 158
• 7.3 Задания к работе 160
• 7.4 Вопросы для самопроверки 164
• Список литературы 165
• Введение
• В практикум включены необходимые теоретические сведения, содержание работ, примеры выполнения, варианты заданий, вопросы по самоконтролю знаний для 7 практических работ. Некоторые практические работы относятся к нескольким разделам дисциплины, поэтому для них можно, не «привязывая» к конкретному разделу, выполнять описание в виде отдельных приложений. Все практические работы выполняются с использованием компьютера.
• Практическая часть дисциплины адаптирована для обучения будущих специалистов по обработке информации. Практикум содержит дополнительные сведения из теории множеств, теории графов и алгебры логики, описание практических работ, запланированных для выполнения студентами в процессе изучения предмета с привлечением средств Excel, Delphi.
• Содержание пособия полностью соответствует требованиям программы дисциплины и относится к практической части. Подготовка рукописи вызвана необходимостью создания учебного пособия для студентов, т. к. подобные практикумы по дискретной математике отсутствуют. Практикум содержит краткое изложение теории, которая относится непосредственно к выполнению работ, варианты заданий, примеры выполнения. В конце каждого раздела приведены контрольные вопросы. Студенту предлагается выполнить индивидуальные задания.
• Некоторые практические работы являются традиционными, и составные части их представлены в учебниках и методических разработках других вузов, основная часть является авторской. Недостатком является отсутствие практической работы по нечётким множествам. Пособие может быть рекомендовано студентам дневной и заочной форм обучения.
• Практическая работа № 1. Изучение методов сортировки данных
• Цель работы: изучение наиболее известных методов сортировки данных и их использование на примерах конкретных задач.
• 1.1 Теоретическая часть
• Для дискретного анализа характерно, что самые простые, казалось бы, ничем не примечательные задачи могут быть предметом серьёзного научного исследования. Здесь мы рассматриваем одну из таких простых задач, которая часто встречается в приложениях, называется задачей сортировки и до сих пор остается интересной.
• При рассмотрении данного круга задач необходимо предварительно изучить тему «Множества и отношения». Рефлексивное, транзитивное, но антисимметричное отношение R на множестве A называется частичным порядком. Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях можно считать, что один элемент множества превосходит другой.
• Примеры частичных порядков.
• «» на множестве вещественных чисел;
• «» на подмножествах универсального множества;
• «…делит…» на множестве натуральных чисел.
• Множества с частичным порядком принято называть частично упорядоченными множествами (ч. у. м.).
• Если R - отношение частичного порядка на множестве A, то при х y и xRy мы называем x предшествующим элементом или предшественником, а y - последующим. У произвольно взятого элемента y может быть много предшествующих элементов. Однако если x предшествует y, и не существует таких элементов z, для которых xRz и zRy, x называется непосредственным предшественником (иначе говорят, что y покрывает x) и обозначается x<y [3].
• Линейным порядком на множестве A называется отношение частичного порядка, при котором из любой пары элементов можно выделить предшествующий и последующий.
• Постановка задачи: пусть задано конечное множество А, состоящее из n элементов a_i, на нём задано отношение линейного порядка Р.
• Требуется перенумеровать элементы А числами от 1 до n таким образом, чтобы из того, что i<j следовало (a_i, a_j) Є P. Выполнение этой задачи называется сортировкой массива данных [3].
• Способы сравнения могут быть очень разнообразными, но в большинстве случаев они исходят из двух базовых элементарных упорядочений: упорядочение чисел по значению и упорядочение слов по алфавиту.
• Потребность в сортировке больших объёмов данных ощущалась очень давно, например, в комплекте счётно-аналитических машин Холлерита была специальная сортирующая машина.
• Во многих задачах требуется иметь данные, расположенные в порядке возрастания или в порядке убывания. Такое упорядочение в программировании называется сортировкой. Сортировка применяется во многих задачах. Существуют различные методы сортировки: одни из них просты, но более медленные, другие быстрые, но более сложные. Одни сортируют каждый массив заново, другие распознают уже упорядоченные части массива и поэтому работают быстрее.
• Выдающийся специалист по программированию Д. Кнут посвятил сортировке и поиску данных почти весь второй том трудов «Искусство программирования для ЭВМ» [4].
• Сортировка данных - обработка информации, в результате которой элементы её (записи) располагаются в определённой последовательности в зависимости от значения некоторых признаков элементов, называемых ключевыми.
• Наиболее распространёнными видами сортировки данных являются упорядочение массива записей - расположение записей сортируемого массива данных в порядке монотонного изменения значения ключевого признака. Сортировка данных позволяет сократить в десятки раз продолжительность решения задач, связанных с обработкой больших массивов записей. Такое ускорение происходит за счёт сокращения времени поиска записей с определёнными значениями ключевых признаков. Упорядочение осуществляется в процессе многократного просмотра исходного массива.
• Одними из важнейших процедур обработки структурированной информации являются сортировка и поиск. Сортировкой также называют процесс перегруппировки заданной последовательности (кортежа) объектов в некотором определенном порядке. Определенный порядок (например, упорядочение в алфавитном порядке, по возрастанию или убыванию количественных характеристик, по классам, типам и т. п.) в последовательности объектов необходим для удобства работы с этими объектами. В частности, одной из целей сортировки является облегчение последующего поиска элементов в отсортированном множестве. Под поиском подразумевается процесс нахождения в заданном множестве объекта, обладающего свойствами или качествами задаваемого априори эталона (или шаблона).
• Например, требуется решить задачу: даны целые числа x, a₁, a₂, …, a_n (n>0). Определить, каким по счёту идёт в последовательности a₁, a₂, …, a_n член, равный x. Если такого члена нет, то предусмотреть соответствующее сообщение.
• В этом примере мы сталкиваемся с задачей поиска. «Одно из наиболее часто встречающихся в программировании действий - поиск. Он же представляет собой идеальную задачу, на которой можно испытывать различные структуры данных…» - пишет Н. Вирт [14]. Теория поиска - важный раздел теории информации.
• Очевидно, что с отсортированными (упорядоченными) данными работать намного легче, чем с произвольно расположенными. Упорядоченные данные позволяют эффективно их обновлять, исключать, искать нужный элемент и т. п. Достаточно представить, например, словари, справочники, списки кадров в неотсортированном виде и сразу становится ясным, что поиск нужной информации является труднейшим делом.
• 1.2 Методы, используемые при поиске и сортировке
• 1.2.1 Основные понятия
• Существуют различные алгоритмы сортировки данных. И понятно, что не существует универсального, наилучшего во всех отношениях алгоритма сортировки. Эффективность алгоритма зависит от множества факторов, среди которых можно выделить основные:
• - числа сортируемых элементов;
• - степени начальной отсортированности (диапазона и распределения значений сортируемых элементов);
• - необходимости исключения или добавления элементов;
• - доступа к сортируемым элементам (прямого или последовательного). Принципиальным для выбора метода сортировки является последний фактор [16].
• Если данные могут быть расположены в оперативной памяти, то к любому элементу возможен прямой доступ. Удобной структурой данных в этом случае выступает массив сортируемых элементов. Если данные размещены на внешнем носителе в файле последовательного доступа, то к ним можно обращаться последовательно. В качестве структуры подобных данных можно взять файловый тип [9].
• В этой связи выделяют сортировку двух классов объектов: массивов (внутренняя сортировка) и файлов (внешняя сортировка).
• Процедура сортировки предполагает, что при наличии некоторой упорядочивающей функции F расположение элементов исходного множества меняется таким образом, что
• ,
• где знак неравенства понимается в смысле того порядка, который установлен в сортируемом множестве.
• Поиск и сортировка являются классическими задачами теории обработки данных, решают эти задачи с помощью множества различных алгоритмов. Рассмотрим наиболее популярные из них.
• 1.2.2 Поиск
• Для определенности примем, что множество, в котором осуществляется поиск, задано как массив:

var a: array [0..N] of item;

где item - заданный структурированный тип данных, обладающий хотя бы одним полем (ключом), по которому необходимо проводить поиск.

Результатом поиска, как правило, служит элемент массива, равный эталону, или отсутствие такового.

Важно знать и про ассоциативную память. Это можно понимать как деление памяти на порции (называемые записями), и с каждой записью ассоциируется ключ. Ключ - это значение из некоторого вполне упорядоченного множества, а записи могут иметь произвольную природу и различные параметры. Доступ к данным осуществляется по значению ключа, которое обычно выбирается простым, компактным и удобным для работы.

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

Таблица расстановки.

Поиск, вставка и удаление, как известно, - основные операции при работе с данными [16]. Мы начнем с исследования того, как эти операции реализуются над самыми известными объектами - массивами и (связанными) списками.

Массивы

На рисунке 1.1 показан массив из семи элементов с числовыми значениями. Чтобы найти в нем нужное нам число, мы можем использовать линейный поиск (процедура представлена на псевдокоде, подобном языку Паскаль):

int function SequentialSearch (Array A, int Lb, int Ub, int Key);

begin

for i = Lb to Ub do

if A (i) = Key then

return i;

return -1;

end;

Максимальное число сравнений при таком поиске - 7; оно достигается в случае, когда нужное нам значение находится в элементе A[6]. Различают поиск в упорядоченном и неупорядоченном массивах. В неупорядоченном массиве, если нет никакой дополнительной информации об элементе поиска, его выполняют с помощью последовательного просмотра всего массива и называют линейным поиском. Рассмотрим программу, реализующую линейный поиск. Очевидно, что в любом случае существуют два условия окончания поиска: 1) элемент найден; 2) весь массив просмотрен, и элемент не найден. Приходим к программе:

While (a[i]<>x) and (i<n) do Inc(i);

If a[i]<>x then Write (`Заданного элемента нет')

Если известно, что данные отсортированы, можно применить двоичный поиск:

int function BinarySearch (Array A, int Lb, int Ub, int Key);

begin

do forever

M = (Lb + Ub)/2;

if (Key < A[M]) then

Ub = M - 1;

else if (Key > A[M]) then

Lb = M + 1;

else

return M;

if (Lb > Ub) then

return -1;

end;

Переменные Lb и Ub содержат, соответственно, верхнюю и нижнюю границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится равным (M - 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска - всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Рисунок 1.1 - Массив

Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Кроме поиска нам необходимо бывает вставлять и удалять элементы. К сожалению, массив плохо приспособлен для выполнения этих операций. Например, чтобы вставить число 18 в массив на рисунке 1.1, нам понадобится сдвинуть элементы A[3]… A[6] вниз - лишь после этого мы сможем записать число 18 в элемент A[3]. Аналогичная проблема возникает при удалении элементов. Для повышения эффективности операций вставки / удаления предложены связанные списки.

Иначе двоичный поиск (бинарный поиск) называют поиском делением пополам. В большинстве случаев процедура поиска применяется к упорядоченным данным (телефонный справочник, библиотечные каталоги и пр.).

Односвязные списки

На рисунке 1.2 те же числа, что и раньше, хранятся в виде связанного списка; слово «связанный» часто опускают. Предполагая, что X и P являются указателями, число 18 можно вставить в такой список следующим образом:

X->Next = P->Next;

P->Next = X;

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



Рисунок 1. 2 - Односвязный список

Поиск в бинарных деревьях

Мы использовали двоичный поиск для поиска данных в массиве. Этот метод чрезвычайно эффективен, поскольку каждая итерация вдвое уменьшает число элементов, среди которых нам нужно продолжать поиск. Однако операции вставки и удаления элементов не столь эффективны. Двоичные деревья позволяют сохранить эффективность всех трех операций - если работа идет со «случайными» данными. В этом случае время поиска оценивается как O (lg n). Наихудший случай - когда вставляются упорядоченные данные. В этом случае оценка время поиска - O(n).

Двоичное дерево - это дерево, у которого каждый узел имеет не более двух наследников. Пример бинарного дерева приведен на рисунке 1.5. Предполагая, что Key содержит значение, хранимое в данном узле, мы можем сказать, что бинарное дерево обладает следующим свойством: у всех узлов, расположенных слева от данного узла, значение соответствующего поля меньше, чем Key, у всех узлов, расположенных справа от него, - больше. Вершину дерева называют его корнем. Узлы, у которых отсутствуют оба наследника, называются листьями. Корень дерева на рисунке 1.3 содержит число 20, а листья - 4, 16, 37 и 43. Высота дерева - это длина наидлиннейшего из путей от корня к листьям. В нашем примере высота дерева равна 2.



Рисунок 1.3 - Двоичное дерево

Чтобы найти в дереве какое-то значение, мы стартуем из корня и движемся вниз. Например, для поиска числа 16, мы замечаем, что 16 20, и потому идем влево. При втором сравнении имеем 16 7, так что мы движемся вправо. Третья попытка успешна - мы находим элемент с ключом, равным 16.

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

Рисунок 1.4 - Несбалансированное бинарное дерево

Вставка и удаление

Чтобы лучше понять, как дерево становится несбалансированным, посмотрим на процесс вставки пристальнее. Чтобы вставить 18 в дерево на рисунке 1.3 мы ищем это число. Поиск приводит нас в узел 16, где благополучно завершается. Поскольку 18 16, мы попросту добавляет узел 18 в качестве правого потомка узла 16 (рисунок 1.5).

Теперь мы видим, как возникает несбалансированность дерева. Если данные поступают в возрастающем порядке, каждый новый узел добавляется справа от последнего вставленного. Это приводит к одному длинному списку. Обратите внимание: чем более «случайны» поступающие данные, тем более сбалансированным получается дерево.

Удаления производятся примерно так же - необходимо только позаботиться о сохранении структуры дерева. Например, если из дерева на рисунке 1.5 удаляется узел 20, его сначала нужно заменить на узел 37. Это даст дерево, изображенное на рисунок 1.6. Рассуждения здесь примерно следующие. Нам нужно найти потомка узла 20, справа от которого расположены узлы с большими значениями. Таким образом, нам нужно выбрать узел с наименьшим значением, расположенный справа от узла 20. Чтобы найти его, нам и нужно сначала спуститься на шаг вправо (попадаем в узел 38), а затем на шаг влево (узел 37); эти двухшаговые спуски продолжаются, пока мы не придем в концевой узел, лист дерева.

Рисунок 1.5 - Бинарное дерево после добавления узла 18	Рисунок 1.6 - Бинарное дерево после удаления узла 20

Разделенные списки

Разделенные списки - это связные списки, которые позволяют вам прыгнуть (skip) к нужному элементу. Это позволяет преодолеть ограничения последовательного поиска, являющегося основным источником неэффективного поиска в списках. В то же время вставка и удаление остаются сравнительно эффективными. Оценка среднего времени поиска в таких списках есть O (lg n). Для наихудшего случая оценкой является O(n), но худший случай крайне маловероятен.

Идея, лежащая в основе разделенных списков, очень напоминает метод, используемый при поиске имен в адресной книжке. Чтобы найти имя, вы помечаете буквой страницу, откуда начинаются имена, начинающиеся с этой буквы. На рисунке 1.6, например, самый верхний список представляет обычный односвязный список. Добавив один «уровень» ссылок, мы ускорим поиск. Сначала мы пойдем по ссылкам уровня 1, затем, когда дойдем до нужного отрезка списка, пойдем по ссылкам нулевого уровня.

Эта простая идея может быть расширена - мы можем добавить нужное число уровней. Внизу на рисунке 1.6 мы видим второй уровень, который позволяет двигаться еще быстрее первого. При поиске элемента мы двигаемся по этому уровню, пока не дойдем до нужного отрезка списка. Затем мы еще уменьшаем интервал неопределенности, двигаясь по ссылкам 1_го уровня. Лишь после этого мы проходим по ссылкам 0_го уровня.

Вставляя узел, нам понадобится определить количество исходящих от него ссылок. Эта проблема легче всего решается с использованием случайного механизма: при добавлении нового узла мы «бросаем монету», чтобы определить, нужно ли добавлять еще слой. Например, мы можем добавлять очередные слои до тех пор, пока выпадает «решка». Если реализован только один уровень, мы имеем дело фактически с обычным списком и время поиска есть O(n). Однако если имеется достаточное число уровней, разделенный список можно считать деревом с корнем на высшем уровне, а для дерева время поиска есть O (lg n).

Поскольку реализация разделенных списков включает в себя случайный процесс, для времени поиска в них устанавливаются вероятностные границы. При обычных условиях эти границы довольно узки. Например, когда мы ищем элемент в списке из 1000 узлов, вероятность того, что время поиска окажется в 5 раз больше среднего, можно оценить как 1/ 1,000,000,000,000,000,000 (рисунок 1.7).

Рисунок 1.7 - Устройство разделенного списка

1.2.3 Оценки времени исполнения

Для оценки эффективности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения. Например, мы можем утверждать, что время поиска есть O(n) (читается так: о большое от n). Это означает, что при больших n время поиска не сильно больше, чем количество элементов. Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n²), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите таблицу 1.1, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций. Скорость роста O(log₂n) характеризует алгоритмы типа двоичного поиска.

Таблица 1.1 - Скорость роста нескольких функций O()

n	log2 n	n log2 n	n1.25	n2
1	0	0	1	1
16	4	64	32	256
256	8	2,048	1,024	65,536
4,096	12	49,152	32,768	16,777,216
65,536	16	1,048,565	1,048,476	4,294,967,296
1,048,476	20	20,969,520	33,554,432	1,099,301,922,576
16,775,616	24	402,614,784	1,073,613,825	281,421,292,179,456

Если считать, что числа в таблице 1.1 соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму со временем работы O(log₂ n) потребуется 20 микросекунд, алгоритму со временем работы O(n^1.25) - порядка 33 секунд, алгоритму со временем работы O(n²) - более 12 дней. В нижеследующем тексте для каждого алгоритма приведены соответствующие O_оценки. Более точные формулировки и доказательства можно найти в [12], [15].

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

Связанные списки позволяют эффективно вставлять и удалять элементы, но поиск в них последователен и потому отнимает много времени. Имеются алгоритмы, позволяющие эффективно выполнять все три операции.

1.2.4 Сортировки

Сортировка вставками

Один из простейших способов отсортировать массив - сортировка вставками. В обычной жизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортировать имеющиеся у вас карты, вы вынимаете карту, сдвигаете оставшиеся карты, а затем вставляете карту на нужное место. Процесс повторяется до тех пор, пока хоть одна карта находится не на месте. Как среднее, так и худшее время для этого алгоритма - O(n²). Дальнейшую информацию можно получить в книге Кнута [4].

На рисунке 1.8 (a) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз - до тех пор, пока не найдем место, куда нужно вставить 3. Это процесс продолжается на рисунке 1.8 (b) для числа 1. Наконец, на рисунке 1.8 (c) мы завершаем сортировку, поместив 2 на нужное место.

Рисунок 1.8 - Сортировка вставками

Если длина нашего массива равна n, нам нужно пройтись по n - 1 элементам. Каждый раз нам может понадобиться сдвинуть n - 1 других элементов. Вот почему этот метод требует довольно-таки много времени.

Сортировка вставками относится к числу методов сортировки по месту. Другими словами, ей не требуется вспомогательная память, мы сортируем элементы массива, используя только память, занимаемую самим массивом. Кроме того, она является устойчивой - если среди сортируемых ключей имеются одинаковые, после сортировки они остаются в исходном порядке.

Сортировка с помощью включения

Кто играл в карты, процедуру сортировки включениями осуществлял многократно. Как правило, после раздачи карт игрок, держа карты веером в руке, переставляет карты с места на место, стремясь их расположить по мастям и рангам, например, сначала все тузы, затем короли, дамы и т. д. Элементы (карты) мысленно делятся на уже «готовую последовательность» и неправильно расположенную последовательность. Теперь на каждом шаге, начиная с i = 2, из неправильно расположенной последовательности извлекается очередной элемент и перекладывается в готовую последовательность на нужное место.

for i:=2 to N do

begin

x:=a[i];

<включение х на соответствующее место готовой последовательности a[1],…, a[i]>

End

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

Исходные элементы 23 34 12 13 9

i=2 23 34 12 13 9

i=3 12 23 34 13 9

i=4 12 13 23 34 9

i=5 9 12 13 23 34

В алгоритме поиск подходящего места осуществляется как бы просеиванием x: при движении по последовательности и сравнении с очередным a[j]. Затем х либо вставляется на свободное место, либо а[j] сдвигается вправо и процесс как бы «уходит» влево.

Сортировка с помощью прямого включения

Элементы массива, начиная со второго, последовательно берутся по одному и включаются на нужное место в уже упорядоченную часть массива, расположенную слева от текущего элемента а[i]. В отличие от стандартной ситуации включения элемента в заданную позицию массива, позиция включаемого элемента при этом неизвестна. Определим её, сравнивая в цикле поочерёдно a[i] с a [i_1], а [i_2],… до тех пор, пока не будет найден первый из элементов меньший или равный а[i], либо не будет достигнут левый конец массива. Поскольку операции сравнения и перемещения чередуются друг с другом, то этот способ часто называют просеиванием или погружением. Очевидно, что программа, реализующая описанный алгоритм, должна содержать цикл в цикле.

program sortirovka_l;

(*сортировка включением по линейному поиску*)

const N=5;

type item= integer;

var a: array [0..n] of item; i, j: integer; x: item;

begin (*задание искомого массива*)

for i:=1 to N do begin write ('введите элемент a [', i, ']=');

readln (a[i])

end;

for i:=1 to N do begin write (a[i], ' ');

end;

writeln;

(*алгоритм сортировки включением*)

for i:=2 to n do

begin

x:=a[i]; j:=i; a[0]:=x; (*барьер*)

while x<a [j-l] do

begin

a[j]:=a [j_1]; j:=j_1;

end;

a[j]:=x;

{for k:=1 to n do write (a[k], ' ') end; writeln;} end;

(*вывод отсортированного массива*)

for i:=1 to N do

begin

write (a[i], ' '); end;

readln; end.

В рассмотренном примере программы для анализа процедуры пошаговой сортировки можно рекомендовать использовать трассировку каждого прохода по массиву с целью визуализации его текущего состояния. В тексте программы в блоке непосредственного алгоритма сортировки в фигурных скобках находится строка, которая при удалении скобок выполнит требуемое (параметр k необходимо описать в разделе переменных - var k:integer).

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

program sortirovka_2;

(*сортировка двоичным включением*)

const N=5;

type item= integer;

var a: array [0..n] of item; i, j, m, L, R: integer; x: item;

begin (*задание элементов массива*)

for i: - l to N do begin write ('введите элемент a [', i, ']= ');

readln (a[i]);

end;

for i:=1 to N do begin write (a[i], ' ');

end;

writeln;

(*алгоритм сортировки двоичным включением*)

for i:=2 to n do

begin

x:=a[i]; L:=l; R:^i;

while L<R do

begin

m:=(L+R) div 2; if a [m] <=x then L:=m+1 else R:=m;

end;

for j:=i downto R+l do a[j]:=a [j_1];

a[R]:=x; end;

(* вывод отсортированного массива*)

for i: - l to N do

begin write (a[i], ' ');

end;

readln;

end.

Сортировка Шелла

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n^1.25), для худшего случая оценкой является O(n^1.5). Дальнейшие ссылки см. в книге Кнута [4].

На рисунке 1.8 приведен пример сортировки вставками. Мы сначала вынимали 1, затем сдвигали 3 и 5 на одну позицию вниз, после чего вставляли 1. Таким образом, нам требовались два сдвига. В следующий раз нам требовалось два сдвига, чтобы вставить на нужное место 2. На весь процесс нам требовалось 2+2+1=5 сдвигов.

На рисунке 1.9 иллюстрируется сортировка Шелла. Мы начинаем, производя сортировку вставками с шагом 2. Сначала мы рассматриваем числа 3 и 1: извлекаем 2, сдвигаем 3 на 1 позицию с шагом 2, вставляем 2. Затем повторяем то же для чисел 5 и 2: извлекаем 2, сдвигаем вниз 5, вставляем 2 и т. д. Закончив сортировку с шагом 2, производим ее с шагом 1, т. е. выполняем обычную сортировку вставками. Всего при этом нам понадобится 1 + 1+ 1 = 3 сдвига. Таким образом, использовав вначале шаг, больший 1, мы добились меньшего числа сдвигов.

Рисунок 1.9 - Сортировка Шелла

Можно использовать самые разные схемы выбора шагов. Как правило, сначала мы сортируем массив с большим шагом, затем уменьшаем шаг и повторяем сортировку. В самом конце сортируем с шагом 1. Хотя этот метод легко объяснить, его формальный анализ довольно труден. В частности, теоретикам не удалось найти оптимальную схему выбора шагов. Кнут провел множество экспериментов и следующую формулу выбора шагов (h) для массива длины N.

Вот несколько первых значений h:

.

Чтобы отсортировать массив длиной 100, прежде всего, найдем номер s, для которого h_s 100. Согласно приведенным цифрам, s = 5. Нужное нам значение находится двумя строчками выше. Таким образом, последовательность шагов при сортировке будет такой: 13-4-1. Ну, конечно, нам не нужно хранить эту последовательность: очередное значение h находится из предыдущего.

Сортировка с помощью дерева

Улучшенный метод сортировки выбором с помощью дерева. Метод сортировки прямым выбором основан на поисках наименьшего элемента среди неготовой последовательности. Усилить метод можно запоминанием информации при сравнении пар элементов. Этого добиваются определением в каждой паре меньшего элемента за n/2 сравнений. Далее n/4 сравнений позволит выбрать меньший из пары уже выбранных меньших и т. д. Получается двоичное дерево сравнений после n_1 сравнений, у которого в корневой вершине находится наименьший элемент, а любая вершина содержит меньший элемент из двух приходящих к ней вершин. Одним из алгоритмов, использующих структуру дерева, является сортировка с помощью пирамиды (Дж. Вильямс) [3]. Пирамида определяется как последовательность ключей h_L…h_R, такая, что

h_i<=h_2i и h_i<=h_2i+l, для i=L,…, R/2.

Другими словами, пирамиду можно определить как двоичное дерево заданной высоты h, обладающее тремя свойствами:

* каждая конечная вершина имеет высоту h или h_1;

* каждая конечная вершина высоты h находится слева от любой конечной вершины высоты h_1;

* значение любой вершины больше значения любой следующей за ней вершины.

Рассмотрим пример пирамиды, составленной по массиву 27 9 14 8 5 11 7 2 3.

У пирамиды n=9 вершин, их значения можно разместить в массиве а, но таким образом, что следующие за вершиной из a[i] помещаются в a[2i] и a [2i+l]. Заметим, что а[6]=11, а[7]=7, а они следуют за элементом а[3]=14 (рисунок 1.10).

Рисунок 1.10 - Пирамида

Очевидно, что если 2i > n, тогда за вершиной a[i] не следуют другие вершины, и она является конечной вершиной пирамиды.

Процесс построения пирамиды для заданного массива можно разбить на четыре этапа:

1) меняя местами а[1] и а[n], получаем 3 9 14 8 5 11 7 2 27;

2) уменьшаем n на 1, т. е. n=n_1, что эквивалентно удалению вершины 27 из дерева;

3) преобразуем дерево в другую пирамиду перестановкой

нового корня с большей из двух новых, непосредственно следующих за ним вершин, до тех пор, пока он не станет больше, чем обе вершины, непосредственно за ним следующие;

4) повторяем шаги 1, 2, 3 до тех пор, пока не получим n=1.

Для алгоритма сортировки нужна процедура преобразования произвольного массива в пирамиду (шаг 3). В ней необходимо предусмотреть последовательный просмотр массива справа налево с проверкой одновременно двух условий: больше ли а[n], чем a[2i] и a [2i+l].

Полный текст программы приведен ниже.

program sortirovka_5;

(*улучшенная сортировка выбором - сортировка с помощью дерева*)

const N=8;

type item= integer;

var a: array [1..n] of item; k, L, R: integer; x: item;

procedure sift (L, R:integer);

var i, j: integer; x, y: item;

begin i:=L; j:=2*L; x:=a[L]; if (j<R) and (a[j]<a [j+1]) then j:=j+1;

while (j<=R) and (x<a[j]) do begin y:=a[i]; a[i]:=a[j];

a[j]:=y; a[i]:=a[j]; i:=j; j:=2*j;

if (j<R) and (a[j]<a [j+1]) then j:=j+1;

end;

end;

begin

(*задание искомого массива*)

for k:=1 to N do begin write ('Bведите элемент a [', k, ']=');

readln (a[k]);

end;

for k:=1 to N do begin write (a[k], ' ');

end;

writeln;

(*алгоритм сортировки с помощью дерева*)

(*построение пирамиды*)

L:=(n div 2) +1; R:=n; while L>1 do begin L:=L_1; SIFT (L, R);

end;

(*сортировка*)

while R>1 do begin x:=a[l]; a[l]:=a[R]; a[R]:=x; R:=R_1; SIET (1, R);

end;

(*вывод отсортированного массива*) for k:=1 to N do begin write (a[k], ' ');

end;

readln;

end.

Сортировка с помощью обменов

1_ый вариант. Соседние элементы массива сравниваются и при необходимости меняются местами до тех пор, пока массив не будет полностью упорядочен. Повторные проходы массива сдвигают каждый раз наименьший элемент оставшейся части массива к левому его концу. Метод широко известен под названием «пузырьковая сортировка» потому, что большие элементы массива, подобно пузырькам, «всплывают» на соответствующую позицию. Основной фрагмент программы содержит два вложенных цикла, причём внутренний цикл удобнее выбрать с шагом, равным -1 [8]:

for i: =2 to n do

for j:=n downto i do

if a [j_1]>a[j] then

begin {обмен}x:=a [j_1]; a [j_1]:=a[j]; a[j]:=xend;

2_ой вариант. Пузырьковая сортировка является не самой эффективной, особенно для последовательностей, у которых «всплывающие» элементы находятся в крайней правой стороне. В улучшенной (быстрой) пузырьковой сортировке предлагается производить перестановки на большие расстояния, причем двигаться с двух сторон. Идея алгоритма заключается в сравнении элементов, из которых один берется слева (i = 1), другой - справа (j = n). Если a[i] <= a[j], то устанавливают j = j - 1 и проводят следующее сравнение. Далее уменьшают j до тех пор, пока a[i] > a[j]. В противном случае меняем их местами и устанавливаем i = i + 1. Увеличение i продолжаем до тех пор, пока не получим a[i] > a[j]. После следующего обмена опять уменьшаем j. Чередуя уменьшение j и увеличение i, продолжаем этот процесс с обоих концов до тех пор, пока не станет i = j. После этого этапа возникает ситуация, когда первый элемент занимает ему предназначенное место, слева от него младшие элементы, а справа - старшие [8].

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

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

program sortirovka_6;

(*сортировка прямым обменом - пузырьковая сортировка*)

const N=5;

type item= integer;

var a: array [1..n] of item; i, j: integer; x: item;

begin (*задание искомого массива*)

for i:=1 to N do begin write ('введи элемент a [', i, ']= ');

readln (a[i]);

end;

for i:=1 to N do begin write (a[i], ' ');

end;

writeln;

(*алгоритм пузырьковой сортировки*)

for i:=2 to n do for j:=n downto i do begin

if a [j_1]>a[j] then begin x:=a [j_1]; a [j_1]:=a[j]; a[j]:=x;

end;

end;

(*вывод отсортированного массива*)

for i:=1 to N do begin write (a[i], ' ');

end;

readln;

end.

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

program sortirovka_7;

(*сортировка прямым обменом - шейкерная сортировка*)

const N=5;

type item= integer;

var a: array [1..n] of item; i, j, k, L, R: integer; x: item;

begin (*задание искомого массива*)

for i: =1 to N do begin write ('введи элемент а [', i, '] = ');

readln (a[i]);

end;

for i:=1 to N do begin write (a[i], ' ');

end;

writeln;

(*алгоритм шейкерной сортировки*)

L: =2; R:=n; k:=n;

repeat

for j:=R downto L do begin

if a [j-l]>a[j] then begin x:=a [j_1]; a [j_1]:=a[j];

a[j]:=x; k:=-j

end;

end;

L:=k+1;

for j:=L to R do begin

if a [j-l]>a[j] then begin x:=a [j-l]

a [j-l]:=a[j]; a[j]:=x; k:=j

end;

end;

R:=k_1; until L>R;

(*вывод отсортированного массива*)

for i:=l to N do

begin write (a[i], ' ');

end;

readln;

end.

Быстрая сортировка

Хотя идея Шелла значительно улучшает сортировку вставками, резервы еще остаются. Один из наиболее известных алгоритмов сортировки - быстрая сортировка, предложенная Ч. Хоаром. Метод и в самом деле очень быстр, недаром по-английски его так и величают QuickSort [6].

Этому методу требуется O (n log₂n) в среднем и O(n²) в худшем случае. К счастью, если принять адекватные предосторожности, наихудший случай крайне маловероятен. Быстрый поиск не является устойчивым. Кроме того, ему требуется стек, т. е. он не является и методом сортировки на месте.

Алгоритм разбивает сортируемый массив на разделы, затем рекурсивно сортирует каждый раздел. В функции Partition один из элементов массива выбирается в качестве центрального. Ключи, меньшие центрального, следует расположить слева от него, те, которые больше - справа.

int function Partition (Array A, int Lb, int Ub);

begin

select a pivot from A[Lb]… A[Ub];

reorder A[Lb]… A[Ub] such that:

all values to the left of the pivot are pivot

all values to the right of the pivot are pivot

return pivot position;

end;

procedure QuickSort (Array A, int Lb, int Ub);

begin

if Lb < Ub then

M = Partition (A, Lb, Ub);

QuickSort (A, Lb, M - 1);

QuickSort (A, M + 1, Ub);

end;

На рисунке 1.11 (а) в качестве центрального выбран элемент 3. Индексы начинают изменяться с концов массива. Индекс i начинается слева и используется для выбора элементов, которые больше центрального, индекс j начинается справа и используется для выбора элементов, которые меньше центрального. Эти элементы меняются местами - см. рисунок 1.11 (b). Процедура QuickSort рекурсивно сортирует два подмассива, в результате получается массив, представленный на рисунке 1.11 (c).

В процессе сортировки может потребоваться передвинуть центральный элемент. Если нам повезет, выбранный элемент окажется медианой значений массива, т. е. разделит его пополам. Предположим на минутку, что это и в самом деле так. Поскольку на каждом шаге мы делим массив пополам, а функция Partition, в конце концов, просмотрит все n элементов, время работы алгоритма есть O (n log₂n).

В качестве центрального функция Partition может попросту брать первый элемент (A[Lb]). Все остальные элементы массива мы сравниваем с центральным и передвигаем либо влево от него, либо вправо. Есть, однако, один случай, который безжалостно разрушает эту прекрасную простоту. Предположим, что наш массив с самого начала отсортирован. Функция Partition всегда будет получать в качестве центрального минимальный элемент и потому разделит массив наихудшим способом: в левом разделе окажется один элемент, соответственно, в правом останется Ub - Lb элементов.

Рисунок 1.11 - Пример работы алгоритма Quicksort

Таким образом, каждый рекурсивный вызов процедуры quicksort всего лишь уменьшит длину сортируемого массива на 1. В результате для выполнения сортировки понадобится n рекурсивных вызовов, что приводит к времени работы алгоритма порядка O(n²). Один из способов побороть эту проблему - случайно выбирать центральный элемент. Это сделает наихудший случай чрезвычайно маловероятным.

Сортировка с помощью прямого выбора

При сортировке этим методом выбирается наименьший элемент массива и меняется местами с первым. Затем выбирается наименьший среди оставшихся n - 1 элементов и меняется местами со вторым и т. д. до тех пор, пока не останется один самый больший элемент. Основной фрагмент программы может выглядеть так [11]:

for i:=l to n_1 do

begin

k: =i;

x:=a[i];

for j:=i+1 to n do

if a[j]<x then begin k:=j; x:=a[k] end;a[k]:=a[i]; a[i]: =xend;

k - величина, хранящая индекс элемента, участвующего в операции обмена.

Сортировка файлов

Главная особенность методов сортировки последовательных файлов в том, что при их обработке в каждый момент непосредственно доступна одна компонента (на которую указывает указатель). Чаще процесс сортировки протекает не в оперативной памяти, как в случае с массивами, а с элементами на внешних носителях («винчестере», дискете и т. п.).

Понять особенности сортировки последовательных файлов на внешних носителях позволит следующий пример [9].

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

program sortirovka_faila_1;

{сортировка последовательного файла}

const n=8; type item= integer;

var a: array [1..n] of item;

i, k: integer; x, y: item;

fl, f2: text; {file of item};

begin

{задание искомого массива}

for i:=1 to N do begin write ('введи элемент а ['i, '] = ');

readln (a[i]);

end;

writeln; assign (fl, 'datl.dat'); rewrite(fl);

assign (f2, 'dat2.dat'); rewrite(f2);

{формирование последовательного файла}

for i:=1 to N do begin writeln (fl, a[i]);

end;

{алгоритм сортировки с использованием вспомогательного файла}

for k:=1 to (n div 2) do

begin {извлечение из исходного файла и запись во вспомогательный}

reset(fl); readln (fl, x);

for i:=2 to n do begin readln (fl, y);

if x>y then writeln (f2, y) else begin writeln (f2, x); x:=y;

end;

end;

writeln (f2, x);

{извлечение из вспомогательного файла и запись в исходный}

rewrite(fl); reset(f2); readln (f2, x);

for i:=2 to n do begin readln (f2, y);

if x>y then writeln (fl, y) else begin writeln (fl, x); x:=y;

end;

end;

writeln (fl, x); rewrite(f2); end;

(вывод результата)

reset(fl);

for i:=1 to N do readln (fl, a[i]);

for i:=1 to N do begin write (a[i], ' ');

end;

close(fl); close(f2); readln;

end.

По сути можно в программе обойтись без массива а [1..n]. В качестве упражнения попытайтесь создать программу, в которой не используются массивы.

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

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

Если объединить эти два массива в один, разумеется, двойного размера, то программа упрощается. Пусть индексы i и j фиксируют два входных элемента с концов исходного массива, k и L - два выходных, соответствующих концам вспомогательного массива. Направлением пересылки (сменой ролей массивов) удобно управлять с помощью булевской переменной, которая меняет свое значение после каждого прохода, когда элементы a₁…, a_n движутся на место a_ni….a_2n и наоборот. Необходимо еще учесть изменяющийся на каждом проходе размер объединяемых упорядоченных групп элементов. Перед каждым последующим проходом размер удваивается. Если считать, что количество элементов в исходной последовательности не является степенью двойки (для процедуры разделения это существенно), то необходимо придумать стратегию разбиения на группы, размеры которых q и r могут не совпадать с ведущим размером очередного прохода. В окончательном виде алгоритм сортировки слиянием представлен ниже.