Tiago Madeira

Ordenação

Ordenação por Seleção

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-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 i=1. Vou sempre marcar \(i\) com a cor preta e \(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 \(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] 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

  1. n
  2. n
  3. \sum_{j=1}^{n} n
  4. \sum_{j=1}^{n} 1
  5. \sum_{j=1}^{n} 1
  6. 0
  7. 0
  8. n-1
  9. n-1
  10. n-1
  11. 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 &raquo; 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 ??

Obrigado! Seu comentário foi enviado e será publicado quando for aprovado.

Infelizmente ocorreu um erro ao enviar seu comentário.