Как реализовать алгоритм быстрой сортировки без медианного элемента?
1 ответ
Медианный элемент - это лишь один из способов выбора значения-разделителя (pivot), такая эвристика для уменьшения вероятности (но не полного исключения) плохого разбиения.
Сортировка будет работать и при использовании произвольного элемента - первого, последнего, среднего по индексу, или со случайным индексом.
Выбор первого или последнего не очень хорош, если массив уже сортирован (или почти сортирован) - нередкий случай, для других методов выбора разделителя вероятность плохого массива невелика.
-
-
Если я буду каждый раз буду использовать рандом для pivot, то это не будет считаться медианным элементом?– DaniyarCommented 15 дек. 2020 в 18:53
-
Нет, выбор медианы из трёх и выбор случайного индекса - разные методы.– MBoCommented 15 дек. 2020 в 18:55
-
Мне нужна по заданию нужна Быстрая сортировка Хоару (без медианного (pivot) элемента). Если я выберу pivot = arr[random], это будет по заданию?– DaniyarCommented 16 дек. 2020 в 10:18
-
Pivot - это разделительный элемент. А его выбор может быть через медиану, случайным или другим способом. Что препод имел в виду - сказать трудно, т.к. QuickSort - сортировка, основанная на сравнениях. Но есть разновидности, например, поразрядная быстрая сортировка, однако гадать на кофейной гуще я не буду, нужно уточнить у того, кто задавал.– MBoCommented 16 дек. 2020 в 10:36