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:

1. para i [tex]\leftarrow{}[/tex] 1 até tamanho-1, faça
2.	minimo [tex]\leftarrow{}[/tex] i
3.	para j [tex]\leftarrow{}[/tex] i+1 até tamanho, faça
4.		se vetor[j] < vetor[minimo], então
5.			minimo [tex]\leftarrow{}[/tex] j
6.		fim-se
7.	fim-para
8.	temp [tex]\leftarrow{}[/tex] vetor[i]
9.	vetor[i] [tex]\leftarrow{}[/tex] vetor[minimo]
10.	vetor[minimo] [tex]\leftarrow{}[/tex] 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 [tex]i=1[/tex]. Vou sempre marcar [tex]i[/tex] com a cor preta e [tex]min[/tex] 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 [tex]j=2[/tex] até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.

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

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

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

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

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

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

[tex]j=6[/tex] … [tex]v[j] = 5 > v[minimo] = v[5] = 2[/tex], 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. [tex]n[/tex]
  2. [tex]n-1[/tex]
  3. [tex]\sum_{j=1}^{n} + n[/tex]
  4. [tex]\sum_{j=1}^{n}[/tex]
  5. [tex]\sum_{j=1}^{n}[/tex] ???
  6. [tex]0[/tex]
  7. [tex]0[/tex]
  8. [tex]n-1[/tex]
  9. [tex]n-1[/tex]
  10. [tex]n-1[/tex]
  11. [tex]0[/tex]

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 [tex]0[/tex] (como se nenhum se entrasse) e depois com ela valendo [tex]\sum_{j=1}^{n}[/tex].

Primeiro cálculo

[tex]T(n)[/tex] [tex]=[/tex] [tex](n)[/tex] [tex]+[/tex] [tex](n-1)[/tex] [tex]+[/tex] [tex](\sum_{j=1}^{n} + n)[/tex] [tex]+[/tex] [tex](\sum_{j=1}^{n})[/tex] [tex]+[/tex] [tex](0)[/tex] [tex]+[/tex] [tex](0)[/tex] [tex]+[/tex] [tex](0)[/tex] [tex]+[/tex] [tex](n-1)[/tex] [tex]+[/tex] [tex](n-1)[/tex] [tex]+[/tex] [tex](n-1)[/tex] [tex]+[/tex] [tex](0)[/tex]

[tex]T(n) = n^{2} + 6n -3[/tex]

[tex]\Theta{}(n^{2}) = f(n)[/tex]

Segundo cálculo

[tex]T(n)[/tex] [tex]=[/tex] [tex](n)[/tex] [tex]+[/tex] [tex](n-1)[/tex] [tex]+[/tex] [tex](\sum_{j=1}^{n} + n)[/tex] [tex]+[/tex] [tex](\sum_{j=1}^{n})[/tex] [tex]+[/tex] [tex](\sum_{j=1}^{n})[/tex] [tex]+[/tex] [tex](0)[/tex] [tex]+[/tex] [tex](0)[/tex] [tex]+[/tex] [tex](n-1)[/tex] [tex]+[/tex] [tex](n-1)[/tex] [tex]+[/tex] [tex](n-1)[/tex] [tex]+[/tex] [tex](0)[/tex]

[tex]T(n) = 1,5 n^{2} + 6,5 n – 3[/tex]

[tex]\Theta{}(n^{2}) = f(n)[/tex]

Conclusão

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

Ordenação por Inserção

Também conhecida como Insertion Sort, a Ordenação por Inserção consiste em inserir um elemento [tex]n[/tex] num vetor já ordenado de [tex]n-1[/tex] elementos. Neste artigo, apresento-lhes este simples algoritmo para ordenação de vetores.

O pseudocódigo da ordenação por inserção é o seguinte:

1. para j [tex]\leftarrow{}[/tex] 2 até comprimento do vetor, faça
2.	elemento [tex]\leftarrow{}[/tex] vetor[j]
3.	i [tex]\leftarrow{}[/tex] j - 1
4.	enquanto i > 0 e vetor[i] > elemento, faça
5.		vetor[i + 1] [tex]\leftarrow{}[/tex] vetor[i]
6.		i [tex]\leftarrow{}[/tex] i - 1
7.	fim-enquanto
8.	vetor[i + 1] [tex]\leftarrow{}[/tex] elemento
9. fim-para

Para explicar eu vou fazer uma coisa que sempre faço para corrigir meus algoritmos, fingir que sou o programa, executando cada passo manualmente (claro que geralmente faço mais rápido, porque não preciso escrever tudo que faço). Vamos iniciar com o seguinte vetor v.

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

Aí o código me manda começar com [tex]j=2[/tex] e iterar até o comprimento do vetor (6). A primeira ordem que ele me dá é para armazenar o elemento [tex]a[j][/tex] ([tex]a[2][/tex]) na variável elemento. Para facilitar toda a explicação eu vou sempre pintar de cinza o [tex]v[j][/tex] onde eu estou (no caso, o segundo elemento do vetor, 3) e de preto o vetor ainda não ordenado (elementos [tex]\geq{}j[/tex]).

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

Então ele me diz que [tex]i \leftarrow{} j-1[/tex]. Portanto, [tex]i=1[/tex]. E agora ele me faz um enquanto (que poderia ser substituído por para) onde meu i deverá ir diminuindo. Vamos entrar no loop…

Bom, meu [tex]i =1[/tex] é maior que 0. [tex]v[1]=5[/tex] é maior que o [tex]elemento=3[/tex]? Sim, então vamos entrar no corpo do enquanto… Aqui ele me manda fazer um [tex]vetor[i+1] = vetor[i][/tex], que nesse caso é fazer um [tex]v[2]=v[1]=5[/tex].

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

E agora subtrae de i um valor. Portanto, [tex]i=0[/tex]. Ele retorna ao enquanto, mas agora não satisfazemos a condição [tex]i>0[/tex], por isso saímos do enquanto. Então ele pede para [tex]vetor[i+1]=elemento[/tex] ([tex]v[1]=elemento[/tex]). Portanto, o vetor fica assim:

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

E incrementamos o j, agora [tex]j=3[/tex].

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

[tex]elemento = 7[/tex]

[tex]i = 3-1 = 2[/tex]

[tex]i > 0[/tex] … E [tex]5 > 7[/tex]? Não! Portanto, não entramos no enquanto.

[tex]v[3] = elemento[/tex] (nenhuma mudança)

E lá vamos para [tex]j=4[/tex] e continuando até que vamos ter o vetor ordenado:

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

Qual a lógica?

Como eu já disse na introdução, mas lá sem grandes explicações, a Ordenação por Inserção divide o vetor em dois. O primeiro (de elementos [tex]inseridos no primeiro vetor já ordenado (por isso ele se chama Algoritmo de Inserção).

A chave do algoritmo é o enquanto que acontece para ir deslocando todos os elementos para seu índice [tex]+1[/tex] enquanto o elemento for menor que eles (para depois o elemento ser colocado onde parou).

A variável elemento só serve para não perdermos o valor de [tex]v[j][/tex] (porque depois fazemos [tex]v[i+1]=v[i][/tex] quando [tex]i=j-1[/tex])

Acredito que não tenham restado dúvidas. Dê mais uma olhada no algoritmo e tente implementar. Se tiver dificulade, coloque mensagens de debug estratégicas para entender o algoritmo. (ex.: no início do para coloque para imprimir o valor de j e no início de cada enquanto coloque para imprimir os valores elemento, i e v[i])

Custo

Você deve ter percebido que este algoritmo não tem um custo fixo. Se todo o vetor estiver ordenado, ele nunca precisará iterar o [tex]i[/tex] e portanto será executado bem mais rápido do que se o vetor estiver inteiro em ordem decrescente (quando ele sempre precisará iterar [tex]i[/tex] até o fim – 0). Então, neste artigo, gostaria-lhes de apresentar a análise de algoritmos baseada em casos. Para este programa, dizemos que:

  • Melhor caso é quando todos os elementos já estão ordenados. Custo: [tex]\Theta{}(n)[/tex]
  • Pior caso é quando os elementos estão em ordem decrescente. Custo: [tex]\Theta{}(n^{2})[/tex]

Em alguns programas o caso médio é importante também, mas não é o caso da ordenação por inserção. Vemos que há uma diferença bem grande entre o custo dos dois casos. Por isso, precisamos conhecer onde que nosso algoritmo será implementado e quais as chances de ele ser o melhor ou pior caso. Em geral, o pior caso é o mais comum… Por isso, diremos que o custo deste algoritmo é [tex]\Theta{}(n^{2})[/tex].