2

Что делать если необходимо отсортировать массив, например 6 5 2 9 1 3 7 4 используя в качестве опорного элемента, именно средний элемент. В моем случае 9 либо 1. Я не имею ввиду выбор медианы 3 элементов. Дело в том что выходит что 9 наибольшее значение, а 1 наименьшее. Не пойму как быть с опорным элементом в этом случае. Как быть ? Спасибо.

2
  • 2
    Оставлять как есть, корректность алгоритма от этого не поменяется, просто вы получите худший из возможных вариантов и увеличение времени выполнения. По факту вы просто отделите один элемент и пойдете сортировать оставшиеся n-1. Ну или можете улучшить выборку опорного элемента.
    – Alex Krass
    19 июл 2018 в 18:11
  • 3
    Так а в чем проблема? Если выбранный опорный элемент далек от медианы, то получится "плохое" разбиение - с пустой левой или правой частью. Но это никак не мешает алгоритму продолжать работать по общей схеме. Ничего страшного. Если у вас на всех уровнях рекурсии будет получаться "плохое" разбиение, то алгоритм будет работать за O(n^2), но на корректность результата это не влияет - массив будет отсортирован. 19 июл 2018 в 18:12

1 ответ 1

3

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

Следующий шаг может быть лучше, а может и не быть - это свойство QuickSort - всегда может случиться плохая последовательность делений на части, ведущая к квадратичному поведению.

Ваш ответ

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

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