Что делать если необходимо отсортировать массив, например 6 5 2 9 1 3 7 4 используя в качестве опорного элемента, именно средний элемент. В моем случае 9 либо 1. Я не имею ввиду выбор медианы 3 элементов. Дело в том что выходит что 9 наибольшее значение, а 1 наименьшее. Не пойму как быть с опорным элементом в этом случае. Как быть ? Спасибо.
-
2Оставлять как есть, корректность алгоритма от этого не поменяется, просто вы получите худший из возможных вариантов и увеличение времени выполнения. По факту вы просто отделите один элемент и пойдете сортировать оставшиеся n-1. Ну или можете улучшить выборку опорного элемента.– Alex Krass19 июл 2018 в 18:11
-
3Так а в чем проблема? Если выбранный опорный элемент далек от медианы, то получится "плохое" разбиение - с пустой левой или правой частью. Но это никак не мешает алгоритму продолжать работать по общей схеме. Ничего страшного. Если у вас на всех уровнях рекурсии будет получаться "плохое" разбиение, то алгоритм будет работать за O(n^2), но на корректность результата это не влияет - массив будет отсортирован.– AnT stands with Russia19 июл 2018 в 18:12
1 ответ
Да просто используйте этот элемент как разделительный и получайте деление массива - да, самое плохое, какое может быть, с отделением всего одного элемента.
Следующий шаг может быть лучше, а может и не быть - это свойство QuickSort - всегда может случиться плохая последовательность делений на части, ведущая к квадратичному поведению.