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

На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка абсолютно бесплатно. Урок-презентация на эту тему содержит всего 44 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.

Презентации » Устройства и комплектующие » Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка

Просмотр ВСЕЙ презентации! ЖМИТЕ

Оцените презентацию от 1 до 5 баллов!

Смотреть онлайн
Скачать

Тип файла:

ppt / pptx (powerpoint)
Всего слайдов:

44 слайда
Для класса:

1,2,3,4,5,6,7,8,9,10,11
Размер файла:

3.07 MB
Просмотров:

53
Скачиваний:

0
Автор:

неизвестен

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

№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) Проста в реализации и используется во встраиваемых системах Есть аппаратные реализации Простой алгоритм, нетривиальная производительность Асимптотический порядок роста? Лучшая последовательность? Производительность в среднем случае? Некоторые замечательные алгоритмы ждут исследования

№37 слайд