Warum heißt Quicksort "Quicksort"?

9

Bei dieser Frage geht es nicht darum, die Vorzüge eines anderen Sortieralgorithmus zu diskutieren - sicherlich gibt es viele andere Fragen, die dies tun. Diese Frage bezieht sich auf den Namen. Warum heißt Quicksort "Quicksort"? Sicher, es ist die meiste Zeit "schnell", aber nicht immer. Die Möglichkeit einer Degeneration zu O (N ^ 2) ist bekannt. Es gibt verschiedene Modifikationen an Quicksort, die dieses Problem mindern, aber diejenigen, die den schlimmsten Fall auf ein garantiertes O (n log n) reduzieren, werden im Allgemeinen nicht mehr als Quicksort bezeichnet. (zB Introsort).

Ich frage mich nur, warum von allen bekannten Sortieralgorithmen dies der einzige ist, der den Namen "schnell" verdient, der nicht beschreibt, wie der Algorithmus funktioniert, sondern wie schnell er (normalerweise) ist. Mergesort wird so genannt, weil es die Daten zusammenführt. Heapsort heißt so, weil es einen Heap verwendet. Introsort hat seinen Namen von "Introspective", da es seine eigene Leistung überwacht, um zu entscheiden, wann von Quicksort zu Heapsort gewechselt werden soll. Ähnliches gilt für alle langsameren - Bubblesort, Einfügesortierung, Auswahlsortierung usw. Sie sind alle nach ihrer Funktionsweise benannt. Die einzige andere Ausnahme, an die ich denken kann, ist "Bogosort", was wirklich nur ein Witz ist, den niemand jemals in der Praxis benutzt. Warum wird Quicksort nicht als beschreibender bezeichnet, wie "Partitionssortierung" oder "Pivot-Sortierung"? welche beschreiben was es eigentlich macht? Es geht nicht einmal darum, "zuerst hier zu sein". Mergesort wurde 15 Jahre vor Quicksort entwickelt. (1945 bzw. 1960 laut Wikipedia)

Ich denke, das ist wirklich eher eine Geschichtsfrage als eine Programmierfrage. Ich bin nur neugierig, wie es zu dem Namen kam - war es nur gutes Marketing?

algorithms naming history sorting Darrel Hoffman
quelle
1
Timsort, das verbesserte Quicksort, hat keinen Namen nach seiner Funktionsweise, sondern nach seinem Erfinder. Namen wie Flashsort oder Introsort sagen auch nicht viel über Algorithmen aus.
Vartec
What's in a name? that which we call a rose By any other name would smell as sweet;Das oder genauso schnell sein. Außerdem hat die Möglichkeit der Degeneration zu O (N ^ 2) eine geringe Wahrscheinlichkeit, und N LogN ist für einen Algorithmus ziemlich gut, obwohl wir heute schnellere Algorithmen haben. Außerdem war es zu spät, als etwas schnelleres auftauchte, alle nannten es bereits Quicksort!
Ampt
1
@vartec Timsort ist eigentlich von Mergesort abgeleitet, nicht von Quicksort, aber ich stimme zu, das ist eine weitere Ausnahme. Introsort gibt Ihnen nicht den gesamten Algorithmus, aber es beschreibt zumindest etwas davon, wie es funktioniert - es ist "introspektiv". Flashsort ist mir nicht sehr vertraut, aber ich denke, es heißt so, weil es jedes Element in seiner besten Vermutung "blitzt", wo es sein sollte?
Darrel Hoffman
1
@Ampt Tatsächlich ist in der einfachsten Form von Quicksort der Fall O (N ^ 2) sehr wahrscheinlich, wenn die Daten bereits oder fast sortiert sind. Zwar machen spätere Entwicklungen wie Median-of-3 oder Random Pivot es weitaus seltener, aber der Name wird immer noch für Implementierungen verwendet, bei denen solche Verbesserungen fehlen.
Darrel Hoffman
Anscheinend ist es besser als am schnellsten?
JeffO

Antworten:

13

1962 war die Forschung zu Sortieralgorithmen nicht so weit fortgeschritten wie heute, und der Informatiker Tony Hoare fand einen neuen Algorithmus, der schneller als der andere war. Deshalb veröffentlichte er einen Artikel namens Quicksort, und als der Artikel zitiert wurde, blieb der Titel erhalten.

Das Abstract zitieren:

Es wird eine neue Methode zum Sortieren im Direktzugriffsspeicher eines Computers beschrieben. Das Verfahren ist im Vergleich zu anderen bekannten Verfahren hinsichtlich Geschwindigkeit, Speicherökonomie und einfacher Programmierung sehr günstig. Bestimmte Verfeinerungen der Methode, die bei der Optimierung innerer Schleifen nützlich sein können, werden im zweiten Teil des Papiers beschrieben.

johannes
quelle
Die Fußnote auf Seite 11 im verknüpften PDF deutet darauf hin, dass 1961 ein früheres Papier über Quicksort veröffentlicht wurde. Dieses Papier wird auch im Abschnitt "Referenzen" am Ende des Papiers erwähnt.
FrustratedWithFormsDesigner
1961, Algorythm 64: Quicksort
Pieter B
Ich denke, das ist so nah an der richtigen Antwort, wie ich sie wahrscheinlich bekommen werde. Es wird erklärt, wer es benannt hat, aber nicht, warum es diesen Namen immer noch verwendet, wenn neuere und möglicherweise schnellere Alternativen existieren. Gute Lektüre - es ist interessant zu sehen, wie viel Zeug aus den 60er Jahren noch für moderne Technologie gilt.
Darrel Hoffman
3
@DarrelHoffman Warum sollte sich der Name ändern? Ab wann überwiegen die Nachteile des Aufrufs des Algorithmus Quicksort die Kosten für den Versuch, alle dazu zu bringen, ihn PartitionSort oder was auch immer zu nennen?
Prosfilaes
0

Ich glaube, dass es ursprünglich nach dem Erfinder Hoare Sort genannt wurde, aber der Name wurde ziemlich früh geändert, da Hoare auf Englisch ein wenig zu nahe an der Hure klang. Ich bin mir nicht sicher, warum sie "schnell" anstelle von etwas anderem gewählt haben.

Evicatos
quelle
-1

Ich glaube, das liegt daran, dass es zu der Zeit, als es erfunden wurde, sehr viel schneller war als alle (oder besser gesagt, die meisten, da die Geschwindigkeit auch stark von der Art der Daten abhängt und in einigen Fällen andere Algorithmen viel schneller als Quicksort werden) Algorithmen da draußen.

Also ja, es ist historisch (ich kenne diese Geschichte jedoch nicht genau ...)

Aber ich stimme zu, dass sein Name stattdessen einen Hinweis auf den Algorithmus enthalten sollte ...

Olivier Dulac
quelle