Arquivo da tag: selection sort

Ordenação por Seleção

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

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 \leftarrow{} 1 até tamanho-1, faça
2.  minimo \leftarrow{} i
3.  para j \leftarrow{} i+1 até tamanho, faça
4.      se vetor[j] < vetor[minimo], então
5.          minimo \leftarrow{} j
6.      fim-se
7.  fim-para
8.  temp \leftarrow{} vetor[i]
9.  vetor[i] \leftarrow{} vetor[minimo]
10. vetor[minimo] \leftarrow{} temp
11. 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=2v[j] = 3 < v[minimo] = v[1] = 5[/latex], portanto [latex]minimo = j = 2[/latex].  <table> <thead> <tr> <td>v[1]</td> <td>v[2]</td> <td>v[3]</td> <td>v[4]</td> <td>v[5]</td> <td>v[6]</td> </tr> </thead> <tr> <td class="preto">5</td> <td class="cinza">3</td> <td>7</td> <td>8</td> <td>2</td> <td>5</td> </tr> </table>  [latex]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[/latex], portanto [latex]minimo = j = 5[/latex].  <table> <thead> <tr> <td>v[1]</td> <td>v[2]</td> <td>v[3]</td> <td>v[4]</td> <td>v[5]</td> <td>v[6]</td> </tr> </thead> <tr> <td class="preto">5</td> <td>3</td> <td>7</td> <td>8</td> <td class="cinza">2</td> <td>5</td> </tr> </table>  [latex]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-1
  3. \sum_{j=1}^{n} + n
  4. \sum_{j=1}^{n}
  5. \sum_{j=1}^{n} ???
  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}) + (0) + (0) + (0) + (n-1) + (n-1) + (n-1) + (0)

T(n) = n^{2} + 6n -3 \Theta{}(n^{2}) = f(n)

Segundo cálculo

T(n) = (n) + (n-1) + (\sum_{j=1}^{n} + n) + (\sum_{j=1}^{n}) + (\sum_{j=1}^{n}) + (0) + (0) + (n-1) + (n-1) + (n-1) + (0)

T(n) = 1,5 n^{2} + 6,5 n - 3 \Theta{}(n^{2}) = f(n)

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.