¿Por qué ‘quicksort’ se llama ‘quicksort’?

Answer 1

Otras personas no le dieron este nombre después de leer el algoritmo (no sé por qué, siento que lo tomaste así. Podría deberse al uso de la palabra “llamado”).

El propio CA R Hoare lo nombró tipo rápido cuando publicó el artículo.
Aquí hay un enlace a ese documento. http: //comjnl.oxfordjournals.org…

Esta es una cita de wikipedia

Cuando se implementa bien, puede ser aproximadamente dos o tres veces más rápido que sus competidores principales, fusionar ordenación y ordenamiento.

Así que tenía sentido nombrarlo de forma rápida.

Ahora hagamos que sea más una respuesta de programación en lugar de una historia.
1. Al seleccionar la mediana como pivote se obtiene performance (nlogn) en el peor de los casos.
2. La ordenación rápida aleatoria también proporciona rendimiento Θ (nlogn) casi todo el tiempo. El comportamiento del algoritmo solo depende del generador de números aleatorios. Incluso intencionalmente, no podemos producir una entrada incorrecta para RANDOMIZED_QUICKSORT a menos que podamos predecir que el generador producirá a continuación.

Lo siento, no puedo ver la perspectiva de marketing.

Answer 2

Respuesta corta, es de clasificación rápida porque es de clasificación rápida.

Respuesta larga. Existen muchos métodos de clasificación, algunos de ellos asintóticamente más rápidos que los demás. Se sabe que la clasificación por fusión es el algoritmo más rápido que no asume una estructura especial sobre los elementos, pero que la clasificación rápida se denomina clasificación “rápida”.

La razón es que, aunque puede ser asintóticamente lento, funciona muy rápido en la mayoría de los casos prácticos. Incluso hay una versión que dice [math] O (nlog (n)) [/ math] complejidad de caso promedio. No necesita mucha memoria extra, es decir, se puede implementar en el lugar sin sobrecargas de tiempo. No utilizar memoria adicional es una excelente manera de ahorrar tiempo en la práctica, ya que la asignación de memoria, etc., también genera gastos generales.