- •Оглавление
- •Список рисунков
- •ВвЕдение
- •Необходимые понятия и определения
- •Основные структуры данных
- •Задача сортировки массивов
- •Трудоемкость методов сортировки массивов
- •Задача сортировки последовательностей
- •Теорема о сложности сортировки
- •Задача поиска элементов с заданным ключом
- •Методы сортировки с квадратичной трудоемкостью
- •Метод прямого выбора
- •Алгоритм на псевдокоде
- •Пузырьковая сортировка
- •Алгоритм на псевдокоде
- •Шейкерная сортировка
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Метод Шелла
- •Метод прямого включения
- •Алгоритм на псевдокоде
- •Метод Шелла
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Быстрые методы сортировки массивов
- •Пирамидальная сортировка
- •Свойства пирамиды
- •Алгоритм на псевдокоде
- •Построение (1, 8)-пирамиды
- •Сортировка
- •Алгоритм на псевдокоде
- •Метод Хоара
- •Алгоритм на псевдокоде
- •Проблема глубины рекурсии.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Работа с линейными списками
- •Указатели. Основные операции с указателями
- •Основные операции с линейными списками
- •Методы сортировки последовательностей
- •Метод прямого слияния
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Цифровая сортировка
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Двоичный поиск в упорядоченном массиве
- •Алгоритм двоичного поиска
- •Алгоритм на псевдокоде
- •Обозначим
- •Найден – логическая переменная, в которой будем отмечать факт успешного завершения поиска.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сортировка данных с произвольной структурой
- •Сравнение данных произвольной структуры
- •Сортировка по множеству ключей. Индексация
- •Алгоритм на псевдокоде (на примере пузырьковой сортировки)
- •Индексация через массив указателей
- •Варианты заданий
- •Двоичные деревья
- •Основные определения и понятия
- •Различные обходы двоичных деревьев
- •Варианты заданий
- •Деревья поиска
- •Поиск в дереве
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Идеально сбалансированное дерево поиска
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Случайное дерево поиска
- •Определение случайного дерева поиска
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сбалансированные по высоте деревья (авл-деревья)
- •Определение и свойства авл-дерева
- •Повороты при балансировке
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Определение б-дерева порядка m
- •Поиск в б-дереве
- •Алгоритм на псевдокоде
- •Построение б-дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Определение двоичного б-дерева
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Деревья оптимального поиска (доп)
- •Определение дерева оптимального поиска
- •Точный алгоритм построения доп
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Хэширование и поиск
- •Понятие хэш-функции
- •Алгоритм на псевдокоде
- •Метод прямого связывания
- •Метод открытой адресации
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Элементы теории кодирования информации
- •Необходимые понятия
- •Кодирование целых чисел
- •Алфавитное кодирование
- •Оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Почти оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Рекомендуемая литература
- •Псевдокод для записи алгоритмов
- •Структуры и алгоритмы обработки данных
- •630102, Г. Новосибирск, ул. Кирова, 86.
Алгоритм на псевдокоде
Сортировка методом Шелла
DO (k=hm, hm-1, … 1)
DO (i=k+1, k+2, … n)
t: = ai, j: =i-k
DO (j>0 и t < aj)
aj+k: = aj
j: = j-k
OD
aj+k: = t
OD
OD
Эффективность метода зависит от выбора значений шагов. Последовательность значений шагов, которая дает наилучшую трудоемкость, пока неизвестна, метод продолжает исследоваться, но существует и часто используется следующая последовательность шагов, предложенная Кнутом.
h1=1, hi=2hi-1+1, i=2,… m, m=
При такой последовательности шагов средний порядок трудоёмкости O(n1.2), n → ∞. Таким образом, метод Шелла существенно быстрее методов с квадратичной трудоемкостью. Метод Шелла не устойчив.
Варианты заданий
Разработать процедуру сортировки массива целых чисел методом прямого включения (язык программирования Паскаль или Си). Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве. Предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.
Разработать процедуру сортировки массива целых чисел методом Шелла (язык программирования Паскаль или Си). Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве. Предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.
Сравнить метод прямого включения и метод Шелла по количеству сравнений и пересылок для различных типов массивов. Разработать процедуру построения графика зависимости величин М и С от размера массива.
Сравнить метод прямого включения и метод Шелла с ранее расмотренными методами сортировки по количеству сравнений и пересылок для различных типов массивов. Разработать процедуру построения графика зависимости величин М и С от размера массива
Экспериментально определить подходящую последовательность шагов для метода Шелла.
Опытным путем определить константы в выражениях оценки для количества сравнений и пересылок в методе Шелла.
Быстрые методы сортировки массивов
Пирамидальная сортировка
Пирамидальная сортировка основана на алгоритме построения пирамиды. Последовательность ai, ai+1,…,ak называется (i,k)-пирамидой, если неравенство
aj≤min(a2j, а2j+1) (*)
выполняется для каждого j, j=i,…,k для которого хотя бы один из элементов a2j, a2j+1 существует.
Например, массив А является пирамидой, а массив В не является.
А=(а2 , а3 , а4 , а5 , а6 а7 , а8 )=(3, 2, 6, 4, 5, 7)
В=(b1, b2, b3, b4, b5, b6, b7)=(3, 2, 6, 4, 5, 7)
Свойства пирамиды
Если последовательность ai, ai+1,…,аk-1, ak является (i, k)-пирамидой, то последовательность ai+1,…,ak-1, полученная усечением элементов с обоих концов последовательности, является (i+1, k-1)пирамидой.
Если последовательность a1…an – (1, n)-пирамида, то а1 – минимальный элемент последовательности.
Если a1, a2…,an/2,an/2+1,…an-произвольная последовательность, то последовательность an/2+1,…,an является (n/2+1, n)-пирамидой.
Процесс построения пирамиды выглядит следующим образом. Дана последовательность as+1,…,ak, которая является (s+1, k)-пирамидой. Добавим новый элемент х и поставим его на s-тую позицию в последовательности, т.е. пирамида всегда будет расширяться влево. Если выполняется (*), то полученная последовательность – (s, k)-пирамида. Иначе найдутся элементы a2s+1,a2s такие, что либо a2s < as либо a2s+1 < as.
Пусть имеет место первый случай, второй случай рассматривается аналогично. Поменяем местами элементы as и a2s. В результате получим новую последовательность as’,as+1,…, a2s’,…, ak. Повторяем все действия для элемента a2s’ и т.д. пока не получим (s, k)-пирамиду.
П ример. Добавим в (2, 8)-пирамиду новый элемент х=6.
Условные обозначения: Х новый элемент
Х сравнение с включаемым элементом
обмен элементов
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
3 |
2 |
6 |
3 |
4 |
5 |
7 |
пирамида |
6 |
3 |
2 |
6 |
3 |
4 |
5 |
7 |
|
|
|
|
|
|
|
|
|
|
2 |
3 |
6 |
6 |
3 |
4 |
5 |
7 |
|
|
|
|
|
|
|
|
|
|
2 |
3 |
4 |
6 |
3 |
6 |
5 |
7 |
пирамида |
Рисунок 7 Добавление в пирамиду нового элемента