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:

para i $\leftarrow{}$ 1 até tamanho-1, faça
 minimo $\leftarrow{}$ i
 para j $\leftarrow{}$ i+1 até tamanho, faça
  se vetor[j] < vetor[minimo], então
   minimo $\leftarrow{}$ j
  fim-se
 fim-para
 temp $\leftarrow{}$ vetor[i]
 vetor[i] $\leftarrow{}$ vetor[minimo]
 vetor[minimo] $\leftarrow{}$ temp
fim-para

tamanho = comprimento do vetor

Funcionamento

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.

Exemplo de Funcionamento

O programa recebe o seguinte vetor.

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
5	3	7	8	2	5

Aí ele começa com $i=1$. Vou sempre marcar $i$ com a cor preta e $min$ com a cor cinza.

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
5	3	7	8	2	5

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 $j=2$ até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.

$j=2$ … $v[j] = 3 < v[minimo] = v[1] = 5$, portanto $minimo = j = 2$.

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
5	3	7	8	2	5

$j=3$ … $v[j] = 3 < v[minimo] = v[1] = 5$, portanto $minimo = j = 2$.

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
5	3	7	8	2	5

$j=3$ … $v[j] = 7 > v[minimo] = v[2] = 3$, portanto não mexemos em nada.

$j=4$ … $v[j] = 8 > v[minimo] = v[2] = 3$, portanto não mexemos em nada.

$j=5$ … $v[j] = 2 < v[minimo] = v[2] = 3$, portanto $minimo = j = 5$.

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
5	3	7	8	2	5

$j=6$ … $v[j] = 2 < v[minimo] = v[2] = 3$, portanto $minimo = j = 5$.

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
5	3	7	8	2	5

$j=6$ … $v[j] = 5 > v[minimo] = v[5] = 2$, portanto não mexemos em nada.

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

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
2	3	7	8	5	5

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

Custo

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. $n$
2. $n$
3. $\sum\_{j=1}^{n} n$
4. $\sum\_{j=1}^{n} 1$
5. $\sum\_{j=1}^{n} 1$
6. $0$
7. $0$
8. $n-1$
9. $n-1$
10. $n-1$
11. $0$

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 $0$ (como se nenhum se entrasse) e depois com ela valendo $\sum\_{j=1}^{n}$.

Primeiro cálculo

$$T(n) = n + (n-1) + (\sum\_{j=1}^n n) + \\ (\sum\\_{j=1}^n 1) \times 2 + 0 \times 3 + (n-1) \times 3 + 0$$ $$T(n) = n^{2} + 6n - 3 = \Theta{}(n^2)$$

Segundo cálculo

$$T(n) = n + (n-1) + (\sum\_{j=1}^n n) + \\ (\sum\\_{j=1}^n 1) \times 3 + 0 \times 2 + (n-1) \times 3 + 0$$ $$T(n) = 1,5 n^{2} + 6,5 n - 3 = \Theta{}(n^2)$$

Conclusão

Como vocês puderam ver, não faz diferença alguma o $\frac{n^{2} + n}{2}$ 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.