Теория алгоритмов. Сортировка массива. (Лекция 17) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №1

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №2

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №3

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №4

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №5

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №6

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №7

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №8

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №9

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №10

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №11

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №12

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №13

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №14

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №15

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №16

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №17

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №18

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №19

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №20

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №21

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №22

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №23

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №24

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №25

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №26

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №27

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №28

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №29

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №30

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №31

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №32

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №33

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №34

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №35

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №36

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №37

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №38

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №39

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №40

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №41

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №42

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №43

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №44

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №45

Теория алгоритмов. Сортировка массива. (Лекция 17), слайд №46

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория алгоритмов. Сортировка массива. (Лекция 17). Доклад-сообщение содержит 46 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 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

Слайд 44

Описание слайда:

Улучшения алгоритма Первый элемент в сортируемом куске выбирается случайно и запоминается Участки, меньшие определенного размера, сортируются простыми способами Иногда исключение рекурсивных вызовов приводит к повышению эффективности

Слайд 45

Описание слайда:

Быстрая сортировка Анализ алгоритма Эффективность во многом зависит от сбалансированности разбиения на подмассивы Наихудшее разбиение: 1 к (N–1) => O(N2) Лучшее разбиение: N/2 к N/2 => O(N log N) Средний случай: O(N log N)

Слайд 46

Описание слайда:

Вопросы? Сортировка: общие замечания Задача сортировки Внутренняя и внешняя сортировка Устойчивость Сортировка массива Сортировка прямыми вставками Идея Псевдокод Анализ алгоритма Сортировка бинарными вставками Сортировка прямым выбором Идея алгоритма Временная сложность алгоритма Сортировка прямыми обменами Идея алгоритма Временная сложность алгоритма Улучшения алгоритма Шейкерная сортировка Сортировка Шелла Идея алгоритма Временная сложность алгоритма Сортировка слияниями Идея алгоритма Временная сложность алгоритма Быстрая сортировка Идея алгоритма Временная сложность алгоритма