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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №1Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка, слайд №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.
Описание слайда:
Пример: 2-Sum Подсчет количества инструкций, как функции от N.

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


Сортировка выбором
Описание слайда:
Сортировка выбором

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


Сортировка выбором: реализация на Java
Описание слайда:
Сортировка выбором: реализация на Java

Слайд 12


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

Слайд 13


Видео 2 Видео 2
Описание слайда:
Видео 2 Видео 2

Слайд 14


Сортировка вставками
Описание слайда:
Сортировка вставками

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


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

Слайд 20


Сортировка вставками: пример
Описание слайда:
Сортировка вставками: пример

Слайд 21


Видео 4 Видео 4
Описание слайда:
Видео 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
Описание слайда:
Сортировка вставками: лучший и худший случай Лучший случай. Массив отсортирован; необходимо 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
Описание слайда:
Видео 5 Видео 5

Слайд 24


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

Слайд 25


Видео 6 Видео 6
Описание слайда:
Видео 6 Видео 6

Слайд 26


Сортировка Шелла
Описание слайда:
Сортировка Шелла

Слайд 27


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

Слайд 28


h-sorting Сортировка вставками через шаг h
Описание слайда:
h-sorting Сортировка вставками через шаг h

Слайд 29


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

Слайд 30


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

Слайд 31


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

Слайд 32


Сортировка Шелла: реализация на Java
Описание слайда:
Сортировка Шелла: реализация на Java

Слайд 33


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

Слайд 34


Видео 7 Видео 7
Описание слайда:
Видео 7 Видео 7

Слайд 35


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

Слайд 36


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

Слайд 37


Перетасовка
Описание слайда:
Перетасовка

Слайд 38


Как перетасовать элементы в массиве? Цель. Переставить элементы в массиве так, чтобы они имели равномерное распределение
Описание слайда:
Как перетасовать элементы в массиве? Цель. Переставить элементы в массиве так, чтобы они имели равномерное распределение

Слайд 39


Сортировка Шелла Сгенерировать вещественные числа для каждого элемента Отсортировать массив
Описание слайда:
Сортировка Шелла Сгенерировать вещественные числа для каждого элемента Отсортировать массив

Слайд 40


Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i] и a[r] Видео 8
Описание слайда:
Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i] и a[r] Видео 8

Слайд 41


Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i] и a[r]
Описание слайда:
Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i] и a[r]

Слайд 42


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

Слайд 43


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

Слайд 44


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию