Algorítmos de Ordenação - Parte II

Como Comparar Algorítmos de Ordenação

Alguns critérios normalmente usados para comparar algorítmos de ordenação são:

• Velocidade de execução
• Necessidade de Memória Adicional
• Estabilidade

Velocidade de Execução

Este é normalmente o critério mais importante. Não se pode, entretanto, esquecer que a velocidade vai depender de vários fatores.

É intuitivo que quanto mais itens temos para ordenar, mais tempo vai demorar. A forma como o tempo aumenta com o aumento dos itens varia conforme o algorítmo.

Considere o sequinte algorítmo simples: examinamos os N itens, um a um, e separamos o primeiro; repetimos o processo para os N-1 intens restantes e assim por diante. A ordenação levará N+(N-1)+(N-2)+...+1 passos. Esta soma resulta em N²/2 passos, daí dizermos que este algorítmo leva um tempo proporcional a N² para ordenar N itens. Veremos nos próximos artigos que um bom algorítmo reduz isto para N*log(N) passos. Na maioria dos casos, quanto melhor o algorítmo, mais complexos serão os passos e portanto eles serão mais demorados. Mesmo assim, para um N grande log(N) é muito menor que N.

Por exemplo, vamos supor que temos um programa que demora N² microsegundos para ordenar N itens e outro que leva 100*N*log(N) microsegundos (em outras palavras, cada passo do segundo programa demora 100 vezes mais que cada passo do primeiro).

Para ordenar 10 itens, o primeiro algorítmo demora 100 microsegundos e o segundo 1000 microsegundos. Ordenando 100 itens, os tempos sobem para 10000 e 20000 microsegundos. Para 1000 itens, o primeiro levará 1000000 de microsegundos (mais de 16 minutos), enquanto que o segundo levará apenas 300000 (5 minutos).

Não é o caso do algorítmos simples apresentado acima, mas o tempo para os algorítmos mais sofisticados vai depender dos dados serem ordenados. Isto nos obriga a falar em tempo médio e em tempo do pior caso. Por exemplo, veremos que o Quicksort possui um tempo médio proporcional a N*log(N) e um tempo do pior caso proporcional a N². Isto significa, que o Quicksort é normalmente muito rápido, porém às vezes é muito lento!

A velocidade depende também das características do computador. A ordenação envolve principalmente comparar e mover chaves. Computadores diferentes podem levar tempos relativos diferentes para estas duas operações. Por exemplo, suponha que as chaves sejam valores em ponto flutuante. Pode existir uma grande diferença nas velocidades de comparação entre um computador com unidade de ponto flutuante e um computador que necessite fazer uma chamada de biblioteca. Neste segundo computador pode fazer sentido minimizar as comparações, mesmo que isto signifique mais movimentações. O resumo da história é que um algorítmo que funcione bem num computador pode não se dar tão bem em outro.

Necessidade de Memória Adicional

Alguns algorítmos são capazes de ordenar os dados nas posições em que eles estão armazenados, usando memória adicional apenas para trocar de posição duas chaves. Outros necessitam de memória adicional proporcional ao tamanho dos dados sendo ordenados. Os algorítmos descritos nesta série necesitam de nenhuma ou muito pouca memória adicional.

Estabilidade

Dizemos que um algorítmo é estável se ele manter chaves iguais na mesma ordem em que elas estão na entrada. Dizendo de outra maneira, se nós aplicarmos o algorítmo a dados já ordenados, a saída será idêntica à entrada. É sempre possível converter um algorítmo instável em um estável usando a posição original da chave como o último critério de ordenação. Por exemplo, se estamos usando ponteiros para ordenar as chaves, comparamos os ponteiros se as chaves são iguais.

No próximo artigo da série vamos ver os primeiros algorítmos de ordenação.