Algoritmos Computacionais

Artigos sobre lógica de programação por Tiago Madeira

algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.

Ordenação por Seleção

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

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

Aí ele começa com LaTeX: i=1 . Vou sempre marcar com a cor preta e LaTeX: 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 LaTeX: j=2 até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.

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

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

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

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

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

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

LaTeX: j=6 ... LaTeX: 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

$LaTeX: \sum_{j=1}^{n} + n$
$LaTeX: \sum_{j=1}^{n}$
$LaTeX: \sum_{j=1}^{n}$ ???

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

Primeiro cálculo

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

$LaTeX: T(n) = n^{2} + 6n -3$

$LaTeX: \Theta{}(n^{2}) = f(n)$

Segundo cálculo

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

$LaTeX: T(n) = 1,5 n^{2} + 6,5 n - 3$

$LaTeX: \Theta{}(n^{2}) = f(n)$

Conclusão

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

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

Categoria(s): Ordenação

4 comentários

#1 | hlegius (15/01/2006)

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!

#2 | Tiago Madeira » Ordenação por Seleção (10/12/2006)

[…] O artigo está em outro local agora: Ordenação por seleção […]

#3 | Augusto César (02/04/2008)

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

#4 | Fernanda (30/05/2008)

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

Escreva um comentário

53 assinantes

Mais artigos

Comentários recentes

Matheus Eduardo Maura: Faço engenharia eletrica-eletronica( UNIRP SÃO JOSE DO RIO PRETO), e...
rafael: muito legal o artigo mas teria como resolver esse algoritmo nao consegui de jeito nenhum,...
Roger: Bom artigo. Podia atualizar esse site
Aline Celestrino Bento: o que É ALGORITMO=exemplo:35 :7 porque eu ñ sei ALINE
Claudio: eu gostaria de saber este algoritmo: faça um algoritmo que determine, para um digrafo,...
ingrid morgana gomes paes: que bacana que legau isso e emtesamte e legau para apremder mais a...
Filipe Névola: filipe.bico@hotmail. com
Filipe Névola: Boa noite, gostaria de saber se você tem alguma implementação de menor caminho...
Carlos Luiz Silva Meirelles: estou fazendo curso de informática gratuito patrocindo pelo estado....
Maria Regina de Queiroz: Olá Tiago, li os seus artigos e gostei muito, gostaria se possivel que...

Categorias

Escrevo também...

Tiago Madeira
Site pessoal e blog do autor destes artigos
Mal Vicioso
Blog sobre filosofia e sobre a hipocrisia da sociedade

Sobre o design

Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.

Licença

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.

HTML 4.01 gerado por WordPress em 0.646 segundos.