Наихудший случай быстрой сортировки с использованием метода median-of-3

Question

Можем ли мы всегда избегать наихудшего случая быстрой сортировки с использованием метода медианы-3?

Answer 1

Алгоритм Quick Sort работает следующим образом:

1. Если количество элементов в S равно 0 или 1, вернуть (базовый случай).
2. Выберите любой элемент V в S (так называемый стержень).
3. Разделить элементы в S, кроме v, на две непересекающиеся группы
4. Return {QuickSort (S1) + v + QuickSort (S2)}

Наихудший случай дляБыстрая сортировка с использованием метода медиана-3 - это когда выбранная точка сводит размер проблемы к минимуму.Это означает, что выбранный свод обеспечивает максимально удаленный раздел.И поскольку мы используем метод median-of-3, выбранный раздел не может быть ни самым большим, ни самым маленьким элементом, так как наш выбранный метод гарантирует, что раздел имеет элемент, больший и меньший, чем медиана.

Следовательно,если вы имеете в виду, можем ли мы избежать наихудшего случая истинного сценария O (n ^ 2), где каждый элемент находится в порядке обратного значения, и мы должны разбить весь список, тогда да, мы можем избежать наихудшего сценария.

Смысл использования метода медиана-3 - приблизить нас к среднему времени выполнения быстрой сортировки : O (nlogn).Это связано с тем, что, избегая выбора самых дальних элементов в списке для выбора нашего раздела, мы можем минимизировать наше отклонение от наилучшего / среднего времени выполнения O (nlogn).

Используя метод median-of-3позволит нам никогда не искать во всем списке нужный раздел, а начинать где-то посередине.Следовательно, мы можем избежать наихудшего времени выполнения O (n ^ 2) и установить среднее время выполнения O (nlogn)