Quicksort e não se incomoda?

Especialmente ao escrever aplicativos 'padrão' (não HPC), você considera qual algoritmo de classificação escolher ou apenas aceita o quicksort (que é o que a maioria das bibliotecas chama apenas de classificação)? Até certo ponto, pode ser rentável em situações específicas, mas, por outro lado, a otimização adequada requer algum tempo para analisar o problema e fazer benchmarks.

Em geral, o uso dos métodos padrão, a menos que haja uma necessidade específica de fazer algo mais exótico, mantém tudo muito mais legível / compreensível no caminho IMHO.

Se você tiver (ou em alguns casos, suspeitar fortemente) que possui um problema de desempenho, é hora de adicionar complexidade.

Por outro lado, se você estiver usando uma linguagem baixa o suficiente para não haver uma classificação interna para o tipo de objetos que você precisa, tente escolher uma ou duas que cubram todas as suas bases e as implemente.

Sempre chame as rotinas da biblioteca fornecidas, a menos que você tenha um motivo muito, muito bom para não fazer isso (e você precisa documentar o motivo).

Isso ocorre porque é difícil obter algoritmos de classificação absolutamente certos. Houve um erro no quicksort Java com conjuntos de dados muito grandes, que foram identificados, corrigidos e entregues aos clientes pela Sun, portanto você não precisava.

Além disso, a classificação padrão no Java 7 foi atualizada para uma classificação mais nova e melhor. Também de graça.

A menos que o padrão de classificação é comprovadamente não é bom o suficiente para você, ficar com ela.

Em uma conferência, ouvi uma boa história sobre isso.

Na Microsoft, alguém estava escrevendo um aplicativo VB (c. VB 3) e mandou um e-mail para várias pessoas dizendo que ele tinha muitos valores e que ele queria que eles aparecessem na caixa de combinação em ordem, como ele deveria fazer isso.

Todos mergulharam em busca de seus velhos livros de ciência da computação, procurando rotinas altamente eficientes e portando-os para o Visual Basic e enviando-os por correio para ele. Um cara acabou de enviar de volta "quantos valores na caixa de combinação?".

"Cerca de 50" veio a resposta.

"Basta definir a propriedade classificada como TRUE".

Em 99.9999% das instâncias, a classificação é melhor feita usando uma biblioteca, controle ou SQL selecionado, pois a diferença de desempenho entre a rotina da biblioteca e qualquer coisa que você escrever será desprezível e o esforço e a sobrecarga de manutenção compensarão enormemente as conseqüências.

Este é o momento de retirar a citação clássica sobre otimização prematura. Na maioria dos casos, isso realmente não importa. Heck, com a velocidade das CPUs hoje em dia, você provavelmente poderia classificar a maioria dos conjuntos de dados com bolha e nem perceber muito. Mas quando você está classificando conjuntos de dados realmente grandes e o desempenho da classificação começa a se tornar um problema, você definitivamente deve procurar outras opções.

Embora isso obviamente não importe para os bits e os horários. Acho que a classificação por mesclagem é mais fácil de escrever e entender do que o quicksort. Então, se eu vou escrever meu próprio algoritmo de classificação, eu o usaria.

Pelo menos em uma biblioteca escrita com competência, eu esperaria que o built-in sortfosse implementado como um Introsort em vez de apenas um Quicksort. A diferença raramente importa muito, mas o Introsort elimina o pior desempenho do Quicksort com um efeito mínimo nos casos mais comuns.

Para responder à sua pergunta, no entanto: sim - é com isso que você normalmente deve começar e até / a menos que tenha resultados de criação de perfil indicando que é um problema, é onde deve permanecer.