UNIVERSIDADE FEDERAL DO PARÁ
CENTRO DE CIÊNCIAS EXATAS E NATURAIS
DEPARTAMENTO DE INFORMÁTICA
DISCIPLINA: ESTRUTURAS DE DADOS II
PROFESSOR: A B C SAMPAIO
ORDENAÇÃO DE DADOS
INTERCALAÇÃO - MERGESORT
ALUNOS: JORLAN TEIXEIRA COSTA NO: 9908802701
JOSÉ MARIA DE OLIVEIRA Jr. NO: 9908803401
CONSISTE EM DIVIDIR O VETOR EM DOIS OU MAIS,
ORDELÁ-LOS SEPARADAMENTE E INTERCALÁ-LOS DOIS
A DOIS FORMANDO, CADA PAR INTERCALADO, NOVOS
SEGMENTOS ORDENADOS ATÉ QUE RESULTE APENAS
UM SEGMENTO ORDENADO.
PARA OBTER A ORDENAÇÃO DOS SEGMENTOS
INICIAIS , PODE-SE USAR QUALQUER MÉTODO DE
INTERCALAÇÃO.
Segmentos previamente ordenados
intercala
intercala
ORDENADO
ORDENADO
Intercala
ORDENADO
PARA NÃO USAR OUTROS MÉTODOS , PODEMOS
INICIAR OS SEGMENTOS COM VALOR IGUAL A 1.
ESTE MÉTODO É CHAMADO DE MERGESORT.
MÉTODO DA INTERCALAÇÃO SIMPLES-MERGESORT
INICIA-SE COM SEGMENTOS DE VALOR IGUAL A 1.
COMO CADA SEGMENTO POSSUI APENAS 1
ELEMENTO CADA , JÁ ESTÃO ORDENADOS.
EXEMPLO
23 17
8 15
9 12 19
7
17 23 8 15 9 12 7 19
8 15 17 23 7 9 12 19
7 8 9 12 15 17 19 23
QUANDO O VET0R NÃO FOR UMA POTÊNCIA DE
2, OCORRERÁ UM SEGMENTO RESULTE SEM UM
PAR PARA SER INTERCALADO.
ESSE SEGMENTO QUE SERÁ O ULTIMO DO VETOR
É TRANSCRITO PARA A INTERAÇÃO SUBSEQUENTE.
EXEMPLO
23 17 8 15 9 12 19 7 14 10
17 23 8 15 9 12 7 19 10 14
8 15 17 23 7 9 12 19 10 14
7 8 9 10 12 15 17 19 23 10 14
7 8 9 10 12 14 15 17 19 23
A IMPLEMENTAÇÀO DO MÉTODO É
FEITA EM 3 NÍVEIS:
SIMPLEMERGE:
OPERAÇÃO DE INTERCALAÇÃO
DE UM PAR DE SEGMEMT0S
MERGEPASS:
INTERCALAÇÃO DE TODOS OS
PARES DE SEGMENTOS
ORDENADOS.
MERGESORT:
EFETUA TODA A SEQUÊNCIA
DE INTERCALAÇÃO
procedure simplemerge(c: vet; cI1, CF1,CI2, CF2:
integer; ca: vet; r: integer);
var
CAI1, CAI2, k, i: integer;
begin
CAI1:= CI1; CAI2:= CI2;
k:= r;
while (CAI1 <= CF1) and (CAI1 <= CF2 do
begin
if c[CAI1] < c[CAI2]
then
begin
ca[k]:= c[CAI2];
CAI1:= CAI1 + 1
end {then}
else
begin
ca[k]:= c[CAI2];
CAI2:= CAI2 + 1
end; {else}
k:= k + 1;
end; {while}
if CAI1 > CF1
then
for i:= CAI2 to CF2 do
begin
ca[k]:= c[i];
k:= k + 1;
end {for}
else
for i:= CAI1 to CF1
begin
ca[k]:= c[i];
k:= k + 1;
end; {for}
end; {simplemerge}
procedure mergepass(c, ca: vet;n, l: integer);
var
p, q, r, i: integer;
begin
p:= 1;
q:= p + l;
r:= 1;
while q <= n do
begin
simplemerge(c, p, q - 1, q, min(q + l - 1,
n), ca, r);
r:= r + 2*l;
p:= q + l;
q:= p + l;
end; {while}
if p <= n
then
for i:= p to n do
ca[i]:= c[i];
end; {mergepass}
procedure mergesort(c: vet; n: integer);
var
l, i: integer;ca:vet;
begin
l:= 1;
while l < n do
begin
if (l = 1) or (l = 4) or (l = 16) or
(l = 64) or (l = 256) or (l = 1024) or (l = 2048)
or (l = 4096)
then mergepass(c, ca, n, l)
else mergepass(ca, c, n, l);
l:= 2*l;
end; {while}
if (n = 2) or (n = 8) or (n =32) or (n = 128) or
(n = 512) or (n = 2048) or (n =8192)
then
for i:= 1 to n do
c[i]:= ca[i];
end; {mergesort}
EXEMPLO DE INTERCALAÇÃO
VETOR C
25
19
18
Q
P
P
CAI1:= CI1
CF1
VETOR CA
19
K:= R
CAI2:= CI2
CF2
25
K
10
Q
CAI1:= CI1
CAI2:= CI2
CF1
CF2
10
K:= R
18
K
VETOR CA
19
25
P
VETOR C
18
Q
CAI1:= CI1
CF1
10
18
K:= R
10
K
CAI2:= CI2
19
CAF2
25
INTERCALANDO SEQUÊNCIAS NATURAIS
CONSISTE EM TIRAR PROVEITO DAS
EVENTUAIS ORDENAÇÕES PARCIAIS.
BUSCA-SE OS SEGMENTOS JÁ ORDENADOS
EFETUANDO AS INTERCALAÇÕES A PARTIR
DELES.
EXEMPLO
23
23
11
11
74
42
23
23
42
11
74
42
96
65
11
58
42
58
65
58
58
65
74
65
87
87
87
74
99
99
99
87
36
94
36
94
36
94
94
99
ESTE MÉTODO DIMINUI O NÚMERO DE
INTERÇÕES EFETUADAS EM APENAS UMA
UNIDADE POR ISSO NÀO VALE A PENA
UTILIZAR ESTE MÉTODO.
EXEMPLO DE INTERCALAÇÃO
INTERCALAÇÃO DE ARQUIVOS CLASSIFICADOS
A INTERCALAÇÃO É FEITA COMPARANDO- SE
OS PRIMEIROS REGISTROS DE CADA UM DOS
ARQUIVOS A SEREM INTERCALADOS.
SELECIONA-SE AQUELE QUE POSSUIR A
MENOR CHAVE, TRANSFERINDO-A PARA A
SAÍDA.
ESSE REGISTRO É SUBSTITUÍDO
PELO SEU SUCESSOR E O PROCESSO É
REPETIDO ATÉ QUE NÃO SOBRE
NENHUM REGISTRO.
IMPLEMENTAÇÃO
• ARQUIVOS
ENTRADA: FILE(1) , FILE(2) , . . . , FILE(P) ;
SAÍDA: FILE(0).
• ÁRVORE DE SELEÇÃO
st[ 1 ] É A RAIZ DA ÁRVORE;
st[ 2i ] É A SUBÁRVORE DA ESQUERDA DE st[ i ]
i = 1, n div 2
st[ 2i + 1 ] É A SUBÁRVORE DA DIREITA DE st[ i ]
1
p-1
nodos não -folhas
p
2p-1
nodos folhas
14
13
09
05
08
17
15
11
10
29
19
16
18
35
35
23
24
22
72
.
.
.
.
.
.
.
.
.
.
.
.
.
21
.
.
09
05
08
14
13
17
15
11
10
29
21
19
16
18
35
23
24
22
72
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
.
13
09
05
08
14
15
17
19
11
10
29
21
23
16
18
35
.
24
22
72
.
.
.
.
.
.
.
.
.
.
.
.
.
35
.
05
13
09
10
08
14
15
17
19
11
18
29
21
23
16
22
35
.
24
.
72
.
.
.
.
.
.
.
.
.
.
35
.
.
.
09
13
05
11
10
08
14
15
17
19
16
18
29
21
23
24
22
35
.
.
.
72
.
.
.
.
.
.
.
.
.
.
35
.
.
05
09
13
08
11
10
29
14
15
17
19
16
18
35
21
23
24
22
72
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
.
procedure filemerge ( file, p, n );
begin
for i:=0 to p do
reset ( file (i) );
for i:=0 to p-1 do
st [1]:=minkey;
for i:=0 to 2*p-1 do
read (file (i-p+1) , st [i] );
for i:=0 to p-1 do
pop (st , file, 2*p-1 );
write (file (0), st[1] );
for i:=2 to n do
begin
pop (st , file, 2*p-1 );
write (file (0), st[1] );
end;
end;
CLASSIFICAÇÃO
POR
DISTRIBUIÇÃO DE CHAVES
ESTE MÉTODO DE CLASSIFICAÇÃO ANTECEDE AOS
COMPUTADORES DIGITAIS. ELE É UMA ADAPTAÇÃO DO
PROCESSO DE CLASSIFICAÇÃO MECÂNICA DE CARTÕES
PERFURADOS, UTILIZADOS PARA ARMAZENAMENTO DE
DADOS.
EXEMPLO
POR EXEMPLO, SUPONHAMOS QUE UM ARQUIVO
FORMADO POR 20 CARTÕES TIVESSE, EM UM CERTO
CAMPO, OS SEGUINTES VALORES PERFURADOS:
523, 018, 125, 937, 628, 431,
243, 705, 891, 362, 429, 005, 540,
353, 115, 427, 910, 580, 174, 456
A CLASSIFICAÇÃO PELA COLUNA QUE CONTÉM O
DÍGITO DA UNIDADE PRODUZIRIA A SEGUINTE
DISTRIBUIÇÃO PELOS ESCANINHOS
523, 018, 125, 937, 628, 431, 243, 705, 891, 362, 429,
005, 540, 353, 115, 427, 910, 580, 174, 456
CLASSIFICAÇÃO PELAS UNIDADES
115
580
353
005
910 891
243
705
427 628
540 431 362 523 174 125 456 937 018 429
0
1
2
3
4
5
6
7
8
9
RECOLHENDO OS CARTÕES NA ORDEM DESCRITA,TEMOS:
540, 910, 580, 431, 891, 362, 523, 243, 353, 174,
125, 705, 005, 115, 456, 937, 427, 018, 628, 429
CLASSIFICANDO PELA COLUNA DAS DEZENAS, OBTEMOS:
429
628
018 427
005 115 125 937 243 456
705 910 523 431 540 353 362 174 580 891
0
1
2
3
4
5
6
7
8
9
COLOCANDO-OS EM ORDEM, TEMOS:
705, 005, 910, 115, 018, 523, 125, 427, 628, 429,
431, 937, 540, 243, 353, 456, 362, 174, 580, 891
CLASSIFICANDO PELA COLUNA DA CENTENA, TEMOS:
456
174
431 580
018 125
362 429 540
937
005 115 243 353 427 523 628 705 891 910
0
1
2
3
4
5
6
7
8
9
AGORA FINALMENTE RETIRANDO-OS EM ORDEM
OBTEMOS OS CARTÕES NA ORDEM DESEJADA
005, 018, 115, 125, 174, 243, 353, 362, 427, 429,
431, 456, 523, 540, 580, 628, 705, 891, 910, 937
MÉTODO DA INDEXAÇÃO DIRETA - RADIXSORT
• UTILIZA-SE O DÍGITO COMO UM ÍNDICE QUE
VAI REMATER O DADO TODO PARA O ESCANINHO
CORRESPONDENTE.
• UTILIZA-SE UMA TABELA DE FREQUÊNCIAS
PARA CONTABILIZAR O NÚMERO DE CHAVES.
• UTILIZA-SE UMA TABELA DE FREQUÊNCIAS
ACUMILADASPARA INDICAR A POSIÇÃO
INICIAL DE CADA ESCANINHO.
• A MEDIDA QUE AS CHAVES VÃO SENDO DISTRIBUÍDAS
OS PONTEIROS VÃO SENDO INCREMENTADOS.
DÍGITO
0
1
2
3
4
5
6
7
8
9
FREQ.
3
2
1
3
1
4
1
2
2
1
0
3
5
6
9
10
14
15
17
19
FREQ. AC.
INDICA A POSIÇAÕ INICIAL DE CADA ESCANINHO
INDICA O NÚMERO DE OCORRÊNCIAS DAS CHAVES
{indica o dígito correspondente ao passo}
funtion parte (ch: integer; passo: 1..4);
begin
case passo of
1: parte:= ch mod 10;
2: parte:= (ch mod 100) div 10;
3: parte:= (ch mod 1000) div 100;
4: parte:= ch div 1000;
end;
end;
procedure distribuicao(c1:vet; n1:0..9999; p1: ..4)
var
c2: vet; f, fac: vet2; v: 0..9; i: 0..n1; k: 0..999
begin
for i:= o to 9 do
f[i]:= 0 {inicializa a }
{ tabela de frequências}
for i:= 1 to n1 do
begin
v:= parte(c1[i], p1);
f[v]:= f[v] + 1
end;
fac[0]:= 0;
fac[1]:= f[0];
for i:= 2 to 9 do
fac[i]:= fac[i - 1] + f[i - 1];
{fase de distribuição}
for i:= 1 to n1 do
begin
v:= parte(c1[i], p1);
k:= fac[v];
c2[k]:= c1[i];
fac[v]:= fac[v] + 1;
end;
end{distribuicao}