Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок

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

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №2

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №3

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №4

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №5

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №6

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №7

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №8

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №9

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №10

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №11

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №12

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №13

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №14

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №15

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №16

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №17

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №18

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №19

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №20

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №21

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №22

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №23

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №24

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №25

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №26

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №27

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №28

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №29

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №30

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №31

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №32

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №33

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №34

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №35

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №36

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №37

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №38

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №39

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №40

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №41

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №42

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №43

Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №44

Содержание ▲

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

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

Слайд 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

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

Какую сортировку выбрать? Атрибуты Стабильность Параллелизм Детерминированность Дубликаты Типы ключей Связный список или массив Количество элементов Упорядоченность в массиве Гарантии производительности Комбинирование сортировок Достаточно ли создано сортировок?