Суть этого вопроса не в том, чтобы обсуждать достоинства этого по сравнению с любым другим алгоритмом сортировки - конечно, есть много других вопросов, которые делают это. Этот вопрос о названии. Почему Quicksort называется «Quicksort»? Конечно, это "быстро", большую часть времени, но не всегда. Возможность вырождения в O (N ^ 2) хорошо известна. Существуют различные модификации быстрой сортировки, которые смягчают эту проблему, но те, которые сводят наихудший случай к гарантированному O (n log n), больше не называются быстрой сортировкой. (например, Introsort).
Мне просто интересно, почему из всех известных алгоритмов сортировки это единственное, заслуживающее названия «быстрый», которое описывает не то, как работает алгоритм, а то, насколько он быстр (обычно). Mergesort называется так потому, что объединяет данные. Heapsort называется так, потому что он использует кучу. Интросорт получил свое название от «Интроспективы», поскольку он контролирует собственную производительность, чтобы решить, когда переключаться с быстрой сортировки на Heapsort. Аналогично для всех более медленных - Bubblesort, Insertion sort, Selection sort и т. Д. Все они названы так, как они работают. Единственное другое исключение, которое я могу придумать, это «Богосорт», который на самом деле является просто шуткой, которую никто никогда не использует на практике. Почему Quicksort не называется чем-то более наглядным, например, «сортировка по разделам» или «сортировка по оси», которые описывают то, что на самом деле делает? Это даже не тот случай, когда «пришел первым». Mergesort был разработан за 15 лет до Quicksort. (1945 и 1960 соответственно, согласно Википедии)
Я думаю, это действительно больше вопрос истории, чем вопрос программирования. Мне просто любопытно, как это получило название - это был просто хороший маркетинг?
источник
What's in a name? that which we call a rose By any other name would smell as sweet;Это или так же быстро. Кроме того, вероятность вырождения в O (N ^ 2) имеет небольшой шанс, и N LogN довольно хорош для алгоритма, несмотря на то, что у нас сегодня более быстрые алгоритмы. Кроме того, к тому времени, когда появилось что-то более быстрое, было уже слишком поздно, все уже называли это быстрой сортировкой!Ответы:
В 1962 году исследование алгоритмов сортировки было не таким продвинутым, как сегодня, и ученый-компьютерщик Тони Хоар нашел новый алгоритм, который был быстрее, чем другой, поэтому он опубликовал статью под названием «Быстрая сортировка», и, как только она была процитирована, заголовок остался.
Цитирую аннотацию:
источник
Я полагаю, что первоначально он назывался Hoare Sort по имени изобретателя, но название изменилось довольно рано из-за того, что Hoare звучит немного близко к проститутке на английском языке. Что касается того, почему они выбрали «быстрый» вместо чего-то другого, я не уверен.
источник
Я полагаю, что это потому, что в то время, когда это было изобретено, это было намного быстрее, чем все (или, скорее, большинство, так как скорость также сильно зависит от вида данных, а в некоторых случаях другие алгоритмы становятся намного быстрее, чем быстрая сортировка) алгоритмы там.
Так что да, это исторический (однако я не знаю точно эту историю ...)
Но я согласен, что его имя должно содержать подсказку алгоритма ...
источник