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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Быстрая сортировка (Quicksort). Повторяющиеся ключи. Применение сортировок, слайд №1Быстрая сортировка (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)
Описание слайда:
Быстрая сортировка (Quicksort)

Слайд 2


Два классических алгоритма сортировки Критические компоненты в мировой вычислительной инфраструктуре Понимание научных основ этих алгоритмов даст нам возможность разрабатывать прикладные системы для решения реальных задач Быстрая сортировка входит в десятку самых полезных алгоритмов, разработанных в 20-м веке
Описание слайда:
Два классических алгоритма сортировки Критические компоненты в мировой вычислительной инфраструктуре Понимание научных основ этих алгоритмов даст нам возможность разрабатывать прикладные системы для решения реальных задач Быстрая сортировка входит в десятку самых полезных алгоритмов, разработанных в 20-м веке

Слайд 3


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

Слайд 4


Быстрая сортировка Основной план Перемешать элементы случайным образом Разбиение для элемента j a[j] оставить на месте Нет элементов меньше чем a[j] с правой стороны Нет элементов больше чем a[j] с левой стороны Отсортировать каждую часть рекурсивно
Описание слайда:
Быстрая сортировка Основной план Перемешать элементы случайным образом Разбиение для элемента 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
Описание слайда:
Быстрая сортировка Повторять до тех пор, пока i и j не пересекутся Проверять i-ые элементы до тех пор пока a[i] < a[lo] Проверять j-ые элементы до тех пор пока a[j] > a[lo] Поменять местами a[i] и a[j] Видео 1

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


Быстрая сортировка: реализация Не требует дополнительной памяти Выход из циклов. Обращайте особое внимание на условия выхода из циклов Ограничения. Проверка j == lo излишняя, но i == hi нет Рандомизация. Перетасовка нужна чтобы обеспечить гарантии производительности Равные ключи. Если присутствуют дубликаты, то можно использовать другой вариант алгоритма
Описание слайда:
Быстрая сортировка: реализация Не требует дополнительной памяти Выход из циклов. Обращайте особое внимание на условия выхода из циклов Ограничения. Проверка j == lo излишняя, но i == hi нет Рандомизация. Перетасовка нужна чтобы обеспечить гарантии производительности Равные ключи. Если присутствуют дубликаты, то можно использовать другой вариант алгоритма

Слайд 11


Быстрая сортировка: эмпирический анализ Оценка времени выполнения: На ПК 108 сравнений/секунду На суперкомпьютере 1012 сравнений/секунду
Описание слайда:
Быстрая сортировка: эмпирический анализ Оценка времени выполнения: На ПК 108 сравнений/секунду На суперкомпьютере 1012 сравнений/секунду

Слайд 12


Быстрая сортировка: лучший случай Лучший случай. Количество сравнений ~ N log2N
Описание слайда:
Быстрая сортировка: лучший случай Лучший случай. Количество сравнений ~ N log2N

Слайд 13


Быстрая сортировка: худший случай Худший случай. Количество сравнений ~ ½ N2
Описание слайда:
Быстрая сортировка: худший случай Худший случай. Количество сравнений ~ ½ N2

Слайд 14


Быстрая сортировка: средний случай
Описание слайда:
Быстрая сортировка: средний случай

Слайд 15


Быстрая сортировка: свойства Худший случай. Квадратичное количество сравнений N + (N-1) + (N-2) + … + 1 ~ ½ N2 Средний случай. Количество сравнений ~ 1,39 Nlog2N На 39% сравнений больше, чем у сортировки слиянием Но, на практике, быстрее сортировки слиянием, потому что меньше перемещаются данные Перетасовка Гарантирует отсутствия худшего случая Предупреждение. Часть реализаций быстрой сортировки приводят к квадратичному времени выполнения если: Массив отсортирован или отсортирован в обратном порядке Имеется много дубликатов (даже если они перемешаны)
Описание слайда:
Быстрая сортировка: свойства Худший случай. Квадратичное количество сравнений N + (N-1) + (N-2) + … + 1 ~ ½ N2 Средний случай. Количество сравнений ~ 1,39 Nlog2N На 39% сравнений больше, чем у сортировки слиянием Но, на практике, быстрее сортировки слиянием, потому что меньше перемещаются данные Перетасовка Гарантирует отсутствия худшего случая Предупреждение. Часть реализаций быстрой сортировки приводят к квадратичному времени выполнения если: Массив отсортирован или отсортирован в обратном порядке Имеется много дубликатов (даже если они перемешаны)

Слайд 16


Быстрая сортировка: свойства Утверждение. Быстрая сортировка не требует дополнительной памяти Доказательство Разделение требует дополнительную память размером константа Рекурсия требует стек размером логарифм Быстрая сортировка не устойчива
Описание слайда:
Быстрая сортировка: свойства Утверждение. Быстрая сортировка не требует дополнительной памяти Доказательство Разделение требует дополнительную память размером константа Рекурсия требует стек размером логарифм Быстрая сортировка не устойчива

Слайд 17


Быстрая сортировка: реализация Используйте сортировку вставками для маленьких подмассивов Быстрая сортировка очень дорогая для маленьких подмассивов Подмассивы для сортировки вставками ~ 10
Описание слайда:
Быстрая сортировка: реализация Используйте сортировку вставками для маленьких подмассивов Быстрая сортировка очень дорогая для маленьких подмассивов Подмассивы для сортировки вставками ~ 10

Слайд 18


Быстрая сортировка: реализация Разбиение по медиане Поиск медианы из небольшой выборки элементов Медиана из 3-х случайных элементов
Описание слайда:
Быстрая сортировка: реализация Разбиение по медиане Поиск медианы из небольшой выборки элементов Медиана из 3-х случайных элементов

Слайд 19


Быстрая сортировка с сортировкой вставками и медианой из 3-х
Описание слайда:
Быстрая сортировка с сортировкой вставками и медианой из 3-х

Слайд 20


Выбор (Selection)
Описание слайда:
Выбор (Selection)

Слайд 21


Выбор Цель. В массиве размером N, найти k-й наименьший элемент Пример. Min (k = 0), max (k = N-1), median (k = N / 2) Применение Порядковая статистика Поиск наибольшего элемента Руководствуйтесь теорией NlogN верхняя граница N верхняя граница для k = 1, 2, 3. N нижняя граница
Описание слайда:
Выбор Цель. В массиве размером 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
Описание слайда:
Быстрый выбор (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) перемешивание дает вероятностную гарантию
Описание слайда:
Быстрый выбор: математический анализ Утверждение. 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()
Описание слайда:
Быстрый выбор (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 А А А А А А А А А А А
Описание слайда:
Проблема повторяющихся ключей Ошибка. Все элементы остаются на одной стороне Результат. ~ ½ 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
Описание слайда:
Трехчастное разбиение Цель. Делим массив на 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
Описание слайда:
Трехчастное разбиение Дейкстры Берем 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
Описание слайда:
Трехчастное разбиение Дейкстры: реализация на Java

Слайд 33


Трехчастное разбиение Дейкстры: трассировка
Описание слайда:
Трехчастное разбиение Дейкстры: трассировка

Слайд 34


Повторяющиеся ключи: нижняя граница
Описание слайда:
Повторяющиеся ключи: нижняя граница

Слайд 35


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

Слайд 36


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

Слайд 37


Сортировки в Java Arrays.sort() Есть особые методы для примитивных типов Методы для типов данных реализованных с помощью Comparable Методы использующие Comparator Используется быстрая сортировка для примитивных типов; сортировка слиянием для объектов
Описание слайда:
Сортировки в Java Arrays.sort() Есть особые методы для примитивных типов Методы для типов данных реализованных с помощью Comparable Методы использующие Comparator Используется быстрая сортировка для примитивных типов; сортировка слиянием для объектов

Слайд 38


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

Слайд 39


Применение сортировок на практике Основной алгоритм — Q-sort Сортировка вставками для маленьких подмассивов Трехчастное разбиение Разбиение Маленький массив: средний элемент Средний массив: медиана из трех Большой массив: девятки Тьюки
Описание слайда:
Применение сортировок на практике Основной алгоритм — Q-sort Сортировка вставками для маленьких подмассивов Трехчастное разбиение Разбиение Маленький массив: средний элемент Средний массив: медиана из трех Большой массив: девятки Тьюки

Слайд 40


Девятки Тьюки Медиана из трех медиан из трех Аппроксимация медианы из 9-ти Использует не более 12 сравнений
Описание слайда:
Девятки Тьюки Медиана из трех медиан из трех Аппроксимация медианы из 9-ти Использует не более 12 сравнений

Слайд 41


Переполнение стека в Java Переполнение стека рекурсии в Java рушит программу Выполнение программы за квадратичное время
Описание слайда:
Переполнение стека в Java Переполнение стека рекурсии в Java рушит программу Выполнение программы за квадратичное время

Слайд 42


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

Слайд 43


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

Слайд 44


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

Скачать

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