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:
para i \leftarrow{} 1 até tamanho-1, faça
minimo \leftarrow{} i
para j \leftarrow{} i+1 até tamanho, faça
se vetor[j] < vetor[minimo], então
minimo \leftarrow{} j
fim-se
fim-para
temp \leftarrow{} vetor[i]
vetor[i] \leftarrow{} vetor[minimo]
vetor[minimo] \leftarrow{} temp
fim-paratamanho = 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] |
| 5 |
Aí ele começa com i=1. Vou sempre marcar \(i\) com a cor preta e \(min\) com a cor cinza.
| v[1] |
| 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 \(j=2\) até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.
\(j=2\) … \(v[j] = 3 < v[minimo] = v[1] = 5\), portanto \(minimo = j = 2\).
| v[1] | v[2] | v[3] | v[4] | v[5] | v[6] |
| 5 | 3 | 7 | 8 | 2 | 5 |
\(j=3\) … \(v[j] = 3 < v[minimo] = v[1] = 5\), portanto \(minimo = j = 2\).
| v[1] | v[2] | v[3] | v[4] | v[5] | v[6] |
| 5 | 3 | 7 | 8 | 2 | 5 |
\(j=3\) … \(v[j] = 7 > v[minimo] = v[2] = 3\), portanto não mexemos em nada.
\(j=4\) … \(v[j] = 8 > v[minimo] = v[2] = 3\), portanto não mexemos em nada.
\(j=5\) … \(v[j] = 2 < v[minimo] = v[2] = 3\), portanto \(minimo = j = 5\).
| v[1] | v[2] | v[3] | v[4] | v[5] | v[6] |
| 5 | 3 | 7 | 8 | 2 | 5 |
\(j=6\) … \(v[j] = 2 < v[minimo] = v[2] = 3\), portanto \(minimo = j = 5\).
| v[1] | v[2] | v[3] | v[4] | v[5] | v[6] |
| 5 | 3 | 7 | 8 | 2 | 5 |
\(j=6\) … \(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] |
| 2 |
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
- n
- n
- \sum_{j=1}^{n} n
- \sum_{j=1}^{n} 1
- \sum_{j=1}^{n} 1
- 0
- 0
- n-1
- n-1
- n-1
- 0
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 \(0\) (como se nenhum se entrasse) e depois com ela valendo \(\sum_{j=1}^{n}\).
Primeiro cálculo
$$T(n) = n + (n-1) + (\sum_{j=1}^n n) + (\sum\_{j=1}^n 1) \times 2 + 0 \times 3 + (n-1) \times 3 + 0$$
$$T(n) = n^{2} + 6n - 3 = \Theta{}(n^2)$$
Segundo cálculo
$$T(n) = n + (n-1) + (\sum_{j=1}^n n) + (\sum\_{j=1}^n 1) \times 3 + 0 \times 2 + (n-1) \times 3 + 0$$
$$T(n) = 1,5 n^{2} + 6,5 n - 3 = \Theta{}(n^2)$$
Conclusão
Como vocês puderam ver, não faz diferença alguma o \(\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.
Comentários
hlegius
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!
Tiago Madeira » Ordenação por Seleção
[…] O artigo está em outro local agora: Ordenação por seleção […]
Augusto César
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..
Fernanda
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
Babi Matos
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.
Fabiano
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.
Manoel Mota
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…
Luiz
Manoel É que quando tu declarou o vetor, tu começou por 0, tente declarar [1..x] …
fabio
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.
Samuel
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.
h
Valew pelas dicas… eu ri do cara que quer que você faça o trabalho dele… hehe
Hugo Victorino
o programa do fabio ficou bem melhor de entender =X mas tá valendo.
bruce william
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++; } } }
bruce william
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; } } }
Rafael
Cara.. to com problemas pra resolver o algoritmo da ambulancia.. e oseu esta inativo… to com problemas na saida… do algoritmo em c…
Gustavo Antunes de Bitencourt
Em 2012, seu post de 2006, ainda está ajudando… Legal.. Algoritmo, lógica.. sempre.. Porém, seu pseudocódigo encontra-se com um erro… A condição em seu laço está errado. para i <– 1 até tamanho-1, faça <== atribui 1 ao i faz com que ele repita o primeiro valor em um vetor, lista, por exemplo. para i <– 0 até tamanho-1, faça <== atribuir 0 é o correto. Abraço.
Jaciara
Só uma ressalva sobre o “para i <- 1” e o pessoal comentando que deve ser “para i <- 0”: realmente na implementação deve-se inicializar a partir de zero (vetores possuem o primeiro índice igual a 0), mas como tenho visto muito pseudocódigos eles realmente exemplificam dessa maneira. Não é erro no pseudocódigo, ele apenas ilustra o que o i deve inicializar no primeiro índice do vetor.. Espero que entendam
Ozias
Alguém poderia postar como ficaria o pseudocódigo acima em c? Muito Obrigado!
igor
como seria o quicksort no visualg ??