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.

Categoria(s): Ordenação

15 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

#5 | Babi Matos (04/09/2008)

Faço sistemas de informação e estou desenvolvendo um programa em pascal utilizando todos os 4 principais métodos de ordenação: seleção, inserção, bolha e quicksort. Este programa usa a estrutura de um menu onde o usuário vai digitar elementos e escolher o método de seleção pra ordenar e mostrar na tela.
Estou utilizando procedures para implmentar os métodos, mas a seleção não estou conseguindo, entra em loop. Me ajudem por favor…
Veja a minha estrutura e me digam o que estou fazendo de errado??? Se possivel pode corrigir pra mim!
Obrigada.
Babi
var
vetor: array[0..10] of integer;
x,y, a,b:integer;

Procedure Insere(var a:integer; b:integer);
var
i, j, chave: integer;
Begin
for i:=1 to 10 do
for j:= 2 to 10 do
begin
chave:= vetor[j];
i:= j - 1;

while (i > 0) and (vetor[i] > chave ) do
begin
vetor[i + 1]:= vetor[i];
i:= i - 1;
end;
vetor[i + 1]:= chave;
end;

end;
BEGIN
clrscr;
{programa principal}

write(’Digite os elementos: ‘);
for y:=1 to 10 do
begin
readln(vetor[y]);
end;
Insere(a,b);
For y:= 1 to 10 do
writeln (vetor[y]);
readkey;
end.

#6 | Fabiano (28/09/2008)

Não sou especialista em pascal, talvez por isso eu não tenha entendido a sua lógica.
De qualquer forma, têm alguns erros no algoritmo ali em cima.
Se ainda precisar disso me mande um e-mail, q farei o possível pra ajudar.

#7 | Manoel Mota (16/12/2008)

O método é legal e eu gostei, mais vi que o seu primeiro “para” começou com 1, logo quando compilei percebi que o primeiro elemento sempre era o primeiro que eu digitava… mudei para iniciar de 0(zero) e funcionou normal…

#8 | Luiz (19/05/2009)

Manoel
É que quando tu declarou o vetor, tu começou por 0, tente declarar [1..x] …

#9 | fabio (27/11/2009)

ta ai embaixo o que consegui fazer, espero ter ajudado, tchau
program insercao2;
uses crt;

var
vetor: array[0..10] of integer;
i, j, chave,y, a,b:integer;

BEGIN
clrscr;
{programa principal}
for y:=1 to 10 do
begin
writeln(’Digite o, ‘,y,’ elemento: ‘);
readln(vetor[y]);
end;

for j:= 2 to 10 do
begin
chave:= vetor[j];
y:= j - 1;
while (y > 0) and (vetor[y] > chave ) do
begin
vetor[y + 1]:= vetor[y];
y:= y - 1;
end;
vetor[y + 1]:= chave;
end;
For y:= 1 to 10 do
writeln (vetor[y]);

readkey;

end.

#10 | Samuel (10/06/2010)

Esse trabalho está difícil de fazer. Por favor me dê uma ajuda.
O enunciado é esse.
*Apresentar a elaboração de um algoritmo ( passo a passo em forma de texto ) para cada um dos problemas a seguir.
1) localizar os livros de um determinado autor e listar o título de cada um:
2) localizar um determinado título e exibir informações sobre a obra.

#11 | h (11/08/2010)

Valew pelas dicas… eu ri do cara que quer que você faça o trabalho dele… hehe

#12 | Hugo Victorino (03/11/2010)

o programa do fabio ficou bem melhor de entender =X
mas tá valendo.

#13 | bruce william (19/08/2011)

bom seu algoritmo estora o metodo propostos a algoritmos de seleção, implementei uma solução melhor para a mesma :
void selecao (int vetor[], int tam){
int cont, mini, aux, tmp;

for(cont=0;cont<tam;cont++){
mini = cont;
for(aux = cont+1; aux vetor[aux]){
mini = aux;
}
C++;
}
if(cont!=mini){
tmp = vetor[cont];
vetor[cont] = vetor[mini];
vetor[mini] = tmp;
T++;
}

}

#14 | bruce william (19/08/2011)

bom seu algoritmo estora o metodo propostos a algoritmos de seleção, implementei uma solução melhor para a mesma :
void selecao (int vetor[], int tam){
int cont, mini, aux, tmp;

for(cont=0;cont<tam;cont++){
mini = cont;
for(aux = cont+1; aux vetor[aux]){
mini = aux;
}

}
if(cont!=mini){
tmp = vetor[cont];
vetor[cont] = vetor[mini];
vetor[mini] = tmp;

}

#15 | Rafael (08/11/2011)

Cara.. to com problemas pra resolver o algoritmo da ambulancia.. e oseu esta inativo…

to com problemas na saida… do algoritmo em c…

Escreva um comentário

Para ler o que escrevo atualmente, visite meu novo blog.

Índice

Online Judges

Programming Contests

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 que permite que você copie, distribua, exiba, execute a obra e crie obras derivadas desde que mantenha os créditos, não use sua modificação para fins comerciais e compartilhe seu trabalho derivado pela mesma licença.

HTML 4.01 gerado por WordPress em 0.401 segundos.