Презентация Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок абсолютно бесплатно. Урок-презентация на эту тему содержит всего 44 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:44 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:3.10 MB
- Просмотров:64
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Быстрая сортировка
(Quicksort)
№2 слайд
Содержание слайда: Два классических алгоритма сортировки
Критические компоненты в мировой вычислительной инфраструктуре
Понимание научных основ этих алгоритмов даст нам возможность разрабатывать прикладные системы для решения реальных задач
Быстрая сортировка входит в десятку самых полезных алгоритмов, разработанных в 20-м веке
№3 слайд
Содержание слайда:
№4 слайд
Содержание слайда: Быстрая сортировка
Основной план
Перемешать элементы случайным образом
Разбиение для элемента j
a[j] оставить на месте
Нет элементов меньше чем a[j] с правой стороны
Нет элементов больше чем a[j] с левой стороны
Отсортировать каждую часть рекурсивно
№5 слайд
Содержание слайда: Быстрая сортировка
Повторять до тех пор, пока i и j не пересекутся
Проверять i-ые элементы до тех пор пока a[i] < a[lo]
Проверять j-ые элементы до тех пор пока a[j] > a[lo]
Поменять местами a[i] и a[j]
Видео 1
№6 слайд
Содержание слайда: Быстрая сортировка: реализация разбиения на Java
№7 слайд
Содержание слайда: Быстрая сортировка: реализация на Java
№8 слайд
Содержание слайда: Быстрая сортировка
№9 слайд
Содержание слайда: Быстрая сортировка
№10 слайд
Содержание слайда: Быстрая сортировка: реализация
Не требует дополнительной памяти
Выход из циклов. Обращайте особое внимание на условия выхода из циклов
Ограничения. Проверка j == lo излишняя, но i == hi нет
Рандомизация. Перетасовка нужна чтобы обеспечить гарантии производительности
Равные ключи. Если присутствуют дубликаты, то можно использовать другой вариант алгоритма
№11 слайд
Содержание слайда: Быстрая сортировка: эмпирический анализ
Оценка времени выполнения:
На ПК 108 сравнений/секунду
На суперкомпьютере 1012 сравнений/секунду
№12 слайд
Содержание слайда: Быстрая сортировка: лучший случай
Лучший случай. Количество сравнений ~ N log2N
№13 слайд
Содержание слайда: Быстрая сортировка: худший случай
Худший случай. Количество сравнений ~ ½ N2
№14 слайд
Содержание слайда: Быстрая сортировка: средний случай
№15 слайд
Содержание слайда: Быстрая сортировка: свойства
Худший случай. Квадратичное количество сравнений
N + (N-1) + (N-2) + … + 1 ~ ½ N2
Средний случай. Количество сравнений ~ 1,39 Nlog2N
На 39% сравнений больше, чем у сортировки слиянием
Но, на практике, быстрее сортировки слиянием, потому что меньше перемещаются данные
Перетасовка
Гарантирует отсутствия худшего случая
Предупреждение. Часть реализаций быстрой сортировки приводят к квадратичному времени выполнения если:
Массив отсортирован или отсортирован в обратном порядке
Имеется много дубликатов (даже если они перемешаны)
№16 слайд
Содержание слайда: Быстрая сортировка: свойства
Утверждение. Быстрая сортировка не требует дополнительной памяти
Доказательство
Разделение требует дополнительную память размером константа
Рекурсия требует стек размером логарифм
Быстрая сортировка не устойчива
№17 слайд
Содержание слайда: Быстрая сортировка: реализация
Используйте сортировку вставками для маленьких подмассивов
Быстрая сортировка очень дорогая для маленьких подмассивов
Подмассивы для сортировки вставками ~ 10
№18 слайд
Содержание слайда: Быстрая сортировка: реализация
Разбиение по медиане
Поиск медианы из небольшой выборки элементов
Медиана из 3-х случайных элементов
№19 слайд
Содержание слайда: Быстрая сортировка с сортировкой вставками и медианой из 3-х
№20 слайд
Содержание слайда: Выбор
(Selection)
№21 слайд
Содержание слайда: Выбор
Цель. В массиве размером N, найти k-й наименьший элемент
Пример. Min (k = 0), max (k = N-1), median (k = N / 2)
Применение
Порядковая статистика
Поиск наибольшего элемента
Руководствуйтесь теорией
NlogN верхняя граница
N верхняя граница для k = 1, 2, 3.
N нижняя граница
№22 слайд
Содержание слайда: Быстрый выбор (Quick-select)
Разделение массива
a[j] остается на месте
Слева нет элемента больше j
Справа нет элемента меньше j
Повторять для одного подмассива, в зависимости от j; остановиться, когда j равно k
№23 слайд
Содержание слайда: Быстрый выбор: математический анализ
Утверждение. Quick-select в среднем работает за линейное время
Доказательство
Каждый шаг делит массив пополам: N + N/2 + N/4 + … + 1 ~ 2N сравнений
Формула анализа похожа на Q-sort
CN = 2N + 2k ln(N/k) + 2(N-k) ln(N/(N-k))
Замечание. Q-select использует ~ ½ N2 сравнений в худшем случае, но (как и для Q-sort) перемешивание дает вероятностную гарантию
№24 слайд
Содержание слайда: Быстрый выбор
Утверждение. Алгоритм выбора, основанный на сравнении, в худшем случае работает за линейное время
№25 слайд
Содержание слайда: Повторяющиеся ключи
№26 слайд
Содержание слайда: Повторяющиеся ключи
Часто приходится сортировать данные с повторяющимися ключами
По возрасту людей
Удалять повторяющиеся письма
По профессии или должности
Обычно в таких случаях
Огромный массив данных
Небольшое количество значений ключей
№27 слайд
Содержание слайда: Быстрый выбор (Quick-select)
Сортировка слиянием для массива с дубликатами. От ½ N log2N до N log2N сравнений
Q-sort для массива с дубликатами
Алгоритм выполняется за квадратичное время, если не происходит остановки на элементе равном текущему
В 1990-х пользователи С нашли этот дефект в qsort()
№28 слайд
Содержание слайда: Проблема повторяющихся ключей
Ошибка. Все элементы остаются на одной стороне
Результат. ~ ½ N2 сравнений, когда все ключи равны
В А А В А В В В С С С А А А А А А А А А А А
Рекомендация. Останавливать сканирование, если элемент равен центральному элементу
Результат. ~ N log2N сравнений, когда все ключи равны
B A A B A B C C B C B А А А А А А А А А А А
Желаемый случай. Оставлять элементы равные центральному элементу на месте
A A A B B B B B C C C А А А А А А А А А А А
№29 слайд
Содержание слайда: Трехчастное разбиение
Цель. Делим массив на 3 части
Элементы между lt и gt, равные центральному элементу v
Нет элемента больше слева от lt
Нет элемента меньше справа от gt
№30 слайд
Содержание слайда: Трехчастное разбиение Дейкстры
Берем v равное a[lo]
Сканируем i слева на право
(a[i] < v): меняем местами a[lt] и a[i]; инкремент lt и i
(a[i] > v): меняем местами a[gt] и a[i]; декремент gt
(a[i] == v): инкремент i
Видео 3
№31 слайд
Содержание слайда: Трехчастное разбиение Дейкстры
№32 слайд
Содержание слайда: Трехчастное разбиение Дейкстры: реализация на Java
№33 слайд
Содержание слайда: Трехчастное разбиение Дейкстры: трассировка
№34 слайд
Содержание слайда: Повторяющиеся ключи: нижняя граница
№35 слайд
Содержание слайда: Применение сортировок
№36 слайд
Содержание слайда: Применение сортировок
№37 слайд
Содержание слайда: Сортировки в Java
Arrays.sort()
Есть особые методы для примитивных типов
Методы для типов данных реализованных с помощью Comparable
Методы использующие Comparator
Используется быстрая сортировка для примитивных типов; сортировка слиянием для объектов
№38 слайд
Содержание слайда:
№39 слайд
Содержание слайда: Применение сортировок на практике
Основной алгоритм — Q-sort
Сортировка вставками для маленьких подмассивов
Трехчастное разбиение
Разбиение
Маленький массив: средний элемент
Средний массив: медиана из трех
Большой массив: девятки Тьюки
№40 слайд
Содержание слайда: Девятки Тьюки
Медиана из трех медиан из трех
Аппроксимация медианы из 9-ти
Использует не более 12 сравнений
№41 слайд
Содержание слайда: Переполнение стека в Java
Переполнение стека рекурсии в Java рушит программу
Выполнение программы за квадратичное время
№42 слайд
Содержание слайда:
№43 слайд
Содержание слайда: Какую сортировку выбрать?
Атрибуты
Стабильность
Параллелизм
Детерминированность
Дубликаты
Типы ключей
Связный список или массив
Количество элементов
Упорядоченность в массиве
Гарантии производительности
Комбинирование сортировок
Достаточно ли создано сортировок?
№44 слайд
Содержание слайда: Сортировки. Выводы
Скачать все slide презентации Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок одним архивом:
