Ordenação por Seleção

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=1i=1. Vou sempre marcar ii com a cor preta e minmin 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=2j=2 até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.

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

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

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

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

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

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

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

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

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

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

j=6j=6v[j]=5>v[minimo]=v[5]=2v[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. nn
  2. nn
  3. _j=1nn\sum\_{j=1}^{n} n
  4. _j=1n1\sum\_{j=1}^{n} 1
  5. _j=1n1\sum\_{j=1}^{n} 1
  6. 00
  7. 00
  8. n1n-1
  9. n1n-1
  10. n1n-1
  11. 00

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

Primeiro cálculo

T(n)=n+(n1)+(_j=1nn)+(j=1n1)×2+0×3+(n1)×3+0T(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)=n2+6n3=Θ(n2)T(n) = n^{2} + 6n - 3 = \Theta{}(n^2)

Segundo cálculo

T(n)=n+(n1)+(_j=1nn)+(j=1n1)×3+0×2+(n1)×3+0T(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,5n2+6,5n3=Θ(n2)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 n2+n2\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.

O blog está temporariamente sem comentários. Em breve eles estarão de volta.
© 2005–2020 Tiago Madeira