El objetivo de esta pregunta no es debatir los méritos de esto sobre ningún otro algoritmo de clasificación; ciertamente, hay muchas otras preguntas que hacen esto. Esta pregunta es sobre el nombre. ¿Por qué Quicksort se llama "Quicksort"? Claro, es "rápido", la mayoría de las veces, pero no siempre. La posibilidad de degenerar a O (N ^ 2) es bien conocida. Hay varias modificaciones a Quicksort que mitigan este problema, pero las que reducen el peor de los casos a un O garantizado (n log n) generalmente ya no se llaman Quicksort. (por ejemplo, Introsort).
Me pregunto por qué de todos los algoritmos de clasificación conocidos, este es el único que merece el nombre "rápido", que describe no cómo funciona el algoritmo, sino qué tan rápido es (generalmente). Mergesort se llama así porque combina los datos. Se llama así a Heapsort porque usa un montón. Introsort recibe su nombre de "Introspectivo", ya que supervisa su propio rendimiento para decidir cuándo cambiar de Quicksort a Heapsort. Del mismo modo para todos los más lentos: Bubblesort, Insertion sort, Selection sort, etc. Todos se nombran por su funcionamiento. La única otra excepción que se me ocurre es "Bogosort", que es realmente una broma que nadie usa en la práctica. ¿Por qué Quicksort no se llama algo más descriptivo, como "Partition sort" o "Pivot sort", que describen lo que realmente hace? Ni siquiera es un caso de "llegué primero". Mergesort se desarrolló 15 años antes de Quicksort. (1945 y 1960 respectivamente según Wikipedia)
Supongo que esto es realmente más una pregunta de historia que una de programación. Tengo curiosidad por saber cómo obtuvo el nombre, ¿fue solo un buen marketing?
fuente
What's in a name? that which we call a rose By any other name would smell as sweet;Eso o ser igual de rápido. Además, la posibilidad de degenerar a O (N ^ 2) tiene una pequeña posibilidad de suceder, y N LogN es bastante bueno para un algoritmo, a pesar de que hoy tenemos algoritmos más rápidos. Además, para cuando surgió algo más rápido, ya era demasiado tarde, ¡todos ya lo llamaban Quicksort!Respuestas:
En 1962, la investigación sobre algoritmos de clasificación no estaba tan avanzada como hoy y el científico informático Tony Hoare encontró un nuevo algoritmo que era más rápido que el otro, por lo que publicó un artículo llamado Quicksort y, mientras se citaba, el título permaneció.
Citando el resumen:
fuente
Creo que originalmente se llamaba Hoare Sort por el inventor, pero el nombre cambió bastante temprano debido a que Hoare sonaba un poco demasiado cerca de la puta en inglés. En cuanto a por qué eligieron "rápido" en lugar de otra cosa, no estoy seguro.
fuente
Creo que es porque, en el momento en que se inventó, era mucho más rápido que todos (o, más bien, la mayoría, ya que la velocidad también depende en gran medida del tipo de datos y, en algunos casos, otro algoritmo se vuelve mucho más rápido que el de clasificación rápida) algoritmos por ahí.
Entonces sí, es histórico (no sé exactamente esa historia, sin embargo ...)
Pero estoy de acuerdo en que su nombre debería contener una pista del algoritmo ...
fuente