Método de Inserção e Shellsort

Prévia do material em texto

Para uma completa compreensão da técnica, vamos imaginar a situação
representada na figura abaixo:
O
r
d
e
n
a
ç
ã
o
-
I
n
s
e
r
ç
ã
o
Idéias Gerais
Subseqüência não-ordenadaSubseqüência ordenada
i
Ou seja, nosso objetivo é encontrar a posição correta do elemento A[i] na
subseqüência ordenada e inserí-lo em sua posição correta. Após a 
realização desse procedimento, a situação poderia ser ilustrada pela
seguinte representação diagramática:
A
0 n-1
O
r
d
e
n
a
ç
ã
o
-
I
n
s
e
r
ç
ã
o
Idéias Gerais
Subseqüência não-ordenadaSubseqüência ordenada
i+1
A
≤A[i] ≥A[i]
A[i]
O
r
d
e
n
a
ç
ã
o
-
I
n
s
e
r
ç
ã
o
Idéias Gerais
Este algoritmo é baseado no princípio de que em cada iteração, um 
elemento é inserido em sua posição correta, daí o nome inserção
associado ao método.
A questão fundamental é como encontrar a posição correta do elemento A[i] 
entre os elementos associados as posições no intervalo [0,i-1].
Há três alternativas clássicas para resolver essa questão, a saber:
O
r
d
e
n
a
ç
ã
o
-
I
n
s
e
r
ç
ã
o
Idéias Gerais
1ª Alternativa:Æ Vamos percorrer/caminhar/varrer a subseqüência
ordenada, da esquerda para a direita, até encontrar o primeiro elemento
maior (ou igual) ao elemento A[i], e, então, inserir A[i] antes ( a esquerda) 
desse elemento;
2ª Alternativa:Æ Vamos percorrer a subseqüência ordenada, da direita para
a esquerda, até encontrar o primeiro elemento menor (ou igual) ao elemento
A[i], e, então, inserir A[i] depois ( a direita) desse elemento;
3ª Alternativa:Æ Vamos usar o algoritmo de busca binária para encontrar a 
posição apropriada do elemento A[i] na subseqüência ordenada. Nesse caso, 
o algoritmo recebe o nome de ordenação por Inserção Binária;
Observação:Æ A 1ª e 2ª forma são equivalentes. Aqui, vamos implementar
a 2ª forma. Como sugestão, implemente as outras variantes.
O
r
d
e
n
a
ç
ã
o
Método de Inserção
Código parcial associado ao algoritmo de inserção usando notação indexada.
…
for (i=1; i<Dim; i++) { // para cada elemento na posição i
x = A[i]; // cópia do elemento A[i]
j = i-1; // posição de inicio da posição correta
while ( (j>=0)&& (A[j]>x) ) { // procurando a posição correta
A[j+1] = A[j]; // deslocando elementos a direita
j--; // atualizando índice
} // while
A[j+1] = x; // colocando elemento A[i] em sua posição correta
}
O
r
d
e
n
a
ç
ã
o
-
I
n
s
e
r
ç
ã
o
Método de Inserção
void Ordenacao_Insercao(int *A, int Dim) {
int i=1, j, x;
for (; i<Dim; i++) { // para cada elemento na posição i
x = *(A+i); // cópia do elemento A[i]
j = i-1; // posição de inicio da posição correta
while ( (j>=0) && (*(A+j) > x)) ) {//buscando a posição correta
*(A+j+1) = *(A+j); // deslocando elementos a direita
j--; // atualizando índice
} // while
*(A+j+1) = x; //colocando elemento A[i] em sua posição correta
} //for
return;
} // Odenacao_Insercao;
Função associada ao algoritmo de inserção para trabalhar com arrays 
arbitrários e com quaisquer dimensões, usando notação de ponteiros.
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Alguns Fatos
O Método de Ordenação Shellsort pode ser visto como uma variante do 
Método de Inserção (Insertionsort).
O nome Shellsort é em homenagem ao inventor do método, Donald L. 
Shell, em 1959.
Método de ShellSort também é conhecido como Ordenação por 
Incrementos Decrescentes
Uma das razões da lentidão do Método de Inserção é em função do fato 
de que há muitas movimentações para se encontrar o lugar correto, onde 
efetivamente o elemento será inserido. Assim, elementos que estão longe 
de sua posição correta, serão posicionados após muitas trocas.
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Recordando – Método de Inserção
A A[i]
i
Seqüência 
ordenada
Seqüência 
não-ordenada
≤ A[i] ≥ A[i]
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Recordando Método de Inseção
void InsertionSort (int *Str, int Dim) {
int i, j, x;
for (i = 1; i < Dim; i++) {
x = *(Str+i);
for (j=i; x < *(Str+j-1) && j > 0; j--)
*(Str+j) = *(Str+j-1);
*(Str+j) = x;
} //for i
return;
}InsertionSort Elementos que estão longe de sua posição correta, 
serão posicionados após 
muitas trocas.
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Observações Gerais
Uma das razões da lentidão do Método de Inserção é em função 
do fato de que há muitas movimentações para se encontrar o 
lugar correto onde efetivamente o elemento será inserido. Assim, 
elementos que estão longe de sua posição correta, serão 
posicionados após muitas trocas de elementos adjacentes.
Será que não é possível fazer comparações entre elementos que 
estão em distâncias mais longas? 
Se trocarmos os elementos de posições não de uma distância 
unitária (InsertionSort), mas entre distâncias mais longas, 
certamente faremos menos trocas e quando elas ocorrerem, 
saltos acontecerão entre posições não adjacentes.
Esta estratégia evita o número excessivo de trocas (movimentação 
de dados), comparando elementos que estão relativamente longe 
um do outro, assim, se houver troca, o deslocamento é
significativo.
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Idéia Geral do Método
Os elementos são divididos em grupos e cada um dos grupos são 
ordenados com o Método de Inserção.
Em outras palavras, aplica-se o princípio da Ordenação por 
inserção sobre subseqüências periódicas de tamanho h na 
seqüência original.
As subseqüências a serem ordenadas são determinadas pela 
seqüência de parâmetros chamados 
decrementos.
1 2 1, , , ,t t th h h h− − "
Na verdade, os tamanhos h de cada subseqüência é determinado 
fazendo com que h assuma os valores .1 2 1, , , ,t t th h h h− − "
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Idéia Geral do Método
A seqüência de decrementos deve
1
1
1
 
t t
h
h h−
=⎧⎨ <⎩
1 2 1, , , ,t t th h h h− −< >"
satisfazer as seguintes condições :
O
r
d
e
n
a
ç
ã
o
Idéia Geral do Método
1 2 1, , , ,t t th h h h− − "
A[0], A[d], A[2d], A[3d], ...
A[1], A[d+1], A[2d+1], A[3d+1], ...
A[d-1], A[2d-1], A[3d-1],...
...
Se ht = d, teríamos d 
subseqüências:
A[0], A[6], A[12], A[18], ...
A[1], A[7], A[13], A[19], ...
A[5], A[11], A[17],...
...
Se ht = 6, teríamos 6 
subseqüências:
A
0 1 2 3 4 5 6 7 8 9 ... n-1
:Æ Seqüência de parâmetros decrescentes.
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Exemplo de Aplicação do Método
Antes de formalizar o método, vamos ilustrar seu princípio de 
funcionamento através de um exemplo.
7 19 24 13 31 8 82 18 44 63 5 29
0 1 2 3 4 5 6 7 8 9 10 11
Neste exemplo, vamos considerar ht = 6 e a seqüência:
Logo, o array original é dividido em 6 subseqüências, a saber:
A[0], A[6]
A[1], A[7]
A[2], A[8]
A[3], A[9]
A[4], A[10]
A[5], A[11]
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Exemplo de Aplicação do Método
Posições
7 19 24 13 31 8 82 18 44 63 5 29
0 1 2 3 4 5 6 7 8 9 10 11
93
104
115
82
71
60
Após este passo inicial a seqüência passa a ser.
7 18 24 13 5 8 82 19 44 63 31 29
0 1 2 3 4 5 6 7 8 9 10 11
Vamos aplicar a mesma idéia, mas agora reduzindo o 
passo para h = 4, ou seja, ht-1= 4.
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Exemplo de Aplicação do Método
7 18 24 13 5 8 82 19 44 63 31 29
0 1 2 3 4 5 6 7 8 9 10 11
Posições
1173
1062
951
840
Após este passo a seqüência passa a ser.
5 8 24 13 7 18 31 19 44 63 82 29
0 1 2 3 4 5 6 7 8 9 10 11
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Exemplo de Aplicação do Método
5 8 24 13 7 18 31 19 44 63 82 29
01 2 3 4 5 6 7 8 9 10 11
Vamos aplicar a mesma idéia, mas agora reduzindo o passo para 
h = 3, ou seja, ht-2= 3.
Posições
11852
10741
9630
5 7 18 13 8 24 31 19 29 63 82 44
0 1 2 3 4 5 6 7 8 9 10 11
Após este passo a seqüência passa a ser.
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Exemplo de Aplicação do Método
Vamos aplicar a mesma idéia, mas agora reduzindo o passo para 
h = 2, ou seja, ht-3= 2.
Posições
5 7 18 13 8 24 31 19 29 63 82 44
0 1 2 3 4 5 6 7 8 9 10 11
Após este passo a seqüência passa a ser.
1197531
1086420
5 7 8 13 18 19 29 24 31 44 82 63
0 1 2 3 4 5 6 7 8 9 10 11
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Exemplo de Aplicação do Método
Vamos aplicar a mesma idéia, mas agora reduzindo o passo para 
h = 1, ou seja, ht-4= 1. Observem que agora estamos exatamente 
aplicando o Método de Inserção, só que a seqüência já está
praticamente ordenada, conforme pode ser observado. Na verdade, 
só há dois elementos fora de posição e eles estão muito próximos 
um do outro.
Após este passo a seqüência passa a ser.
5 7 8 13 18 19 29 24 31 44 82 63
0 1 2 3 4 5 6 7 8 9 10 11
5 7 8 13 18 19 24 29 31 44 63 82
0 1 2 3 4 5 6 7 8 9 10 11
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Conclusões Gerais
A eficiência deste método se dá em função do fato de que em cada 
etapa do processo de comparação, poucos elementos são 
envolvidos (subseqüências). 
Como a seqüência vai ficando cada vez mais ordenada, a 
necessidade de troca de elementos “fora de ordem” diminui cada 
vez mais, assim, na etapa em que a distância é 1 poucas 
movimentações são necessárias. Caso em que, o método de 
ordenação Shellsort se transforma no método de Inserção, ou 
seja, o método de Inserção é um caso particular do método de 
ShellSort, quando o passo é igual a 1.
Além disso, em cada etapa a seqüência fica mais ordenada e 
movimenta os dados a grandes distâncias, diferentemente do 
método de Inserção em que há muitos deslocamentos unitários 
para se encontrar definitivamente o lugar correto onde a inserção 
será realizada.
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Conclusões Gerais
Qualquer seqüência de decrementos deve produzir uma ordenação 
da seqüência original de valores, desde que no último passo, o valor 
do decremento (incremento decrescente) seja igual a 1, onde todo o 
trabalho restante será feito.
Em outras palavras, o programa pode ser implementado sem 
depender de uma seqüência específica de incrementos.
Como vocês irão verificar no trabalho que irão desenvolver, este
método de ordenação é bem melhor que os anteriores que já vimos 
(Seleção, Bolha e Inserção).
Mesmo sendo eficiente, ele se mantém extremamente simples em 
sua concepção e o seu código e extremamente compacto, o que 
ilustra o poder desta técnica (fazendo muito, com pouco).
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Conclusões Gerais
Observem que, na primeira iteração, todos os elementos que estão 
a uma distância ht são ordenados. 
Na segunda iteração, todos os elementos que estão a uma 
distância ht-1 são ordenados e assim sucessivamente, até que 
h1= 1.
No algoritmo original, Donald L. Shell sugere iniciar ht com N/2 e 
decrementar este valor sistematicamente pela metade, até atingir 1.
Na verdade, algumas seqüências de decrementos produzem 
melhores resultados do que outras (ver código), mas isto será
analisado mais cuidadosamente na disciplina de Complexidade de 
Algoritmos. (Próximo slide dá um exemplo)
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Conclusões Gerais
Substitua a seqüência dos decrementos por uma seqüência que 
seja potência de 2, tipo {16, 8, 4, 2, 1} e verifique a performance. 
Pensem no fato (por quê) dessa seqüência ser particularmente 
ineficiente ?
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Trabalho Ordenação (Penúltimo)
Execute cada um dos algoritmos para os mesmos conjuntos de valores 
inteiros e obtenha os tempos correspondentes a cada um deles. Anote-os e 
reserve;
Implemente os seguintes algoritmos de ordenação:
¾Seleção (dado em sala);
¾ Bolha (dado em sala);
¾ Insercao (dado em sala);
¾ Shellsort (discutido em sala);
¾ Mergesort (pesquisar);
¾ Quicksort (pesquisar);
Trabalhe com conjuntos de valores inteiros com cardinalidade (número de 
elementos):
2 2 3 3 4 4 4 5 5 5 610 ,5.10 ,10 ,5.10 ,10 ,3.10 , 5.10 , 10 , 2.10 , 5.10 , 10 .
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Se achar necessário, sinta-se a vontade para gerar outros conjuntos de 
valores com diferentes números de elementos;
Elabore um gráfico com as curvas relativas a todos os algoritmos 
implementados. Identifique cada uma das curvas;
A partir dos dados obtidos previamente, utilize um aplicativo (Gnuplot, Matlab, 
Excell, Origin, etc) para gerar os gráficos (individuais) relativos ao 
comportamento prático (performance) de cada um dos algoritmos (tempo de 
execução (eixo-y) em função do número de elementos (eixo-x) );
Elabore um “relatório técnico” que contenha uma descrição do trabalho 
elaborado, os gráficos obtidos, uma análise dos resultados (sua conclusão), 
aplicativos usados, anexos com as planilhas e outros elementos que você 
julgar que sejam necessários;
Trabalho Ordenação (Penúltimo)
O
r
d
e
n
a
ç
ã
o
-
S
h
e
l
l
s
o
r
t
Informações adicionais serão dadas em sala de aula;
Envie uma cópia do relatório ( .doc, .pdf, ...), das planilhas (dados) a partir das 
quais você obteve os gráficos e uma cópia dos códigos elaborados. Não 
esqueça de comprimir seus arquivos. Não copie dados (planilhas) dos colegas 
em hipótese alguma.
Prazo de Entrega: 16 de outubro.
Trabalho Ordenação (Penúltimo)