Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Se você fosse perguntado em uma entrevista qual o melhor algoritmo de ordenação, o que você responderia?

+1 voto
109 visitas
perguntada Fev 4, 2015 em Ciência da Computação por danielcajueiro (5,081 pontos)  
Compartilhe

1 Resposta

+1 voto
respondida Mar 7, 2015 por danielcajueiro (5,081 pontos)  
editado Mar 14, 2015 por danielcajueiro

É difícil dar uma resposta geral e única sobre o assunto. De fato, a escolha de um algoritmo de ordenação depende fortemente do contexto. Eu poderia até afirmar que essa é uma pergunta pegadinha.

Considere por exemplo os aspectos:

1) O conjunto de dados possui muitos elementos? Em caso contrário, a pergunta é irrelevante

2) Como são seus dados? Por exemplo, se você deseja apenas ordenar documentos por idade das pessoas, "counting sort" consegue fazer a tarefa com custo linear. Se você estiver lidando com números reais, quick sort funcionará bem em várias situações. É fundamental notar que "counting sort" não pertence a classe dos algoritmos baseados apenas em comparação de elementos dos vetores que devem ser ordenados.

3) A sua memória é grande o suficiente para guardar todos os dados na memória? Em caso contrário, pode ser que você precise dividir os seus dados em partes e trabalhar com mais de um algoritmo.

4) Parte dos seus dados já estão ordenados? Em caso positivo, um algoritmo que pode funcionar bem nesse caso é o "insertion sort". "Insertion sort" é um algoritmo que funciona de forma semelhante a ordenação de cartas de um baralho.

5) Que estrutura de dados está sendo considerada? Embora na maioria dos casos "quick sort" ser mais rápido, heapsort pode ser uma opção interessante, pois se beneficia de ter complexidade no pior caso igual a $O(n\log(n))$.

Detalhes adicionais sobre o assunto podem ser encontrados em Algoritmos - Cormen e Programming Interviews Exposed.

...