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-paratamanho = 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] |
| 5 |
Aí ele começa com i=1. Vou sempre marcar \(i\) com a cor preta e \(min\) com a cor cinza.
| v[1] |
| 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] |
| 2 |
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
- n
- n
- \sum_{j=1}^{n} n
- \sum_{j=1}^{n} 1
- \sum_{j=1}^{n} 1
- 0
- 0
- n-1
- n-1
- n-1
- 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.