Skip to main content
2 de 5
adicionou 1418 caracteres ao conteúdo
Maniero
  • 484,4mil
  • 94
  • 1,3mil
  • 2,2mil

Na verdade pode-se dizer que são os mesmos tanto para uso externo quanto interno. É provável que algum algoritmo seja um pouco melhor em um caso do que outros algoritmos. Não vou analisar um por um para chegar nessa conclusão.

A escolha do algoritmo mais adequado depende de uma série de fatores. Costuma-se dizer que o Quicksort é o mais adequado para o caso geral. O que não quer dizer que ele seja o melhor sempre. Ele foi criado para uso em memória RAM. Mas nada impede que seja usado em armazenamento secundário.

Quando vai para o armazenamento secundário é de extrema importância acessar o disco o mínimo de vezes possível. Então em tese precisaria achar um algoritmo que minimize isso, mesmo que tenha outros custos mais altos.

Porém isso é uma ingenuidade. Na prática todo algoritmo de ordenação que precise de muita performance combinará técnicas diferentes para atingir o objetivo. É óbvio que uma dessas técnicas é colocar o máximo de dados possível em memória e ordenar o que dá ali e ir organizando todas as porções. Se conseguir colocar tudo que está na memória secundária para a primária, o melhor algoritmo para aquele caso funcionará bem na memória. Se não puder colocar tudo, precisa gerenciar a carga da forma mais inteligente possível. Isso tem pouco a ver com o algoritmo de sort em si.

Note que a quantidade de memória que os computadores tem hoje e o advento do SSD melhorou bastante a condição de um algoritmo não tão otimizado conseguir bons resultados. Se tiver vários processadores a escolha pode tender mais para um algoritmo específico. De fato o hardware adequado fará muita diferença, provavelmente mais que o algoritmo mais adequado, desde que não use um muito ruim para qualquer caso.

Pode-se fazer isso transparentemente. Pode-se usar um memory mapped file e fazer na memória tudo o que se espera fazer em arquivo. O sistema operacional gerencia o que deve estar na memória e o que precisa fica em disco. Desta forma pode se concentrar no algoritmo e o gerenciamento da memória fica por conta do sistema operacional. Ler e grava é algo que teria que fazer mesmo. Claro que será muito eficiente se couber tudo na memória ou os dados permitirem poucas trocas de página. Claro que essa facilidade por ter um custo, com o algoritmo certo pode controlar melhor como quer fazer a paginação, ou pode fazer muito pior que o sistema operacional faria. MMF é mais usado em computação do que imagina. Todos seus executáveis são carregados na memória assim. Toda memória virtual funciona assim. De fato qualquer alocação de memória, de uma forma ou de outra acaba chamando um MMF.

Se realmente o hardware for muito restrito me lembro que o MergeSort costuma ser bom em casos assim. Andei pesquisando e parece que o BucketSort é melhor ainda, e tem algumas variantes que podem ajudar melhor cada caso. Tem um estudo que parece confirmar isso.

Maniero
  • 484,4mil
  • 94
  • 1,3mil
  • 2,2mil