Por que o Quicksort é chamado de "Quicksort"?

9

O objetivo desta pergunta não é debater os méritos disso sobre qualquer outro algoritmo de classificação - certamente existem muitas outras perguntas que fazem isso. Esta pergunta é sobre o nome. Por que o Quicksort é chamado de "Quicksort"? Claro, é "rápido", na maioria das vezes, mas nem sempre. A possibilidade de degenerar para O (N ^ 2) é bem conhecida. Existem várias modificações no Quicksort que atenuam esse problema, mas aquelas que reduzem o pior caso a um O garantido (n log n) geralmente não são mais chamadas de Quicksort. (por exemplo, Introsort).

Eu só me pergunto por que, de todos os algoritmos de classificação conhecidos, este é o único que merece o nome "quick", que descreve não como o algoritmo funciona, mas quão rápido (geralmente) é. Mergesort é chamado assim porque mescla os dados. Heapsort é chamado assim porque usa uma pilha. O Introsort recebe o nome de "Introspective", pois monitora seu próprio desempenho para decidir quando mudar do Quicksort para o Heapsort. Da mesma forma para todos os mais lentos - Bubblesort, tipo de inserção, tipo de seleção etc. Eles são todos nomeados pelo modo como funcionam. A única outra exceção em que consigo pensar é "Bogosort", que é realmente apenas uma piada que ninguém realmente usa na prática. Por que o Quicksort não é chamado de algo mais descritivo, como "Classificação de partição" ou "Classificação dinâmica", que descrevem o que realmente faz? Nem sequer é um caso de "cheguei aqui primeiro". O Mergesort foi desenvolvido 15 anos antes do Quicksort. (1945 e 1960, respectivamente, de acordo com a Wikipedia)

Eu acho que isso é realmente mais uma questão de história do que de programação. Só estou curioso para saber como recebeu esse nome - foi apenas um bom marketing?

algorithms naming history sorting Darrel Hoffman
fonte
11
O Timsort, que é um quicksort aprimorado, não leva o nome depois de como ele funciona, mas sim o inventor. Nomes como flashsort ou introsort também não informam muito sobre algoritmo.
vartec
What's in a name? that which we call a rose By any other name would smell as sweet;Isso ou seja tão rápido. Além disso, a possibilidade de degenerar para O (N ^ 2) tem uma pequena chance de acontecer, e N LogN é muito bom para um algoritmo, apesar do fato de termos hoje algoritmos mais rápidos. Além disso, quando algo mais rápido surgiu, era tarde demais, todo mundo já chamava de Quicksort!
Ampt
11
@vartec Timsort é realmente derivado do Mergesort, não do Quicksort, mas eu concordo, essa é outra exceção. O Introsort não fornece todo o algoritmo, mas pelo menos descreve algo de como ele funciona - é "introspectivo". Flashsort com quem eu não estou muito familiarizado, mas acho que é chamado assim porque "pisca" cada elemento no seu melhor palpite de onde deveria estar?
Darrel Hoffman
11
@Ampt Na verdade, na forma mais básica do Quicksort, o caso O (N ^ 2) é bastante provável no caso comum em que os dados já estão classificados ou quase. É certo que desenvolvimentos posteriores, como Mediana de 3 ou pivô aleatório, tornam muito mais raro, mas o nome ainda é usado para implementações que carecem de tais melhorias.
Darrel Hoffman
Aparentemente, é melhor que o Quickest?
Jeffo

Respostas:

13

Em 1962, a pesquisa sobre algoritmos de classificação não estava tão avançada quanto hoje e o cientista da computação Tony Hoare encontrou um novo algoritmo que era mais rápido que o outro, então ele publicou um artigo chamado Quicksort e, como o artigo foi citado, o título permaneceu.

Citando o resumo:

É fornecida uma descrição de um novo método de classificação no armazenamento de acesso aleatório de um computador. O método se compara muito favoravelmente com outros métodos conhecidos em velocidade, economia de armazenamento e facilidade de programação. Certos refinamentos do método, que podem ser úteis na otimização de loops internos, são descritos na segunda parte do artigo.

johannes
fonte
A nota de rodapé na página 11 no PDF vinculado sugere que havia um artigo anterior sobre o Quicksort publicado em 1961. Esse artigo também é mencionado na seção Referências, no final do artigo.
FrustratedWithFormsDesigner
1961, Algorythm 64: Quicksort
Pieter B
Acho que essa é a resposta mais próxima da correta. Ele explica quem o nomeou, mas não por que ele ainda está usando esse nome, quando existem alternativas mais recentes e potencialmente mais rápidas. Boa leitura - é interessante ver quanta coisa dos anos 60 ainda se aplica à tecnologia moderna.
Darrel Hoffman
3
@DarrelHoffman Por que o nome mudaria? Em que momento as desvantagens de chamar o algoritmo Quicksort superam o custo de tentar fazer com que todos o chamem de PartitionSort ou o que seja?
Prosfilaes
0

Acredito que ele foi originalmente chamado Hoare Sort em homenagem ao inventor, mas o nome mudou bastante cedo devido a Hoare parecer um pouco parecido com a prostituta em inglês. Quanto ao motivo pelo qual eles escolheram "rápido" em vez de outra coisa, não tenho certeza.

Evicatos
fonte
-1

Acredito que é porque, no momento em que foi inventado, era muito mais rápido que todos (ou melhor, a maioria, pois a velocidade também depende muito do tipo de dados e, em alguns casos, outro algoritmo se torna muito mais rápido que o quicksort) do algoritmos por aí.

Então, sim, é histórico (no entanto, eu não conheço exatamente essa história ...)

Mas eu concordo que seu nome deve conter uma dica do algoritmo ...

Olivier Dulac
fonte