1

Как реализовать алгоритм быстрой сортировки без медианного элемента?

1 ответ 1

3

Медианный элемент - это лишь один из способов выбора значения-разделителя (pivot), такая эвристика для уменьшения вероятности (но не полного исключения) плохого разбиения.

Сортировка будет работать и при использовании произвольного элемента - первого, последнего, среднего по индексу, или со случайным индексом.

Выбор первого или последнего не очень хорош, если массив уже сортирован (или почти сортирован) - нередкий случай, для других методов выбора разделителя вероятность плохого массива невелика.

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.