Презентация Рекурсия. Сортировка слиянием. Восходящая сортировка слиянием. Сложность сортировки. Устойчивость сортировок онлайн

Содержание слайда: Рекурсия

Содержание слайда: Пример бесконечной рекурсии У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:

Содержание слайда: Рекурсивная функция function arifmPr(base, iter: integer): integer; begin if iter = 1 then arifmPr:= base else arifmPr:= arifmPr(base, iter - 1) + base; end;

Содержание слайда: Рекурсивная функция arifmPr(2, 4) arifmPr:= arifmPr(2,3)+2 arifmPr:= 8+2 arifmPr(2, 3) arifmPr:= arifmPr(2,2)+2 arifmPr:= 6+2 arifmPr(2, 3) arifmPr:= arifmPr(2,2)+2 arifmPr:= 4+2 arifmPr(2, 2) arifmPr:= arifmPr(2,1)+2 arifmPr:= 2+2 arifmPr(2, 1) arifmPr:= 2

Содержание слайда: Сортировка слиянием (Mergesort)

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

Содержание слайда: Сортировка слиянием Основной план Разделить массив на две половины Рекурсивно отсортировать каждую половину Соединить две половины

Содержание слайда: Сортировка слиянием Цель. Получить два отсортированных подмассива от a[lo] до a[mid] и от a[mid+1] до a[hi] Видео 1

Содержание слайда: Слияние: реализация на Java

Содержание слайда: Assertions Assertion. Оператор для тестирования программы Помогает обнаружить логические ошибки Документирует код Java assert оператор. Генерирует исключительную ситуацию, если условие не верно

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

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

Содержание слайда: Видео 2 Видео 2

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

Содержание слайда: Сортировка слиянием: количество сравнений и обращений к массиву Утвержение. Сортировка слиянием использует NlogN сравнений и 6 NlogN обращений для сортировки массива размером N Доказательство. C(N) — количество сравнений, A(N) — количество обращений

Содержание слайда: Разделяй и властвуй Утверждение. Если D(N) удовлетворяет D(N) = 2D(N/2) + N, где N > 1 и D(1) = 0, то D(N) = Nlog2N

Содержание слайда: Разделяй и властвуй Утверждение. Если D(N) удовлетворяет D(N) = 2D(N/2) + N, где N > 1 и D(1) = 0, то D(N) = Nlog2N

Содержание слайда: Разделяй и властвуй Утверждение. Если D(N) удовлетворяет D(N) = 2 D(N/2) + N, где N > 1 и D(1) = 0, то D(N) = Nlog2N

Содержание слайда: Анализ сортировки слиянием: память Утверждение. Сортировка слиянием использует дополнительную память пропорциональную N Массиву aux[] нужен N ячеек для последнего слияния

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

Содержание слайда: Сортировка слиянием: реализация Остановка если все отсортировано Если самый большой элемент первой половины <= самому маленькому элементу второй половины, то подмассив отсортирован Полезно для частично-упорядоченного массива

Содержание слайда: Сортировка слиянием: реализация Ограничить копирование во вспомогательный массив Экономит время (но не память). Менять местами основной и вспомогательный массив при рекурсивном вызове

Содержание слайда: Сортировка слиянием: визуализация

Содержание слайда: Восходящая сортировка слиянием (Bottom-up mergesort)

Содержание слайда: Восходящая сортировка слиянием Начинаем со слияния подмассивов с размером 1 Повторяем для подмассивов с размерами 2, 4, 8, 16, ...

Содержание слайда: Восходящая сортировка слиянием: реализация на Java Итог. Простая и не рекурсивная версия сортировки слиянием (работает на 10% медленнее, чем нисходящая сортировка слиянием)

Содержание слайда: Восходящая сортировка слиянием: визуализация

Содержание слайда: Сложность сортировки

Содержание слайда: Сложность сортировки Вычислительная сложность - основа для обучения эффективным алгоритмам для решения конкреной проблемы Х Вычислительная модель. Возможные операции Стоимость модели. Количество операций Верхняя граница. Стоимость, гарантированная определенным алгоритмам для задачи Х Нижняя граница. Доказанное ограничение стоимости для всех алгоритмов для задачи Х Оптимальный алгоритм. Алгоритм с лучшей максимально возможной стоимостью для задачи Х (когда верхняя и нижняя граница приблизительно совпадают) Пример: сортировка Вычислительная модель: дерево принятия решений Стоимость модели: количество сравнений Верхняя граница: ~ Nlog2N для сортировки слиянием Нижняя граница: ? Оптимальный алгоритм: ?

Содержание слайда: Дерево принятия решений (для 3-х элементов)

Содержание слайда: Нижняя граница для сортировки на основе сравнений Утверждение. Ни один алгоритм сортировки, основанный на сравнениях, не может гарантировать упорядочить N элементов, выполнив менее log2(N!) ~ Nlog2(N) сравнений Доказательство Все элементы массива различны В худшем случае высота дерева будет h Бинарное дерево высотой h имеет максимум 2h листьев N! <= количество листьев <= 2h

Содержание слайда: Нижняя граница для сортировки на основе сравнений Утверждение. Ни один алгоритм сортировки, основанный на сравнениях, не может гарантировать упорядочить N элементов, выполнив менее log2(N!) ~ Nlog2(N) сравнений Доказательство Все элементы массива различны В худшем случае высота дерева будет h Бинарное дерево высотой h имеет максимум 2h листьев N! <= количество листьев <= 2h

Содержание слайда: Сложность сортировки Вычислительная модель. Возможные операции Стоимость модели. Количество операций Верхняя граница. Стоимость, гарантированная определенным алгоритмам для задачи Х Нижняя граница. Доказанное ограничение стоимости для всех алгоритмов для задачи Х Оптимальный алгоритм. Алгоритм с лучшей максимально возможной стоимостью для задачи Х (когда верхняя и нижняя граница приблизительно совпадают) Пример: сортировка Вычислительная модель: дерево принятия решений Стоимость модели: количество сравнений Верхняя граница: ~ Nlog2N для сортировки слиянием Нижняя граница: ~ Nlog2N Оптимальный алгоритм: сортировка слиянием Первая цель разработки алгоритмов: оптимальный алгоритм

Содержание слайда: Сложность сортировки Сравнения? Сортировка слиянием оптимальна по количеству сравнений Память? Сортировка слиянием не оптимальна по памяти

Содержание слайда: Сложность сортировки Можно снизить нижнюю границу для сортировки если есть информация о: Упорядоченности входных данных Распределении значений ключей Представлении ключей Частично-упорядоченный массив Дубликаты ключей. Зная распределение дубликатов во входных данных, мы можем отказаться от NlogN Представление ключей. Можем использовать цифровые/символьные сравнения ключей вместо сравнений номеров и строк

Содержание слайда: Устойчивость сортировок

Содержание слайда: Устойчивость Типичная задача. Отсортировать сначала по имени, а затем, по группам

Содержание слайда: Устойчивость Сортировка вставками и сортировка слиянием устойчивы (но не выборочная и Шелла)

Содержание слайда: Устойчивость: сортировка вставками Сортировка вставками устойчива Равные элементы не передвигаются

Содержание слайда: Устойчивость: выборочная сортировка Выборочная сортировка не устойчива Передвижения элементов на большие расстояния может нарушить порядок

Содержание слайда: Устойчивость: сортировка Шелла Сортировка Шелла не устойчива Передвижения элементов на большие расстояния может нарушить порядок

Содержание слайда: Устойчивость: сортировка слиянием Сортировка слиянием устойчива Если ключи равны, то берутся элементы из левого подмассива