Каково настоящее название медианного сорта и / или где я могу найти больше материала о нем?

Question

Я читаю книгу Алгоритмы в двух словах , опубликованную O'Reilly Media, и я читал раздел об алгоритмах сортировки и нашел один, который называется Median Sort. Поскольку я никогда не слышал об этом раньше, и в моем учебнике из CS3 (который охватывал алгоритмы) его нет в списке, я нашел его в Google и попытался найти в Википедии, но ничего не нашел. Я был бы очень признателен, если бы кто-то мог предоставить имя, под которым я мог бы легко найти алгоритм или указать мне другие ресурсы об этом. Спасибо.

Кроме того, от того, что я могу сказать об алгоритме, это по существу Quicksort за исключением того, всегда использует среднее значение в качестве опоры. Под медианным значением я подразумеваю, что он сканирует массив элементов и выбирает среднее значение в качестве оси, а не средний элемент в массиве в качестве точки. Кроме того, в книге упоминается Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) в отношении рода "Медиана".

Answer 1

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

Правка ( много позже, после просмотра правки в вопросе): похоже, что вы говорите об использовании алгоритма "медиана медиан" для выбора элемента сводки для быстрой сортировки. Алгоритм медианы медиан лучше известен тем, что он используется независимо в качестве альтернативы (или уточнения, в зависимости от вашей точки зрения) алгоритма выбора Хоара. Известно, что это позволяет найти медиану (или другой ранг, но в данном случае мы заботимся только о медиане) в линейном времени.

Суть в том, что sort действительно все еще является быстрой сортировкой. Описание Хора выбора элемента центра не требует и не запрещает выбор медианы:

Первым шагом процесса разделения является выбор конкретного значения ключа, которое, как известно, находится в диапазоне ключей элементов в сегменте, который должен быть отсортирован. Простой способ обеспечить это - выбрать фактическое значение ключа одного из элементов в сегменте. Выбранное значение ключа будет называться bound .

Конечно, почти все теперь называют это «стержнем» вместо «связанного», но это в основном не имеет значения. Метод, используемый для выбора точки разворота / границы, остается открытым.

Answer 2

Поскольку у меня нет вышеупомянутой книги, я сделаю дикое предположение и скажу, что алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна (см. Также статью если вы хотите узнать больше), вероятно, используется для выбора сводной.Я также рекомендую вам прочитать общий алгоритм выбора на основе разделов из той же статьи в Википедии, так как я думаю, что это именно то, что вы ищете.

Answer 3

Мне не принадлежит книга, но я сделаю предположение. Алгоритм, на который ссылается книга, - это алгоритм SELECT Флойд-Ривеста . Блюм-Флойд-Пратт-Ривест-Тарьян (BFPRT) ссылается на этот документ, где они обсуждают свой алгоритм выбора PICK (теперь известный как Медиана медиан ):

M. Блум, Р. В. Флойд, В. Пратт, Р. Л. Ривест, Р. Э. Тарьян, «Границы времени для выбора», Журн. Комп. а также. Sys. Sci., Vol. 7, вып. 4, сс. 448-461, 1973.

Эта статья устанавливает раннее понимание проблемы выбора в информатике.

Answer 4

Да, вы правы, это похоже на быструю сортировку, но она лучше, чем быстрая сортировка, так как позволяет избежать тех случаев, когда ваши массивы делятся очень непропорционально (не равными половинами). Потому что в быстрой сортировке мы не можем быть уверены, что каждый раз наш массив будет разделен на две равные половины или почти равные половины. При медианной сортировке мы гарантируем это, заплатив цену за поиск медианы, но это может быть целесообразным для быстрой сортировки, аналогичной сортировке слиянием и преимущества сортировки на месте.