Математические основы сортировки: получение ожидаемых сравнений и свопов в Quicksort
Quicksort — широко используемый алгоритм сортировки, известный своей эффективностью. Понимание его производительности включает анализ ожидаемого количества сравнений и свопов во время выполнения. В этой статье исследуются математические принципы, лежащие в основе этих ожиданий, с акцентом на вероятностный анализ Quicksort.
Ожидаемое количество сравнений
Ожидаемое количество сравнений в Quicksort зависит от выбора поворота и процесса разделения.Предполагая, что все перестановки одинаково вероятны, средний случай можно проанализировать с помощью рекурсивных уравнений. Для массива размеров n ожидаемые сравнения, обозначаемые как C(n), удовлетворяют рецидиву:
C(n) = n - 1 + frac{1}{n} sum {k=0}^{n-1} [C(k) + C(n - 1 - k)]
Этот рецидив упрощает известный результат: C(n) ≈ 2n ln n для больших n.Вывод предполагает суммирование всех возможных положений поворота и применение свойств гармонических чисел.
Ожидаемое количество свопов
Свопы в Quicksort происходят в процессе разделения. Ожидаемое количество свопов связано с количеством сравнений и распределением вариантов поворотов. При равномерной случайности ожидаемые свопы, обозначаемые как S(n), могут быть аппроксимированы путем анализа этапов разделения.
Каждый шаг перегородки включает в себя замену элементов для обеспечения правильного размещения разворота. Ожидаемые свопы на перегородку пропорциональны размеру подкатегории. Подведение итогов по всем рекурсивным вызовам дает приближение: S(n) ≈ n ln n.
Краткое изложение ожиданий
- Сравнение: Приблизительно 2n ln n для больших n.
- Свопы: Приблизительно n ln n для больших n.
- Обе метрики растут логарифмически с размером массива, что отражает эффективность Quicksort.