algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.
January 13, 2006
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 i1 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
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.
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
. Vou sempre marcar
com a cor preta e
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
até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.
...
, portanto
.
| v[1] | v[2] | v[3] | v[4] | v[5] | v[6] |
| 5 | 3 | 7 | 8 | 2 | 5 |
...
, portanto não mexemos em nada.
...
, portanto não mexemos em nada.
...
, portanto
.
| v[1] | v[2] | v[3] | v[4] | v[5] | v[6] |
| 5 | 3 | 7 | 8 | 2 | 5 |
...
, 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.
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




???





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
.






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
Dae Tiago!
Essa ordenação por seleção, usa o esquema de triangulação simples não é ? Ou seja, a mais usada nos exemplos de ordenação, não ?
Excelentes artigos Tiago!
Abraços!
[…] O artigo está em outro local agora: Ordenação por seleção […]
E aí Tiago..gostei muito das suas explicações!Você é muita fera mesmo!
Eu tô fazendo curso de programação,mas tenho dificuldades pra aprender a programar..
olá,
Gostaria de saber se ha possibilidade de enviar-me um exemplo de uma aplicação real de QUICK-SELECT - PODA E SELEÇÃO . Vi alguns exemplos mas não consegui entender.
por isso peço essa ajuda…
agradeço desde já.
Fernanda Silva
Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.
Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons.