Qual é o algoritmo de classificação mais rápido?

Oh, uma pergunta tão fácil de responder.

• O algoritmo de ordenação mais rápido é aquele que explora as peculiaridades dos seus dados no seu hardware, sujeito às suas restrições externas.
• O segundo algoritmo de ordenação mais rápido é o da biblioteca de ordenação suficientemente boa (talvez a da biblioteca padrão da sua linguagem de programação) que você não teve que escrever.

A razão pela qual você passa por todos esses algoritmos de ordenação como um estudante de graduação não é porque você pode simplesmente deixar cair um no seu programa e ele é otimizado para tudo. É para que você pense algorítmicamente.

Eu escrevi bastante código de ordenação no meu tempo, incluindo o subsistema de ordenação para um servidor de banco de dados (que levou seis meses, e envolveu pelo menos seis "algoritmos"). Os sistemas de sort do mundo real de força industrial têm algumas características interessantes que você tende a não ver como uma graduação:

• Os algoritmos básicos de sort que você aprendeu como uma graduação são peças com as quais uma sort "real" é escrita. Você já deve ter visto isso quando lhe foi dito que a ordenação rápida deve usar a ordenação de inserção como seu "caso base".
• Sistemas de ordenação de força industrial vigiam de perto o que está acontecendo e ajustam ou reajustam.
• O algoritmo em si não é freqüentemente a coisa que tem maior efeito sobre a performance, são as restrições sob as quais o algoritmo de ordenação tem que rodar. O acesso a uma chave de ordenação pode ser uma operação cara se envolver uma busca adicional de disco ou pacote de rede ou até mesmo falha de cache. (Exemplo real: Considere a ordenação de documentos XML por título. Para acessar essa chave de ordenação é necessário analisar o XML.)>li>Tudo envolve um tradeoff. Eu quero dizer tudo.

O algoritmo de ordenação incorporado na biblioteca padrão (ou algoritmos) da sua linguagem de programação é frequentemente baseado em comparação, não em radix. Você já parou para se perguntar por quê? Não é por razões de performance bruta, é porque o algoritmo precisa funcionar em tipos definidos pelo usuário, e é muito mais conveniente para o programador fornecer um operador de comparação "menos do que" do que alguma outra consulta. O programador tem um trabalho a fazer e só quer isto ordenado com o mínimo de boilerplate.

Como outro exemplo do mundo real, uma vez eu tive que escrever algum firmware que envolvia a leitura de cerca de 1000 inteiros de um dispositivo de hardware em um buffer e depois executar a extração de quantis. O microcontrolador em que isto funcionava não tinha essencialmente nenhuma memória extra de leitura-escrita disponível, então algoritmos como radix sort ou quicksort não eram uma opção, e o tamanho do conjunto de dados não era grande o suficiente para fazer o heap sort valer a pena. Eu usei Shell sort que era facilmente a melhor opção: subquadratic sem necessidade de memória extra de leitura/gravação.

E como sempre, certifique-se de que o algoritmo de sort é realmente um gargalo antes de ficar extravagante.