Tiago Madeira

Ordenação

Ordenação por Inserção

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:

para j \leftarrow{} 2 até comprimento do vetor, faça
 elemento \leftarrow{} vetor[j]
 i \leftarrow{} j - 1
 enquanto i > 0 e vetor[i] > elemento, faça
     vetor[i + 1] \leftarrow{} vetor[i]
     i \leftarrow{} i - 1
 fim-enquanto
 vetor[i + 1] \leftarrow{} elemento
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 subtrai 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\)) contém todos seus valores ordenados e o segundo (de elementos \(\geq{} j\)) contém os valores que devem ser inseridos no primeiro vetor já ordenado (por isso ele se chama Algoritmo de Inserção). A chave do algoritmo é o enquanto que acontece para ir deslocando todos os elementos para seu índice \(+1\)) contém todos seus valores ordenados e o segundo (de elementos \(\geq{}j\)) contém os valores que devem ser inseridos no primeiro vetor já ordenado (por isso ele se chama Algoritmo de Inserção).

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

Comentários

José Oliveira

Quando teremos artigos sobre grafos?:D

Tiago Madeira

Acho que daqui a uns 5 artigos. Só vou acabar os algoritmos de ordenação e já vou pra eles. ;)

CosmeWeb

Já me perdi a muito tempo nos teus artigos. :( Poderia citar uns exemplos em JS ou até mesmo em PHP, seria bem melhor. :P

Tiago Madeira

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!

Tiago Madeira &raquo; Ordenação por Inserção

[…] O artigo está em outro local agora: Ordenação por inserção […]

débora

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…

Danilo

Não deveria ser; “enquanto i > = ( IGUAL ) 0 e vetor[i] > elemento, faça” ???

Danilo

Está correto, desculpe.

Irai

.Bom trabalho Tiago, muito bom artigo

Manoel mota

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.

lino

valeu cara, finalmente consegui entender, hehe!

Antonio

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!

Regina Oliveira

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 n² 1²n n log n Saberia informar como posso pesquisar e determinar a ordenação? Obrigada pela atenção e ajuda. Regina Oliveira

marco antonio

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

hermes levino

boa noite thiago tem como explicar ele implementado no laço for ?, ja que no laço while me confundiu um pouco!

Marcos

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.

Marcelo

Parabéns pela didática e paciência em escrever o artigo. Todo professor deveria fazer o mesmo.

João Carlos

Gostei muito dos teus artigos. Gostaria de pedir a sua permissão para citá-los nas minhas aulas, sempre adicionando seu nome no rodapé.

Lucas Emanuel

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]…?

Lucas Emanuel

gente desculpa, eu me refiro fazer essa mudança depois do enquanto no lugar de vetor[i+1] <- elemento…

Leilson

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.

Andrea

O senhor continua respondendo perguntas sobre Alg em 2011? Gostei da sua pagina.

Andrea

O senhor continua respondendo perguntas sobre Alg em 2011?

pamela

Olá Tiago, como faço para ter contato? abraço.

Tiago Madeira

http://tiagomadeira.com/contato/ (ou os comentários mesmo)

Reginaldo

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.

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

Infelizmente ocorreu um erro ao enviar seu comentário.