Ordenação por Seleção

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

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 \leftarrow{} 1 até tamanho-1, faça
2.  minimo \leftarrow{} i
3.  para j \leftarrow{} i+1 até tamanho, faça
4.      se vetor[j] < vetor[minimo], então
5.          minimo \leftarrow{} j
6.      fim-se
7.  fim-para
8.  temp \leftarrow{} vetor[i]
9.  vetor[i] \leftarrow{} vetor[minimo]
10. vetor[minimo] \leftarrow{} 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 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=2v[j] = 3 < v[minimo] = v[1] = 5[/latex], portanto [latex]minimo = j = 2[/latex].  <table> <thead> <tr> <td>v[1]</td> <td>v[2]</td> <td>v[3]</td> <td>v[4]</td> <td>v[5]</td> <td>v[6]</td> </tr> </thead> <tr> <td class="preto">5</td> <td class="cinza">3</td> <td>7</td> <td>8</td> <td>2</td> <td>5</td> </tr> </table>  [latex]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[/latex], portanto [latex]minimo = j = 5[/latex].  <table> <thead> <tr> <td>v[1]</td> <td>v[2]</td> <td>v[3]</td> <td>v[4]</td> <td>v[5]</td> <td>v[6]</td> </tr> </thead> <tr> <td class="preto">5</td> <td>3</td> <td>7</td> <td>8</td> <td class="cinza">2</td> <td>5</td> </tr> </table>  [latex]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-1
  3. \sum_{j=1}^{n} + n
  4. \sum_{j=1}^{n}
  5. \sum_{j=1}^{n} ???
  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}) + (0) + (0) + (0) + (n-1) + (n-1) + (n-1) + (0)

T(n) = n^{2} + 6n -3 \Theta{}(n^{2}) = f(n)

Segundo cálculo

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

T(n) = 1,5 n^{2} + 6,5 n - 3 \Theta{}(n^{2}) = f(n)

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.

19 comentários sobre “Ordenação por Seleção

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

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

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

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

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

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

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

  9. 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++;
    }

    }

    }

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

    }

    }

    }

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

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

Deixe uma resposta