Второй пример: быстрая сортировка
Рандомизированный метод «разделяй и властвуй», который использовался для нахождения медианы, также заложен в основу алгоритма быстрой сортировки. Как и прежде, мы выбираем разделитель для входного множества S и разбиваем S по элементам со значениями ниже и выше разделителя.
Различие в том, что вместо поиска медианы только с одной стороны от разделителя мы рекурсивно сортируем обе стороны и соединяем два отсортированных фрагмента (с промежуточным разделителем) для получения общего результата. Кроме того, необходимо явно включить базовый случай для рекурсивного кода: рекурсия используется только для множеств с размером 4 и более. Полное описание алгоритма быстрой сортировки приведено ниже.
Quicksort(S):
Если |S| ≤ 3
Отсортировать S
Вывести отсортированный список Иначе
Случайно выбрать разделитель ai Ѯ S с равномерным распределением Для каждого элемента aj множества S
Включить aj в множество S −, если aj < ai
Включить aj в множество S +, если aj > ai
Конец цикла
Рекурсивно вызвать Quicksort(S −) и Quicksort(S +)
Вывести отсортированное множество S −,
затем ai и отсортированное множество S +
Конец Если
С другой стороны, если при каждой итерации в качестве разделителя выбирается медиана каждого множества, то получается рекуррентное отношение T(n) ≤ 2T(n/2) + cn, часто встречавшееся при анализе алгоритмов «разделяй и властвуй» главы 5; время выполнения в этом случае составляет O(n log n).
Сейчас нас интересует ожидаемое время выполнения; мы покажем, что оно может быть ограничено величиной O(n log n) — почти такой же, как в лучшем случае при выборе разделителей идеально по центру. Наш анализ быстрой сортировки достаточно близко воспроизводит анализ нахождения медианы.
Как и в процедуре Select, использованной при поиске медианы, ключевую роль играет определение центрального разделителя — разделяющего множество так, чтобы каждая сторона содержала не менее четверти элементов. (Как упоминалось ранее, для анализа достаточно, чтобы каждая сторона содержала некоторую фиксированную часть элементов; четверть выбрана для удобства.)
Идея заключается в том, что случайный выбор с большой вероятностью приведет к центральному разделителю, а центральные разделители работают эффективно. В случае сортировки центральный разделитель разбивает задачу на две существенно меньшие подзадачи.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу