Презентация Перетасовка Кнута. Быстрая сортировка (Quicksort) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Перетасовка Кнута. Быстрая сортировка (Quicksort) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 17 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:17 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.77 MB
- Просмотров:58
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Перетасовка Кнута
На итерации i выбрать r между 0 и i при нормальном распределении
Поменять a[i] и a[r]
№2 слайд
Содержание слайда:
№3 слайд
Содержание слайда:
№4 слайд
Содержание слайда:
№5 слайд
Содержание слайда: Быстрая сортировка
(Quicksort)
№6 слайд
Содержание слайда: Два классических алгоритма сортировки
Критические компоненты в мировой вычислительной инфраструктуре
Понимание научных основ этих алгоритмов даст нам возможность разрабатывать прикладные системы для решения реальных задач
Быстрая сортировка входит в десятку самых полезных алгоритмов, разработанных в 20-м веке
№7 слайд
Содержание слайда:
№8 слайд
Содержание слайда: Быстрая сортировка
Основной план
Перемешать элементы случайным образом
Разбиение для элемента j
a[j] оставить на месте
Нет элементов меньше чем a[j] с правой стороны
Нет элементов больше чем a[j] с левой стороны
Отсортировать каждую часть рекурсивно
№9 слайд
Содержание слайда: Быстрая сортировка
Повторять до тех пор, пока i и j не пересекутся
Проверять i-ые элементы до тех пор пока a[i] < a[lo]
Проверять j-ые элементы до тех пор пока a[j] > a[lo]
Поменять местами a[i] и a[j]
Видео 1
№10 слайд
Содержание слайда: Быстрая сортировка: реализация разбиения на Java
№11 слайд
Содержание слайда: Быстрая сортировка: реализация на Java
№12 слайд
Содержание слайда: Быстрая сортировка
№13 слайд
Содержание слайда: Быстрая сортировка
№14 слайд
Содержание слайда: Быстрая сортировка: реализация
Не требует дополнительной памяти
Выход из циклов. Обращайте особое внимание на условия выхода из циклов
Ограничения. Проверка j == lo излишняя, но i == hi нет
Рандомизация. Перетасовка нужна чтобы обеспечить гарантии производительности
Равные ключи. Если присутствуют дубликаты, то можно использовать другой вариант алгоритма
№15 слайд
Содержание слайда: Быстрая сортировка: лучший случай
Лучший случай. Количество сравнений ~ N log2N
№16 слайд
Содержание слайда: Быстрая сортировка: худший случай
Худший случай. Количество сравнений ~ ½ N2
№17 слайд
Содержание слайда: Быстрая сортировка: свойства
Худший случай. Квадратичное количество сравнений
N + (N-1) + (N-2) + … + 1 ~ ½ N2
Средний случай. Количество сравнений ~ 1,39 Nlog2N
На 39% сравнений больше, чем у сортировки слиянием
Но, на практике, быстрее сортировки слиянием, потому что меньше перемещаются данные
Перетасовка
Гарантирует отсутствия худшего случая
Предупреждение. Часть реализаций быстрой сортировки приводят к квадратичному времени выполнения если:
Массив отсортирован или отсортирован в обратном порядке
Имеется много дубликатов (даже если они перемешаны)
Скачать все slide презентации Перетасовка Кнута. Быстрая сортировка (Quicksort) одним архивом:
