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.
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
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.
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.
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…
Manoel
É que quando tu declarou o vetor, tu começou por 0, tente declarar [1..x] …
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.
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.
o programa do fabio ficou bem melhor de entender =X
mas tá valendo.
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++;
}
}
}
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;
}
}
}
Cara.. to com problemas pra resolver o algoritmo da ambulancia.. e oseu esta inativo…
to com problemas na saida… do algoritmo em c…
Para ler o que escrevo atualmente, visite meu novo blog.
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 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.