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
331 visitas
perguntada Fev 4, 2015 em Ciência da Computação por danielcajueiro (5,806 pontos)  
Compartilhe

1 Resposta

+1 voto
respondida Mar 7, 2015 por danielcajueiro (5,806 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.

comentou Dez 4 por Stuart Mill (1,164 pontos)  
Também existe a questão do sort ser estável ou não. O merge sort é estável, o quicksort nem sempre. Acho que por isso ele é o sort padrão do python.
comentou Dez 4 por danielcajueiro (5,806 pontos)  
Merge sort eh o padrao do python? Nao sabia. "Estavel" quer dizer exatamente o que nesse contexto? Pois se vc aleatorizar o pivot na media o custo medio dá O(nlogn).
comentou Dez 5 por Stuart Mill (1,164 pontos)  
Na verdade, eu pesquisei aqui aqui e o sort padrão é uma mistura do merge sort com o insertion sort que um dos criadores do Python criou (Timsort, https://en.wikipedia.org/wiki/Timsort).
Estabilidade nesse contexto eu quero dizer que, por exemplo, que dois objetos ordinalmente iguais sempre vão aparecer ordenados da mesma forma que a entrada é ordenada. Se por exemplo, tenho uma lista [5,2,6,2], o primeiro '2' sempre aparece antes do segundo '2' após o sort.
Pelo que vi, o Quicksort padrão não é estável (embora haja modificações que tornem estável).https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
comentou Dez 5 por danielcajueiro (5,806 pontos)  
Interessante.
...