25

Eu não tenho treinamento em ciência da computação. Por exemplo, sempre que quero ordenar um vetor de números x em uma das linguagens de programação que utilizo, basta rodar sort(x) e tudo se resolve.

Entretanto, as pessoas que conheço que estudaram ciência da computação tiveram que estudar como os algoritmos de ordenação funcionam. Imagino que este seja um assunto importante nesta área do conhecimento, a ponto de existir ao menos um canal no YouTube que publicou vídeos de companhias de danças folclóricas ilustrando como diferentes algoritmos funcionam na prática.

Pegando uma lista pronta da Wikipedia, é possível encontrar 14 algoritmos de ordenação diferentes:

  • Insertion sort
  • Selection sort
  • Bubble sort
  • Comb sort
  • Merge sort
  • Heapsort
  • Shell sort
  • Radix sort
  • Gnome sort
  • Counting sort
  • Bucket sort
  • Cocktail sort
  • Timsort
  • Quick sort

Isto posto, minhas perguntas são:

  1. Existe algum algoritmo de ordenação que seja o melhor de todos, podendo ser utilizado na maioria dos casos e trazendo os melhores resultados? Existe algum estudo neste sentido?

  2. Alguns problemas específicos de ordenação são melhor resolvidos por algum algoritmo em particular? Que exemplos podem ser dados?

  3. Entendo que uma das maneiras de escolher um bom algoritmo é através da sua complexidade, representada por O(f(x)). Mas esta é uma medida teórica, que até onde sei não leva em conta limitações físicas de memória e disco da máquina. Existe alguma medida de complexidade de algoritmos que não leve em conta apenas a quantidade de operações realizadas, mas também a memória utilizada para isso?

  4. Ainda existe pesquisa sendo realizada na área? Por exemplo, é possível que algum destes 14 algoritmos de ordenação que listei acima não seja indicado para trabalhar com grandes volumes de dados? Algo mais avançado já foi ou está sendo desenvolvido?

1 Resposta 1

23

Porque eles resolvem o mesmo problema de maneiras diferentes. Cada um tem um compromisso diferente. Uns usam mais memória, outros são mais lentos dependendo das circunstâncias. Podemos ver esses compromissos na tabela do Big O Cheat Sheet:

Tabela Big O Cheat Sheet

Existe algum algoritmo de ordenação que seja o melhor de todos, podendo ser utilizado na maioria dos casos e trazendo os melhores resultados? Existe algum estudo neste sentido?

Depende. Se prestar atenção ao texto da pergunta cabe interpretação dela. E "melhor" precisaria ser definido. Sem dizer que "melhor" seria esse, qualquer ponto pode ser destacado.

Em termos de performance muitos consideram que seja o Heapsort, que tem resultado excelente em todos os casos e ocupa um mínimo de memória. Mas depende de qual hardware ele está rodando. Em hardware moderno ele não vai tão bem por ter localidade de referência ruim, mas obviamente depende da implementação. E ele não oferece estabilidade.

Muitos consideram que é o Quicksort, afinal é altamente eficiente em memória, próximo do máximo ideal, e tem a melhor performance possível no melhor caso, na média, e embora possa ser ruim no pior, raramente acontece de fato, principalmente em grandes volumes (estou excetuando da análise os algoritmos que possuem restrição do que e como ele classifica os dados). Provavelmente ele é o mais usado por ser fácil implementar.

Há quem prefira o Introsort que combina os dois anteriores. Aliás, é comum as implementações internas reais de boas funções de sort decidirem pelo melhor algoritmo entre um conjunto de pelo menos duas ou três opções.

Para melhor garantia de performance costuma-se adotar o Mergesort, desde que memória não seja um grande problema. Ele é mais fácil de paralelizar, o que pode torná-lo o mais rápido (que é diferente de ser o mais eficiente), se bem implementado para aproveitar este recurso.

Mais recentemente o Timsort vem sendo usado porque é um Mergesort com mais inteligência e pode ter alguns ganhos expressivos em alguns casos, sem comprometer significativamente os demais. Ele é mais complexo e há casos que não haverá ganho.

Não acredito que os demais possam sequer serem considerados para "todos" os casos com um mínimo de eficiência.

Alguns problemas específicos de ordenação são mais bem resolvidos por algum algoritmo em particular? Que exemplos podem ser dados?

Sim, tem diversas situações específicas que um pode se dar melhor que outro, e isso pode variar muitas coisas:

  • a quantidade de memória total disponível para seu uso
  • o cache disponível
  • a quantidade de processadores disponíveis
  • se a classificação não será feita em memória RAM
  • se os dados costumam estar muito embaralhados ou se já devem ter uma certa ordem
  • se precisa de estabilidade ou não
  • se os dados são muito repetidos ou se é garantido que não há repetição
  • ou até se é possível ter alguma pequena margem de erro na classificação final
  • ou se os dados têm um padrão específico que permite classificar sem comparar, o melhor exemplo é o Radix.

Se quiser visualizar melhor a performance em alguns cenários escolhidos tem um site que faz isto (cuidado pode ser um pouco enganoso se você não entender as limitações desta análise). Note lá mostrando que implementação do mesmo algoritmo faz diferença, e faria mais se tivesse outras opções, algumas rodando em paralelo.

Entendo que uma das maneiras de escolher um bom algoritmo é através da sua complexidade, representada por O(f(x)). Mas esta é uma medida teórica, que até onde sei não leva em conta limitações físicas de memória e disco da máquina. Existe alguma medida de complexidade de algoritmos que não leve em conta apenas a quantidade de operações realizadas, mas também a memória utilizada para isso?

Existe, como o AP mesmo mostrou a complexidade é dada por uma função, faça ela complexa o suficiente, considerando todas as variáveis (não pode esquecer de alguma), e terá o que deseja. Em geral "ninguém" faz, porque raramente compensa o esforço, e simular com dados reais deve dar melhores resultados (mais próximos da realidade) com menos trabalho.

Ainda existe pesquisa sendo realizada na área? Por exemplo, é possível que algum destes 14 algoritmos de ordenação que listei acima não seja indicado para trabalhar com grandes volumes de dados? Algo mais avançado já foi ou está sendo desenvolvido?

Sim, totalmente, existem bem mais do que estes, e "cada dia" surge um novo, até que se prova que ele não é melhor que outros ou o é sob circunstância específicas demais, ou são mais complicados que os já existentes sem um ganho expressivo. De forma geral são melhorias nos existentes ou para uso em um nicho de dados.

Concluindo

Selection é uma bomba difícil de ser superada em ineficiência, excetuando o Bogosort.

Lembrando que para pequenos volumes faz pouca diferença o que usar.

Note que usei o termo classificação, ordenação está errado.

Coloquei no GitHub para referência futura.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .