Algoritmos Computacionais

Artigos sobre lógica de programação por Tiago Madeira

algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.

Ordenação por Inserção

January 11, 2006

Também conhecida como Insertion Sort, a Ordenação por Inserção consiste em inserir um elemento LaTeX: n num vetor já ordenado de LaTeX: 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  2 até comprimento do vetor, faça
2.	elemento  vetor[j]
3.	i  j - 1
4.	enquanto i > 0 e vetor[i] > elemento, faça
5.		vetor[i + 1]  vetor[i]
6.		i  i - 1
7.	fim-enquanto
8.	vetor[i + 1]  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 LaTeX: j=2 e iterar até o comprimento do vetor (6). A primeira ordem que ele me dá é para armazenar o elemento LaTeX: a[j] ( LaTeX: a[2] ) na variável elemento. Para facilitar toda a explicação eu vou sempre pintar de cinza o LaTeX: v[j] onde eu estou (no caso, o segundo elemento do vetor, 3) e de preto o vetor ainda não ordenado (elementos $LaTeX: \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 $LaTeX: i \leftarrow{} j-1$ . Portanto, LaTeX: 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 LaTeX: i =1 é maior que 0. LaTeX: v[1]=5 é maior que o LaTeX: elemento=3 ? Sim, então vamos entrar no corpo do enquanto... Aqui ele me manda fazer um LaTeX: vetor[i+1] = vetor[i] , que nesse caso é fazer um LaTeX: 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, LaTeX: i=0 . Ele retorna ao enquanto, mas agora não satisfazemos a condição LaTeX: i>0 , por isso saímos do enquanto. Então ele pede para LaTeX: vetor[i+1]=elemento ( LaTeX: 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 LaTeX: j=3 .

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

LaTeX: elemento = 7

LaTeX: i = 3-1 = 2

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

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

E lá vamos para LaTeX: 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 LaTeX: <j ) contém todos seus valores ordenados e o segundo (de elementos $LaTeX: \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 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 LaTeX: v[j] (porque depois fazemos LaTeX: v[i+1]=v[i] quando LaTeX: 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 LaTeX: i e portanto será executado bem mais rápido do que se o vetor estiver inteiro em ordem decrescente (quando ele sempre precisará iterar 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: $LaTeX: \Theta{}(n)$
Pior caso é quando os elementos estão em ordem decrescente. Custo: $LaTeX: \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 é $LaTeX: \Theta{}(n^{2})$ .

Categoria(s): Ordenação

16 comentários

#1 | José Oliveira (12/01/2006)

Quando teremos artigos sobre grafos?:D

#2 | Tiago Madeira (12/01/2006)

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

#3 | CosmeWeb (12/01/2006)

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

#4 | Tiago Madeira (12/01/2006)

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!

#5 | Tiago Madeira » Ordenação por Inserção (10/12/2006)

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

#6 | débora (08/03/2008)

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…

#7 | Danilo (03/05/2008)

Não deveria ser;

“enquanto i > = ( IGUAL ) 0 e vetor[i] > elemento, faça”

???

#8 | Danilo (03/05/2008)

Está correto, desculpe.

#9 | Irai (13/09/2008)

.Bom trabalho Tiago, muito bom artigo

#10 | Manoel mota (17/12/2008)

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.

#11 | lino (12/01/2009)

valeu cara, finalmente consegui entender, hehe!

#12 | Antonio (22/01/2009)

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!

#13 | Regina Oliveira (19/03/2009)

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

#14 | marco antonio (18/08/2009)

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

#15 | hermes levino (12/09/2009)

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

#16 | Marcos (15/09/2009)

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.

Escreva um comentário

Para ler o que escrevo atualmente, visite meu novo blog.

Índice

Online Judges

Programming Contests

Sobre o design

Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.

Licença

Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons que permite que você copie, distribua, exiba, execute a obra e crie obras derivadas desde que mantenha os créditos, não use sua modificação para fins comerciais e compartilhe seu trabalho derivado pela mesma licença.

HTML 4.01 gerado por WordPress em 0.449 segundos.