Презентация Теория алгоритмов. Сортировка массива. (Лекция 17) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Теория алгоритмов. Сортировка массива. (Лекция 17) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 46 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:46 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.07 MB
- Просмотров:135
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Сортировка
Алтайский государственный университет
Факультет математики и ИТ
Кафедра информатики
Барнаул 2016
№2 слайд
Содержание слайда: План
Сортировка: общие замечания
Задача сортировки
Внутренняя и внешняя сортировка
Устойчивость
Сортировка массива
Сортировка прямыми вставками
Идея
Псевдокод
Анализ алгоритма
Сортировка бинарными вставками
Сортировка прямым выбором
Идея алгоритма
Временная сложность алгоритма
Сортировка прямыми обменами
Идея алгоритма
Временная сложность алгоритма
Улучшения алгоритма
Шейкерная сортировка
№3 слайд
Содержание слайда: Сортировка:
общие замечания
Задача сортировки
Внутренняя и внешняя сортировка
Устойчивость
Сортировка массива
№4 слайд
Содержание слайда: Сортировка
Сортировка – процесс перестановки объектов заданной совокупности в определенном порядке (возрастающем или убывающем)
Целью сортировки обычно является облегчение последующего поиска элементов в отсортированном множестве
В зависимости от объема и структуры данных методы сортировки подразделяются на:
Внутренние – сортировка массивов
Внешние – сортировка файлов
№5 слайд
Содержание слайда: Сортировка: более формально
Дано: N объектов a1, a2, …, aN
Требуется: упорядочить заданные объекты, т.е. переставить их в такой последовательности ap1, ap2, …, apN, чтобы их ключи расположились в неубывающем порядке kp1 ≤ kp2 ≤ … ≤ kpN
Ключ ki = f(ai) – некоторая функция элемента
ai – целое число => ki = ai
ai – структура => ki = ai.key
№6 слайд
Содержание слайда: Сортировка: устойчивость
При устойчивой сортировке относительный порядок элементов с одинаковыми ключами не меняется
Если kpi ≤ kpj и i < j, то pi < pj
Устойчивость желательна, если элементы уже упорядочены
№7 слайд
Содержание слайда: Сортировка массивов
Массив – одна из наиболее распространенных совокупностей, подвергаемых сортировке
От алгоритмов сортировки массива требуется
экономичность по памяти
Перестановки, упорядочивающие массив, должны выполняться на том же месте
экономичность по времени
Мера эффективности C – количество сравнений ключей и M – число перестановок элементов
№8 слайд
Содержание слайда: Сортировка массивов: алгоритмы
Простые методы сортировки – прямые, временная сложность – O(n2)
сортировка прямыми вставками (by insertion)
сортировка прямым выбором (by selection)
сортировка прямыми обменами выбором (by exchange)
«Улучшенные» методы сортировки,
временная сложность – O(n log n)
быстрая сортировка Хоара (quicksort)
сортировка слияниями (mergesort)
coртировка Шелла (shellsort)
…
№9 слайд
Содержание слайда: Сортировка
прямыми выставками
Идея
Псевдокод
Анализ алгоритма
Сортировка бинарными вставками
№10 слайд
Содержание слайда: Сортировка вставками
№11 слайд
Содержание слайда: Сортировка простыми вставками
Массив делится на две части
«готовую» a1, a2, …, ai-1
исходную ai, ai+1, …, aN
Для каждого i от 2 до N
из исходной части извлекается i-й элемент
вставляется в готовую часть на нужное место
№12 слайд
Содержание слайда: Сортировка простыми вставками
№13 слайд
Содержание слайда: Сортировка простыми вставками
Анализ алгоритма
Лучший случай: массив упорядочен
Худший случай: массив упорядочен в обратном порядке
Сmin = N – 1 Mmin = 3(N-1)
Cavg = (N2 + N – 2)/4 Mavg = (N2 + 9N – 10)/4
Cmax = (N2 + N – 4)/2 Mmax = (N2 + 3N – 4)/2
Итог: T(N) = C(N) + M(N) = O(N2)
№14 слайд
Содержание слайда: Сортировка бинарными вставками
Сортировка простыми вставками может быть улучшена
Можно ускорить поиск подходящего места в «готовой» части, т.к. она упорядочена
В упорядоченной последовательности применим бинарный поиск!
Сложность бинарного поиска в худшем случае
есть O(log N)
Количество сравнений есть O(N log N)
Но по-прежнему, M(N) = O(N2)
Итог: T(N) = O(N log N) +O(N2) = O(N2)
№15 слайд
Содержание слайда: Сортировка
прямым выбором
Идея
Псевдокод
Анализ алгоритма
№16 слайд
Содержание слайда: Сортировка простым выбором
Массив делится на две части
«готовую» a1, a2, …, ai-1
исходную ai, ai+1, …, aN
Для каждого i от 1 до N–1
присвоить k индекс минимального элемента в исходной части
поменять местами элементы ai и ak
№17 слайд
Содержание слайда: Сортировка простым выбором
SELECTIONSORT(A)
1 for i 1 to length[A] – 1 do
2 k i
3 x A[i]
4 for j 1 to length[A] – 1 do
5 if A[j] < x then
6 k j
7 x A[j]
8 A[k] A[i]
9 A[i] x
№18 слайд
Содержание слайда: Сортировка простым выбором
Анализ алгоритма
Количество сравнений не зависит от начального порядка элементов:
Лучший случай: массив упорядочен
Худший случай: массив упорядочен в обратном порядке
С = (N2 – N)/2 Mmin = 3(N – 1)
Mavg N(ln N + ), = 0.577216…
Mmax = N2/4 + 3(N – 1)
Итог (худший случай) : T(N) = C(N) + M(N) = O(N2)
В среднем сортировка выбором выгоднее сортировки вставками
№19 слайд
Содержание слайда: Сортировка
прямыми обменами
Идея
Псевдокод
Анализ алгоритма
№20 слайд
Содержание слайда: Сортировка простыми обменами
(пузырьковая сортировка)
Идея: пузырек воздуха в стакане воды поднимается со дна вверх – самый маленький («легкий») элемент массива перемещается вверх («всплывает»)
Для каждого i от 2 до N
Для каждого j от N до i
Если в паре элементов aj –1 и aj нарушен порядок,
то поменять местами aj –1 и aj
№21 слайд
Содержание слайда: Сортировка простыми обменами
(пузырьковая сортировка)
№22 слайд
Содержание слайда: Си-программа
№23 слайд
Содержание слайда: Улучшенный метод «пузырька»
Если при выполнении очередного прохода не было обменов, то массив уже отсортирован и остальные проходы не нужны
Реализуется через переменную-флаг, показывающую, были ли обмены
Если флаг поднят, то обмены были и нужен еще один проход
Если флаг опущен, то – выход
№24 слайд
Содержание слайда: Улучшенный метод «пузырька»
№25 слайд
Содержание слайда: Шейкерная сортировка
Метод пузырька несимметричен
При нарушении почти полного порядка «легкими» элементами, требуется мало проходов
При нарушении почти полного порядка «тяжелыми» элементами, требуется много проходов
Выход: чередовать направления проходов
№26 слайд
Содержание слайда: Шейкерная сортировка
№27 слайд
Содержание слайда: Сортировка простыми обменами
Анализ алгоритма
Лучший случай: массив упорядочен
Худший случай: массив упорядочен в обратном порядке
Сmin = (N2 – N)/2 Mmin = 0
Cavg = (N2 – N)/2 Mavg = (N2 – N)/4
Cmax = (N2 – N)/2 Mmax = (N2 – N)/2
Итог: T(N) = C(N) + M(N) = O(N2)
№28 слайд
Содержание слайда: «Шейкерная» сортировка
Анализ алгоритма
Лучший случай: массив упорядочен
Худший случай: массив упорядочен в обратном порядке
Сmin = N – 1 Mmin = 0
Cavg = (N2 – N(k+ln N))/2 Mavg = (N2 – N)/4
Cmax = (N2 – N)/2 Mmax = (N2 – N)/2
Итог: T(N) = C(N) + M(N) = O(N2)
№29 слайд
Содержание слайда: Прямые методы сортировки
Сортировка обменами несколько менее эффективна сортировок вставками и выбором
Шейкерная сортировка выгодна, когда массив почти упорядочен
Общее свойство: перемещение элементов ровно на одну позицию за один прием
Можно показать, что среднее расстояние, на которое должен сдвигаться элемент равно N/3
Надо стремиться к дальним пересылкам элементов
№30 слайд
Содержание слайда: Сортировка Шелла
Идея алгоритма
Анализ алгоритма
№31 слайд
Содержание слайда: Сортировка Шелла
(Д.Л.Шелл, 1959)
Элементы разбиваются на подмножества для некоторого h>1
a1, a1+h, a1+2h, a1+3h,…
a2, a2+h, a2+2h, a2+3h,…
…
at, at+h, at+2h, at+3h,…
Сортировка проводится методом вставок для каждого подмножества
h уменьшается и процедура повторяется, пока h>0
№32 слайд
Содержание слайда: Сортировка Шелла
№33 слайд
Содержание слайда: Сортировка Шелла
Анализ алгоритма
Анализ приводит к сложным математическим задачам
Для эффективной сортировки соседние значения не должны быть кратными
Иначе массив распадается на непересекающиеся цепочки
Требуется, чтобы цепочки взаимодействовали как можно чаще
Д. Кнут предлагает выбирать h так (порядок обратный):
1, 4, 13, 40, 121, …, т.е. hk–1 = 3hk+1, ht=1, t = [log3N] – 1
1, 3, 7, 15, 31, …, т.е. hk–1 = 2hk+1, ht=1, t = [log2N] – 1
№34 слайд
Содержание слайда: Сортировка слиянием
Идея алгоритма
Временная сложность алгоритма
№35 слайд
Содержание слайда: Cлияние упорядоченных массивов
№36 слайд
Содержание слайда: Сортировка слиянием (фон Неймана)
№37 слайд
Содержание слайда: Алгоритм сортировки слиянием
(фон Неймана)
Псевдокод
№38 слайд
Содержание слайда: Алгоритм сортировки слиянием
(фон Неймана)
№39 слайд
Содержание слайда: Сортировка слиянием
Анализ алгоритма
Анализ приводит к сложным математическим задачам
Асимптотическая сложность – O(N log N)
№40 слайд
Содержание слайда: Быстрая сортировка
Идея алгоритма
Временная сложность алгоритма
№41 слайд
Содержание слайда: Быстрая сортировка (Хоара)
№42 слайд
Содержание слайда: Быстрая сортировка
Псевдокод
№43 слайд
Содержание слайда: Пример программы
int a[100];
void quickSort(int l, int r)
{
int x = a[l + (r - l) / 2];
//запись эквивалентна (l+r)/2,
//но не вызввает переполнения на больших данных
int i = l;
int j = r;
//код в while обычно выносят в процедуру particle
while(i <= j)
{
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i <= j)
{
swap(a[i], a[j]);
i++;
j--;
}
}
if (i<r)
quickSort(i, r);
if (l<j)
quickSort(l, j);
}
№44 слайд
Содержание слайда: Улучшения алгоритма
Первый элемент в сортируемом куске выбирается случайно и запоминается
Участки, меньшие определенного размера, сортируются простыми способами
Иногда исключение рекурсивных вызовов приводит к повышению эффективности
№45 слайд
Содержание слайда: Быстрая сортировка
Анализ алгоритма
Эффективность во многом зависит от сбалансированности разбиения на подмассивы
Наихудшее разбиение: 1 к (N–1) => O(N2)
Лучшее разбиение: N/2 к N/2 => O(N log N)
Средний случай: O(N log N)
№46 слайд
Содержание слайда: Вопросы?
Сортировка: общие замечания
Задача сортировки
Внутренняя и внешняя сортировка
Устойчивость
Сортировка массива
Сортировка прямыми вставками
Идея
Псевдокод
Анализ алгоритма
Сортировка бинарными вставками
Сортировка прямым выбором
Идея алгоритма
Временная сложность алгоритма
Сортировка прямыми обменами
Идея алгоритма
Временная сложность алгоритма
Улучшения алгоритма
Шейкерная сортировка
Сортировка Шелла
Идея алгоритма
Временная сложность алгоритма
Сортировка слияниями
Идея алгоритма
Временная сложность алгоритма
Быстрая сортировка
Идея алгоритма
Временная сложность алгоритма
Скачать все slide презентации Теория алгоритмов. Сортировка массива. (Лекция 17) одним архивом:
