What is the real name of median sort and/or where can I find more material on it
I'm reading the book Algorithms in a Nutshell published by O'Reilly Media and I was reading the section on sorting algorithms and found one called Median Sort. Since I had never heard of it before and my textbook from CS3 (which covered algorithms) did not have it listed, I googled it and tried looking it up on Wikipedia and found nothing. I would greatly appreciate it if someone could provide the name I could easily look the algorithm up under or point me to other resources about it. Thank you.
Also, from what I can tell about the algorithm, it's essentially Quicksort except it always uses the median value as the pivot. By median value I mean it seems to scan the array of items and pick the middle value as the pivot, not pick the middle item in the array as the pivot. Also, the book mentions a Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) in relation to the "Median" sort.
1 ответ
Большинство версий быстрой сортировки выбирают (например) медианное значение трех элементов (обычно первого, среднего и последнего), что дает то, что обычно называется медианой из трех элементов быстрой сортировки. Просто начните со среднего элемента, поскольку точка поворота обычно не подходит для какого-либо имени, кроме быстрой сортировки.
Редактировать ( много позже, увидев правку в вопросе): похоже, что вы говорите об использовании алгоритма «медианы медиан» для выбора опорного элемента для быстрой сортировки. Алгоритм медианы медиан более известен тем, что используется независимо в качестве альтернативы (или уточнения, в зависимости от вашей точки зрения) алгоритма выбора Хоара. Известно, что это позволяет найти медиану (или другой ранг, но в этом случае нас интересует только медиана) за линейное время.
Суть в том, что сортировка на самом деле все еще является быстрой сортировкой. Описание Хоара выбора опорного элемента не требует и не запрещает средства выбора медианы:
Первым шагом процесса разделения является выбор определенного ключевого значения, которое, как известно, находится в диапазоне ключей элементов в сегмент, который нужно отсортировать. Простой способ убедиться в этом - выбрать фактическое значение ключа одного из элементов сегмента. Выбранное значение ключа будет называться границей .
Конечно, теперь почти все называют это «точкой поворота», а не «границей», но в большинстве случаев это не имеет значения. Метод, используемый для выбора точки поворота / границы, остается открытым.