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

Два классических алгоритма сортировки

Критические компоненты в мировой вычислительной инфраструктуре
Понимание научных основ

Быстрая сортировка

Основной план
Перемешать элементы случайным образом
Разбиение для элемента j
a[j] оставить на

Быстрая сортировка

Повторять до тех пор, пока i и j не пересекутся
Проверять

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

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

Быстрая сортировка

Быстрая сортировка

Быстрая сортировка: реализация

Не требует дополнительной памяти
Выход из циклов. Обращайте особое внимание

Быстрая сортировка: эмпирический анализ

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

Быстрая сортировка: лучший случай

Лучший случай. Количество сравнений ~ N log2N

Быстрая сортировка: худший случай

Худший случай. Количество сравнений ~ ½ N2

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

Быстрая сортировка: свойства

Худший случай. Квадратичное количество сравнений
N + (N-1) + (N-2)

Быстрая сортировка: свойства

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

Быстрая сортировка: реализация

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

Быстрая сортировка: реализация

Разбиение по медиане
Поиск медианы из небольшой выборки элементов
Медиана из

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

Выбор
(Selection)

Выбор

Цель. В массиве размером N, найти k-й наименьший элемент
Пример. Min (k

Быстрый выбор (Quick-select)

Разделение массива
a[j] остается на месте
Слева нет элемента больше j
Справа

Быстрый выбор: математический анализ

Утверждение. Quick-select в среднем работает за линейное время
Доказательство
Каждый

Быстрый выбор

Утверждение. Алгоритм выбора, основанный на сравнении, в худшем случае работает

Повторяющиеся ключи

Повторяющиеся ключи

Часто приходится сортировать данные с повторяющимися ключами
По возрасту людей
Удалять повторяющиеся

Быстрый выбор (Quick-select)

Сортировка слиянием для массива с дубликатами. От ½ N

Проблема повторяющихся ключей

Ошибка. Все элементы остаются на одной стороне
Результат. ~ ½

Трехчастное разбиение

Цель. Делим массив на 3 части
Элементы между lt и gt,

Трехчастное разбиение Дейкстры

Берем v равное a[lo]
Сканируем i слева на право
(a[i] <

Трехчастное разбиение Дейкстры

Трехчастное разбиение Дейкстры: реализация на Java

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

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

Применение сортировок

Применение сортировок

Сортировки в Java

Arrays.sort()
Есть особые методы для примитивных типов
Методы для типов данных

Применение сортировок на практике

Основной алгоритм — Q-sort
Сортировка вставками для маленьких подмассивов
Трехчастное

Девятки Тьюки

Медиана из трех медиан из трех
Аппроксимация медианы из 9-ти
Использует не

Переполнение стека в Java

Переполнение стека рекурсии в Java рушит программу
Выполнение программы

Какую сортировку выбрать?

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