Algoritmos Computacionais

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  1 até tamanho-1, faça
2.	minimo  i
3.	para j  i+1 até tamanho, faça
4.		se vetor[j] < vetor[minimo], então
5.			minimo  j
6.		fim-se
7.	fim-para
8.	temp  vetor[i]
9.	vetor[i]  vetor[minimo]
10.	vetor[minimo]  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.

Aí ele começa com . Vou sempre marcar com a cor preta e com a cor cinza.

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

... , portanto .

... , portanto não mexemos em nada.

... , portanto não mexemos em nada.

... , portanto .

... , portanto não mexemos em nada.

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

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. 
2. 
3. 
4. 
5. ???
6. 
7. 
8. 
9. 
10. 
11. 

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 (como se nenhum se entrasse) e depois com ela valendo .

Primeiro cálculo

Segundo cálculo

Conclusão

Como vocês puderam ver, não faz diferença alguma o 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.

Espero que tenham gostado! Qualquer dúvida, sugestão ou notificação de erro; poste um comentário ou me envie um e-mail.

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais

Também conhecida como Insertion Sort, a Ordenação por Inserção consiste em inserir um elemento num vetor já ordenado de 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  2 até comprimento do vetor, faça
2.	elemento  vetor[j]
3.	i  j - 1
4.	enquanto i > 0 e vetor[i] > elemento, faça
5.		vetor[i + 1]  vetor[i]
6.		i  i - 1
7.	fim-enquanto
8.	vetor[i + 1]  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.

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

Então ele me diz que . Portanto, . 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 é maior que 0. é maior que o ? Sim, então vamos entrar no corpo do enquanto... Aqui ele me manda fazer um , que nesse caso é fazer um .

E agora subtrae de i um valor. Portanto, . Ele retorna ao enquanto, mas agora não satisfazemos a condição , por isso saímos do enquanto. Então ele pede para (). Portanto, o vetor fica assim:

E incrementamos o j, agora .

... E ? Não! Portanto, não entramos no enquanto.

(nenhuma mudança)

E lá vamos para e continuando até que vamos ter o vetor ordenado:

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 ) contém todos seus valores ordenados e o segundo (de elementos ) contém os valores que devem ser 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 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 (porque depois fazemos quando )

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 e portanto será executado bem mais rápido do que se o vetor estiver inteiro em ordem decrescente (quando ele sempre precisará iterar 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:
• Pior caso é quando os elementos estão em ordem decrescente. Custo:

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 é .

Por hoje é isso aí... Espero que vocês tenham gostado. Qualquer dúvida, não hesitem em perguntar! Ah... E comentem e sugiram para os próximos artigos!

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais