Algoritmos III

Hoje vou apresentar mais um algoritmo de ordenação de vetores. É a Ordenação por Seleção (ou Selection Sort). Sem mais papo e antes mesmo da explicação, vamos ao seu pseudocódigo:

1. para i 1 até tamanho-1, faça

2. minimo i

3. para j i+1 até tamanho, faça

4. se vetor[j] < vetor[minimo], então

5. minimo j

6. fim-se

7. fim-para

8. temp vetor[i]

9. vetor[i] vetor[minimo]

10. vetor[minimo] temp

11. fim-para

tamanho = comprimento do vetor

A idéia é sempre procurar o menor elemento do vetor e inseri-lo no início do vetor. Procuramos o menor valor do vetor e colocamos ele em vetor[1]. Procuramos o menor valor do vetor excluindo o já colocado e colocamos ele em vetor[2]. E assim vamos indo até termos todo o vetor ordenado.

Partindo sempre a partir do último elemento reordenado (a partir do i), o programa procura o menor elemento no vetor e o substitue pelo elemento i atual.

O programa recebe o seguinte vetor.

Aí ele começa com . Vou sempre marcar com a cor preta e com a cor cinza.

Ele marca o próprio índice i como a variável minimo, que é sempre o menor elemento do vetor. Então, ele faz um para de até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.

... , portanto .

... , portanto não mexemos em nada.

... , portanto não mexemos em nada.

... , portanto .

... , portanto não mexemos em nada.

Agora substituímos o v[minimo] pelo v[i], formando com isto o novo vetor:

E assim vamos fazendo com os outros elementos até que todo o vetor esteja ordenado.

Este algoritmo não tem um melhor/pior caso, porque todos os elementos são varridos, sempre. Medir seu custo é simples. Custo de linha por linha...

n = tamanho do vetor

1. 
2. 
3. 
4. 
5. ???
6. 
7. 
8. 
9. 
10. 
11. 

Você pode estar se perguntando porque eu coloquei este custo para a linha 5. Afinal, a linha 5 diria que este programa tem um melhor/pior caso, porque ela não seria executada se o se retornar falso. Mas o caso é que ela é desprezível. Uma soma como estas para o custo geral do nosso algoritmo não vai influenciar em nada. Quer ver? Vamos somar os custos com esta linha valendo (como se nenhum se entrasse) e depois com ela valendo .

Como vocês puderam ver, não faz diferença alguma o que aquela somatória nos proporciona. Já que todo o cálculo de algoritmos é baseado apenas no maior expoente de n e desprezamos todas as constantes (inclusive as que multiplicam o n de maior expoente, muitos passos são desprezíveis.