Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка

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

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №2

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №3

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №4

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №5

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №6

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №7

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №8

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №9

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №10

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №11

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №12

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №13

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №14

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №15

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №16

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №17

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №18

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №19

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №20

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №21

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №22

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №23

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №24

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №25

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №26

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №27

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №28

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №29

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №30

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №31

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №32

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №33

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №34

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №35

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №36

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №37

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №38

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №39

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №40

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №41

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №42

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №43

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №44

Содержание ▲

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

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

Слайд 1

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

Элементарные сортировки

Слайд 2

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

Пример: 2-Sum Подсчет количества инструкций, как функции от N.

Слайд 3

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

Проблема сортировки Пример. Список студентов

Слайд 4

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

Пример сортировки Цель. Отсортировать любые типы данных Пример. Отсортировать случайные вещественные числа в порядке возрастания

Слайд 5

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

Пример сортировки Цель. Отсортировать любые типы данных Пример. Отсортировать строки из файла в алфавитном порядке

Слайд 6

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

Пример сортировки Цель. Отсортировать любые типы данных Пример. Сортировка файлов в директории по имени

Слайд 7

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

Сортировка выбором

Слайд 8

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

Сортировка выбором На итерации i найти минимальный оставшийся элемент с индексом min Поменять местами a[i] и a[min] Видео 1

Слайд 9

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

Сортировка выбором Алгоритм. Сканирование идет слева направо Элементы слева от стрелки отсортированы и не меняются Нет элемента справа от стрелки, который был бы меньше элемента слева от стрелки

Слайд 10

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

Сортировка выбором: внутренний цикл

Слайд 11

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

Сортировка выбором: реализация на Java

Слайд 12

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

Сортировка выбором: математический анализ Утверждение. Сортировка выбором использует (N-1) + (N-2) + … + 1 + 0 ~ N2/2 сравнений и N перестановок

Слайд 13

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

Видео 2 Видео 2

Слайд 14

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

Сортировка вставками

Слайд 15

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

Сортировка вставками На итерации i поменять a[i] с каждым большим элементом слева Видео 3

Слайд 16

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

Сортировка вставками Алгоритм. Сканирование идет слева направо Элементы слева от стрелки отсортированы по возрастанию Элементы справа от стрелки еще не проверены

Слайд 17

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

Сортировка вставками: внутренний цикл

Слайд 18

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

Сортировка вставками: реализация на Java

Слайд 19

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

Сортировка вставками: математический анализ Утверждение. Сортировка вставками использует ~ N2/4 сравнений и ~ N2/4 перестановок при случайном наборе данных В среднем каждый ключ проходит половину пути

Слайд 20

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

Сортировка вставками: пример

Слайд 21

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

Видео 4 Видео 4

Слайд 22

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

Сортировка вставками: лучший и худший случай Лучший случай. Массив отсортирован; необходимо N-1 сравнений и 0 перестановок A E E L M O P R S T X Худший случай. Массив отсортирован в обратно порядке и нет дубликатов; ~ N2/2 сравнений и ~ N2/2 вставок X T S R P O M L E E A

Слайд 23

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

Видео 5 Видео 5

Слайд 24

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

Сортировка вставками: частично упорядоченный массив Инверсия — пара элементов, которая нарушает упорядоченность в массиве

Слайд 25

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

Видео 6 Видео 6

Слайд 26

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

Сортировка Шелла

Слайд 27

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

Сортировка Шелла: обзор Идея. Переупорядочить массив так, чтобы каждые h-е элементы (начиная с любого места в массиве) составляли упорядоченную последовательность

Слайд 28

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

h-sorting Сортировка вставками через шаг h

Слайд 29

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

Слайд 30

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

Сортировка Шелла Утверждение. g-отсортированный массив остается g-отсортированным даже после h-сортировки

Слайд 31

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

Слайд 32

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

Сортировка Шелла: реализация на Java

Слайд 33

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

Слайд 34

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

Видео 7 Видео 7

Слайд 35

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

Сортировка Шелла: анализ Утверждение. В худшем случае количество сравнений при последовательности 3x + 1 равно O(N3/2)

Слайд 36

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

Чем интересна Сортировка Шелла? Простая идея дает хорошую производительность На практике Работает быстро на небольших массивах (bzip2/linux kernel) Проста в реализации и используется во встраиваемых системах Есть аппаратные реализации Простой алгоритм, нетривиальная производительность Асимптотический порядок роста? Лучшая последовательность? Производительность в среднем случае? Некоторые замечательные алгоритмы ждут исследования