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

Рекурсия

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

Рекурсивная функция 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 Представление ключей. Можем использовать цифровые/символьные сравнения ключей вместо сравнений номеров и строк

Устойчивость сортировок

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

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

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

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

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

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