Pourquoi Quicksort est-il appelé «Quicksort»?

9

Le but de cette question n'est pas de débattre du bien-fondé de cela sur tout autre algorithme de tri - il y a certainement beaucoup d'autres questions qui le font. Cette question concerne le nom. Pourquoi Quicksort est-il appelé "Quicksort"? Bien sûr, c'est "rapide", la plupart du temps, mais pas toujours. La possibilité de dégénérer en O (N ^ 2) est bien connue. Il existe diverses modifications à Quicksort qui atténuent ce problème, mais celles qui ramènent le pire des cas à un O garanti (n log n) ne sont généralement plus appelées Quicksort. (par exemple, Introsort).

Je me demande simplement pourquoi de tous les algorithmes de tri bien connus, c'est le seul qui mérite le nom "rapide", qui décrit non pas comment l'algorithme fonctionne, mais à quelle vitesse (généralement) il est. Mergesort est appelé ainsi car il fusionne les données. Heapsort est appelé ainsi car il utilise un tas. Introsort tire son nom de "Introspective", car il surveille ses propres performances pour décider quand passer de Quicksort à Heapsort. De même pour tous les plus lents - Bubblesort, tri par insertion, tri par sélection, etc. Ils sont tous nommés pour leur fonctionnement. La seule autre exception à laquelle je peux penser est "Bogosort", qui n'est vraiment qu'une blague que personne n'utilise jamais dans la pratique. Pourquoi Quicksort n'est-il pas appelé quelque chose de plus descriptif, comme "Tri par partition" ou "Tri par pivot", qui décrivent ce qu'il fait réellement? Ce n'est même pas un cas de "arrivé ici en premier". Mergesort a été développé 15 ans avant Quicksort. (1945 et 1960 respectivement selon Wikipedia)

Je suppose que c'est vraiment plus une question d'histoire qu'une question de programmation. Je suis simplement curieux de savoir comment il a obtenu ce nom - était-ce juste un bon marketing?

algorithms naming history sorting Darrel Hoffman
la source
1
Timsort, qui est un quicksort amélioré, ne tient pas son nom de son fonctionnement, mais plutôt de son inventeur. Des noms comme flashsort ou introsort ne vous disent pas grand- chose non plus sur l'algorithme.
vartec
What's in a name? that which we call a rose By any other name would smell as sweet;Cela ou soyez tout aussi rapide. En outre, la possibilité de dégénérer en O (N ^ 2) a une petite chance de se produire, et N LogN est assez bon pour un algorithme, malgré le fait que nous ayons aujourd'hui des algorithmes plus rapides. D'ailleurs, au moment où quelque chose de plus rapide est arrivé, il était trop tard, tout le monde l'appelait déjà Quicksort!
Ampt
1
@vartec Timsort est en fait dérivé de Mergesort, pas de Quicksort, mais je suis d'accord, c'est une autre exception. Introsort ne vous donne pas l'intégralité de l'algorithme, mais il décrit au moins quelque chose sur son fonctionnement - c'est "introspectif". Flashsort que je ne connais pas très bien, mais je suppose que cela s'appelle ainsi parce qu'il "clignote" chaque élément dans sa meilleure estimation de l'endroit où il devrait être?
Darrel Hoffman
1
@Ampt En fait, sous la forme la plus simple de Quicksort, le cas O (N ^ 2) est très probable dans le cas courant où les données sont déjà triées ou presque. Certes, des développements ultérieurs tels que la médiane de 3 ou le pivot aléatoire le rendent beaucoup plus rare, mais le nom est toujours utilisé pour les implémentations qui manquent de telles améliorations.
Darrel Hoffman
Apparemment, c'est mieux que Quickest?
JeffO

Réponses:

13

En 1962, la recherche sur les algorithmes de tri n'était pas aussi avancée qu'aujourd'hui et l'informaticien Tony Hoare a trouvé un nouvel algorithme qui était plus rapide que l'autre.Il a donc publié un article intitulé Quicksort et, tel que cité, le titre est resté.

Citant le résumé:

Une nouvelle méthode de tri est décrite dans le magasin à accès aléatoire d'un ordinateur. La méthode se compare très favorablement à d'autres méthodes connues en termes de vitesse, d'économie de stockage et de facilité de programmation. Certaines améliorations de la méthode, qui peuvent être utiles dans l'optimisation des boucles internes, sont décrites dans la deuxième partie de l'article.

johannes
la source
La note de bas de page à la page 11 du PDF lié suggère qu'il y avait un document antérieur sur Quicksort publié en 1961. Ce document est également mentionné dans la section Références à la fin du document.
FrustratedWithFormsDesigner
1961, Algorythm 64: Quicksort
Pieter B
Je suppose que c'est aussi proche de la bonne réponse que je suis susceptible d'obtenir. Il explique qui l'a nommé, mais pas pourquoi il utilise toujours ce nom, alors qu'il existe des alternatives plus récentes et potentiellement plus rapides. Bonne lecture - il est intéressant de voir combien de choses datant des années 60 s'appliquent toujours à la technologie moderne.
Darrel Hoffman
3
@DarrelHoffman Pourquoi le nom changerait-il? À quel moment les inconvénients d'appeler l'algorithme Quicksort l'emporteraient-ils sur le coût d'essayer d'amener tout le monde à l'appeler PartitionSort ou autre?
prosfilaes
0

Je crois qu'il s'appelait à l'origine Hoare Sort après l'inventeur, mais le nom a changé assez tôt en raison du son un peu trop proche de la pute en anglais. Quant à savoir pourquoi ils ont choisi "rapide" au lieu de quelque chose d'autre, je ne suis pas sûr.

Evicatos
la source
-1

Je pense que c'est parce que, au moment où il a été inventé, il était beaucoup plus rapide que tous (ou, plutôt, la plupart, car la vitesse dépend également fortement du type de données et dans certains cas, d'autres algorithmes deviennent beaucoup plus rapides que quicksort) du algorithmes là-bas.

Alors oui, c'est historique (je ne connais pas précisément cette histoire, cependant ...)

Mais je suis d'accord que son nom devrait plutôt contenir un indice de l'algorithme ...

Olivier Dulac
la source