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 - всегда может случиться плохая последовательность делений на части, ведущая к квадратичному поведению.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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