- •Структуры и алгоритмы
- •ВвЕдение
- •Необходимые понятия и определения
- •Основные структуры данных
- •Задача сортировки массивов
- •Трудоемкость методов сортировки массивов
- •Задача сортировки последовательностей
- •Теорема о сложности сортировки
- •Задача поиска элементов с заданным ключом
- •Контрольные вопросы
- •Методы сортировки с квадратичной трудоемкостью
- •Метод прямого выбора
- •Алгоритм на псевдокоде
- •Пузырьковая сортировка
- •Алгоритм на псевдокоде
- •Шейкерная сортировка
- •Алгоритм на псевдокоде
- •Контрольные вопросы
- •Метод Шелла
- •Метод прямого включения
- •Алгоритм на псевдокоде
- •Метод Шелла
- •Алгоритм на псевдокоде
- •Контрольные вопросы
- •Быстрые методы сортировки массивов
- •Пирамидальная сортировка
- •Свойства пирамиды
- •Алгоритм на псевдокоде
- •Построение (1, 8)-пирамиды
- •Сортировка
- •Алгоритм на псевдокоде
- •Метод Хоара
- •Алгоритм на псевдокоде
- •Проблема глубины рекурсии.
- •Алгоритм на псевдокоде
- •Контрольные вопросы
- •Работа с линейными списками
- •Указатели. Основные операции с указателями
- •Основные операции с линейными списками
- •Методы сортировки последовательностей
- •Метод прямого слияния
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Цифровая сортировка
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Контрольные вопросы
- •Двоичный поиск в упорядоченном массиве
- •Алгоритм двоичного поиска
- •Алгоритм на псевдокоде
- •Обозначим
- •Найден – логическая переменная, в которой будем отмечать факт успешного завершения поиска.
- •Алгоритм на псевдокоде
- •Контрольные вопросы
- •Сортировка данных с произвольной структурой
- •Сравнение данных произвольной структуры
- •Сортировка по множеству ключей. Индексация
- •Алгоритм на псевдокоде (на примере пузырьковой сортировки)
- •Индексация через массив указателей
- •Контрольные вопросы
- •Хэширование и поиск
- •Понятие хэш-функции
- •Алгоритм на псевдокоде
- •Метод прямого связывания
- •Метод открытой адресации
- •Алгоритм на псевдокоде
- •Контрольные вопросы
- •Правила выполнения лабораторных работ
- •Лабораторная работа 1
- •Лабораторная работа 2
- •Лабораторная работа 3
- •Лабораторная работа 4
- •Лабораторная работа 5
- •Лабораторная работа 6
- •Контрольная работа правила выполнения и оформления Контрольной работы
- •Правила выбора варианта Задания для контрольной работы одинаковы для всех студентов. Начальные данные выбираются индивидуально в зависимости от задания в контрольной работе.
- •Вопросы к зачету правила выставления зачета
- •Рекомендуемая литература
- •Псевдокод для записи алгоритмов
Задача сортировки последовательностей
Пусть дана последовательность S=S1S2 …Sn , т.е. совокупность данных с последовательным доступом к элементам. Примерами такой последовательности могут служить файл на магнитной ленте, линейный список:
Необходимо переставить элементы последовательности так, чтобы выполнялись неравенства:S1≤ S2 ≤ … ≤ Sn Последовательный доступ означает, что любой элемент списка может быть получен только путём просмотра предыдущих элементов, причём просмотр возможен только в одном направлении. Это является существенным ограничением по сравнению с массивом, где можно было обратиться к любому элементу массиву, используя индекс. Поэтому методы сортировки, разработанные специально для массивов, не годятся для последовательностей, в то время как методы сортировки последовательностей используются и для сортировки массивов. Трудоемкость методов сортировки последовательностей измеряется количеством операций, затрачиваемых на сортировку. Характерными операциями при сортировке последовательностей являются операция сравнения элементов и операция пересылки элемента одной последовательности в другую. Как и прежде будем обозначать количества операций сравнения и пересылки С и М соответственно.
Теорема о сложности сортировки
При изучении различных методов сортировок возникает закономерный вопрос о построении метода сортировки с минимально возможной трудоемкостью. Следующая теорема устанавливает нижнюю границу трудоемкости для сортировки массива из n элементов.
Теорема. Если все перестановки из n элементов равновероятны, то любое дерево решений, сортирующее последовательность из n элементов имеет среднюю высоту не менее log(n!).
Приведем нестрогое доказательство. Рассмотрим дерево решений для трех элементов a, b, c.
Рисунок 1 Дерево решений для 6 элементов
Все возможные перестановки – это листья дерева (6 вариантов). Чтобы получить конкретную перестановку нужно сделать два или три сравнения. Оценим среднее количество сравнений, необходимых для упорядочивания массива или среднюю длину пути от корня дерева до листьев. Для этого посчитаем сумму длин всевозможных путей от корня до листьев (длина внешнего пути двоичного дерева) и поделим ее на количество листьев Сср= (2+3+3+3+3+2)/6=2,6.
Из теории графов известно, что длина внешнего пути двоичного дерева с m листьями D(m)≥m log m. Поскольку в общем случае на дереве имеется n! листьев. Тогда Сср≥n! log(n!)/n!=lоg n! > n log n–n log e. Последнее неравенство является известной нижней оценкой для значения факториала. Таким образом, не существует алгоритма сортировки n элементов, использующего в среднем меньше чем (n log n – log e) операций сравнения. Класс сложности n log n является предельно достижимым для алгоритмов сортировки с использованием операций сравнения. Что касается количества пересылок, то если мы определим требуемую перестановку, и имеем память для второй копии массива, то достаточно сделать n пересылок. На сегодняшний день алгоритм, требующий nlogn сравнений и n пересылок, неизвестен.