каждая группа в алгоритме быстрого выбора должна быть отсортирована?

Question

У меня есть вопрос, что мой учитель в своей лекции по алгоритму быстрого выбора говорит, что после того, как мы рассмотрим массив как группы из 5 элементов, ему не нужно сортировать каждую группу, он прав? потому что когда у нас есть группа типа <3,5,7,6,1> без сортировки, как мы можем найти медиану ??? спасибо

РЕДАКТИРОВАНИЕ: речь идет не о быстром выборе, а о линейном алгоритме общего выбора

Answer 1

Медиана - это floor(n / 2) + 1 -й наименьший элемент в отсортированном порядке, который алгоритм выбора может найти в O(n) (считая n нечетным для удобства).Поэтому, если вы знаете, что все элементы слева от k меньше k, а все элементы справа больше k и k находится в положении floor(n / 2) + 1, то вы знаете, что k - это медиана.Вам не нужно сортировать.

Например:

8 3 11 20 18 => 11 - это медиана, потому что она посередине и меньше всего после нее и больше, чем все раньшеЭто.Сортировка не требуется.

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

Answer 2

Если все, что вам нужно, это медиана, то сначала сортировка может оказаться более дорогой, чем просто запуск полуверсии сортировки выбора, в зависимости от вашего алгоритма сортировки.В массиве из n элементов вы знаете, что медиана будет средним (n / 2 + 1) элементом, если n нечетным, или средним из двух средних элементов (n / 2, n / 2 + 1), если четным.Поэтому выполните обычную сортировку выбора, но вместо выполнения всей операции O (N) запустите ее только наполовину, чтобы получить это выбранное медианное значение.

Вы также можете выполнить очень простую Bubble Sort, но только запустить ееп / 2 раза.Это гарантирует, что медиана находится посередине и концептуально проста.Сделайте это вручную на бумаге, если сомневаетесь.