- •Саод, семестр 1
- •Абстрактные типы данных
- •Типы, структуры данных и атд
- •Время выполнения программы
- •Асимптотические отношения
- •Ограниченность показателя функции роста
- •Анализ программы на псевдоязыке
- •Абстрактный тип данных в списках
- •Реализация атд (Абстрактный тип данных). Линейный список
- •Сравнение последовательного и связанного распределения
- •Структуры данных на основе линейных списков Стек, очередь, дек
- •Реализация стека, дека и очереди на основе лсс (Линейного связанного списка)
- •Реализация дека
- •Не линейная структура данных атд дерево
- •Порядок узлов
- •Прямой, обратный и симметричный обход дерева
- •Помеченные деревья или деревья выражений
- •Сортировка
- •Классификация алгоритмов сортировки
- •Постановка задачи сортировки
- •Методы сортировок
- •Типы сортировок
- •Критерии оценки сортировок
- •Простые схемы сортировок
- •Простая вставка
- •Алгоритм Шелла
- •Быстрая сортировка Хоару
- •Оценка эффективности быстрой сортировки
- •Пирамидальная сортировка. Выбор из дерева
- •Сортировка подсчетом
- •Распределяющий подсчет
- •Класс сортировок слиянием
- •Естественное двухпутевое слияние – едс
- •Фиксированное двухпутевое слияние
- •Пример выполнения расчетов по практическому занятию
Простая вставка
В этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.
Пусть отсортировано начало массива A[1], A[2], ..., A[i-1], а остаток массива A[i], ...,A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый – с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной. Так как массив из одного элемента можно считать отсортированным, начнем с i=2.
Этот алгоритм также имеет максимальную и среднюю временную сложности, пропорциональные O(n2), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет временную сложность Tmin(n), пропорциональную O(n). Алгоритм сохраняет порядок элементов с одинаковыми значениями.
Алгоритм Шелла
Подобен пузырьку, в котором сравнение и обмены происходят на некоторой дистанции в зависимости от значения переменной A, называемой шагом сортировки. Метод Шелла относится к классу вставок, в котором происходит обмен записи.
Устойчивой называется сортировка, в которой записи с одинаковым значением ключа сохраняют свою относительную исходную последовательность и после сортировки.
7 5 13 6 7 10 4 7 2 (R1;R6);(R2;R7);(R3;R8)…(Ri;Ri+L)
7 4 7 2 7 10 5 13 6 (R1;R4 ;R7);(R2;R5;R8);(R3;R6;R9)
2 4 6 5 7 7 7 13 10
послед. Шаг h=1
В алгоритме Шелла неявно образуются группы из элементов, которые отстоят друг от друга на h позиций, каждая такая группа сортируется простой вставкой, после чего значение шага надо изменить.
Теорема: K-упорядоченная последовательность после h сортировки будет одновременно kh упорядочена
Самая простая последовательность шагов образуется
h={ ½; N/2 * ½; N/8; N/16; ....; 1 }, где i номер итерации
hi=(Hi-1)/2
h={16,8,4,2,1}
Что приводит к тому, что элементы в четных и нечетных позициях не взаимодействуют друг с другом , вплоть до последней итерации на которую придется максимальное количество обменов – наихудший случай выбора шагов. А наилучший – когда происходит наибольшее перемешивание групп от раза к разу.
Это достигается, если шаги взаимно простые h={13,11,7,5,3,1}. Вообще, последовательность может быть любая, главное чтоб h=1.
Например у Кнута: hi=3h-1+1
При этом I максимально i – max : Himax+2 > N
h>N
Трудоемкость Шелла О(N1,667)
Причем это достигается всего лишь при двух шагах сортировки относительно простых вставок.