Ordenação por Inserçã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.

Também conhecida como Insertion Sort, a Ordenação por Inserção consiste em inserir um elemento n num vetor já ordenado de n-1 elementos. Neste artigo, apresento-lhes este simples algoritmo para ordenação de vetores.

O pseudocódigo da ordenação por inserção é o seguinte:

1. para j \leftarrow{} 2 até comprimento do vetor, faça
2.  elemento \leftarrow{} vetor[j]
3.  i \leftarrow{} j - 1
4.  enquanto i > 0 e vetor[i] > elemento, faça
5.      vetor[i + 1] \leftarrow{} vetor[i]
6.      i \leftarrow{} i - 1
7.  fim-enquanto
8.  vetor[i + 1] \leftarrow{} elemento
9. fim-para

Para explicar eu vou fazer uma coisa que sempre faço para corrigir meus algoritmos, fingir que sou o programa, executando cada passo manualmente (claro que geralmente faço mais rápido, porque não preciso escrever tudo que faço). Vamos iniciar com o seguinte vetor v.

v[1] v[2] v[3] v[4] v[5] v[6]
5 3 7 8 2 5

Aí o código me manda começar com j=2 e iterar até o comprimento do vetor (6). A primeira ordem que ele me dá é para armazenar o elemento a[j] (a[2]) na variável elemento. Para facilitar toda a explicação eu vou sempre pintar de cinza o v[j] onde eu estou (no caso, o segundo elemento do vetor, 3) e de preto o vetor ainda não ordenado (elementos \geq{}j).

v[1] v[2] v[3] v[4] v[5] v[6]
5 3 7 8 2 5

Então ele me diz que i \leftarrow{} j-1. Portanto, i=1. E agora ele me faz um enquanto (que poderia ser substituído por para) onde meu i deverá ir diminuindo. Vamos entrar no loop…

Bom, meu i =1 é maior que 0. v[1]=5 é maior que o elemento=3? Sim, então vamos entrar no corpo do enquanto… Aqui ele me manda fazer um vetor[i+1] = vetor[i], que nesse caso é fazer um v[2]=v[1]=5.

v[1] v[2] v[3] v[4] v[5] v[6]
5 5 7 8 2 5

E agora subtrae de i um valor. Portanto, i=0. Ele retorna ao enquanto, mas agora não satisfazemos a condição i>0, por isso saímos do enquanto. Então ele pede para vetor[i+1]=elemento (v[1]=elemento). Portanto, o vetor fica assim:

v[1] v[2] v[3] v[4] v[5] v[6]
3 5 7 8 2 5

E incrementamos o j, agora j=3.

v[1] v[2] v[3] v[4] v[5] v[6]
3 5 7 8 2 5
elemento = 7 i = 3-1 = 2

i > 0 … E 5 > 7? Não! Portanto, não entramos no enquanto.

v[3] = elemento (nenhuma mudança)

E lá vamos para j=4 e continuando até que vamos ter o vetor ordenado:

v[1] v[2] v[3] v[4] v[5] v[6]
2 3 5 5 7 8

Qual a lógica?

Como eu já disse na introdução, mas lá sem grandes explicações, a Ordenação por Inserção divide o vetor em dois. O primeiro (de elementos <j[/latex]) contém todos seus valores ordenados e o segundo (de elementos [latex]\geq{}j[/latex]) contém os valores que devem ser <strong>inseridos</strong> no <em>primeiro</em> vetor já ordenado (por isso ele se chama <strong>Algoritmo de Inserção</strong>).   A chave do algoritmo é o <strong>enquanto</strong> que acontece para ir deslocando todos os elementos para seu índice [latex]+1 enquanto o elemento for menor que eles (para depois o elemento ser colocado onde parou).

A variável elemento só serve para não perdermos o valor de v[j] (porque depois fazemos v[i+1]=v[i] quando i=j-1)

Acredito que não tenham restado dúvidas. Dê mais uma olhada no algoritmo e tente implementar. Se tiver dificulade, coloque mensagens de debug estratégicas para entender o algoritmo. (ex.: no início do para coloque para imprimir o valor de j e no início de cada enquanto coloque para imprimir os valores elemento, i e v[i])

Custo

Você deve ter percebido que este algoritmo não tem um custo fixo. Se todo o vetor estiver ordenado, ele nunca precisará iterar o i e portanto será executado bem mais rápido do que se o vetor estiver inteiro em ordem decrescente (quando ele sempre precisará iterar i até o fim - 0). Então, neste artigo, gostaria-lhes de apresentar a análise de algoritmos baseada em casos. Para este programa, dizemos que:

  • Melhor caso é quando todos os elementos já estão ordenados. Custo: \Theta{}(n)
  • Pior caso é quando os elementos estão em ordem decrescente. Custo: \Theta{}(n^{2})

Em alguns programas o caso médio é importante também, mas não é o caso da ordenação por inserção. Vemos que há uma diferença bem grande entre o custo dos dois casos. Por isso, precisamos conhecer onde que nosso algoritmo será implementado e quais as chances de ele ser o melhor ou pior caso. Em geral, o pior caso é o mais comum... Por isso, diremos que o custo deste algoritmo é \Theta{}(n^{2}).

26 comentários sobre “Ordenação por Inserção

  1. Dae Cosme…

    Exatamente onde que você se perdeu? O que você não entendeu? Que aí eu reforço esse ponto escrevendo um novo artigo ou editando o mesmo. Acho que o único artigo que ficou meio complexo foi o “Análise de Algoritmos” (segundo o Zé, foi escrito para estudantes de Ciência da Computação). Mas é que aquilo ali é questão de se acostumar. Você pra começar a usar algoritmos, não precisa nem pensar em custo se não quiser também! ;)

    Aguardo sua resposta!

  2. Você e muito fera!
    Estou fazendo um curso técnico de micro informatica
    e estou aprendendo algoritmo.
    e com esse site você tem me ajudado bastante…

  3. Gostei do artigo… achei muito legal, mais acho que o j = 2, deve ser j = 1, já que em muitas linguagems a contagem do índice começa do 0(zero) e não de 1.

  4. Manoel,

    realmente, muitas linguagens indexam o vetor de 0 a n-1; mas levando em conta que muitas também não o fazem, do jeito que ele colocou (pseudocódigo) é bem mais didático.

    Abraço!

  5. Boa noite, prof. Tiago Madeira.

    Curso Ciência da Computação no UniBH e tenho q realizar um trabalho na disciplina de AEDS 3 que solicita encontrar uma ordenação crescente para o comportamento assintótico das seguintes funções:
    n!
    n elevado a n
    4 elevado a n
    4 elevado a log2 n

    1²n
    n log n

    Saberia informar como posso pesquisar e determinar a ordenação?

    Obrigada pela atenção e ajuda.

    Regina Oliveira

  6. como saeria a implementação para organização em ordem decrescente, seria mudar apenas o valor do enquanto para como mostra o exemplo???

    Aguardo retorno

    Obrigado

    abraços

    Marco Antonio

  7. Bom dia Professor.
    Minha pergunta nao e sobre algoritmos, mas com sua experiencia como professor talvez possa me ajudar.E o seguinte , estudo ciencia da computaçao, sou fascinado, mas tenho muita dificuldade em aprender.Enquanto os meus colegas entendem a logica dos programas ainda dentro da sala com a explicaçao do professor , eu , se nao chegar em casa e me debruçar sobre os livros nao consigo aprender , e tem dias que nem assim.Atualmente tenho decorado os algoritmos em vez de entender.Nao e por falta de estudo, fico o maior tempo tentando entender a logica de um programa simples .Tb tem o lado da baixa alto estima, eu ja começo achando q e super complicado e q meus colegas sao mais inteligentes q eu.E possivel desenvolver esse raciocinio rapido para entender a logica desses programas so fazendo exercicios e com o tempo, ou essa caracteristica ja deve estar presente nos estudantes de computaçao.O q vc acha q esta acontecendo comigo em relaçao a dificuldade para aprender ?.Aprender programaçao depende mais do esforço e perseverança ou a pessoa deve ter um talento ou vocaçao previa.Muito agradecido, desculpe o tamanho do post.

  8. ola, fiquei com uma dúvida.

    Eu não poderia dentro do enquanto colocar simplismente V[i] <- elemento depois de eu fazer a troca do elemento que esta na posiçao v[i] para a posição v[i+1]…?

  9. Abaixo do fim-enquanto ta errado, não é vetor[i+1] <- elemento e sim vetor[i] <- elemento, pois foi vetor[i] que ficou vazia. O vetor[i+1] recebeu o valor 5, então agora vetor[i] recebe o valor 3.

  10. Estou tentando criar um algoritmo de Ordenação por Inserção mas não consigo fazer mostrar o vetor ordenado, como faço? Segue o algoritmo para análise. Desde já agradeço.
    {
    int i, j, chave;
    const qtd=10;
    int v[qtd];
    srand(time(NULL));
    printf(“VETOR DESORDENADO\n”);
    for(i=0; i<qtd; i++)
    {
    v[i]=rand()%101;
    printf("\t%d \n", v[i]);
    }
    for(i=0; i<qtd; i++)
    {
    for(j=1; j<qtd-1; j++)
    {
    chave=v[j];
    v[j]=v[j-1];
    }
    while(chave = 0)
    {
    v[j+1]=v[j];
    v[j]=v[j-1];
    }
    v[j+1]=chave;
    }
    printf(“\n VETOR ORDENADO \n”);
    for(i=0; i<qtd; i++)
    printf("\t\%d \n", v[i]);
    system("PAUSE");
    return 0;
    }
    Aguardo resposta.

Deixe uma resposta