Aula 15 - OrdMemSecundaria_Varios Caminhos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Ordenação em 
Memória Secundária
Lívia N. Andrade
A ordenação em memória secundária (ou ordenação em memória externa) envolve arquivos compostos por um número de registros maiores que a memória interna do computador consegue armazenar.
Os métodos de ordenação externa são muito diferentes dos métodos de ordenação interna.
Em ambos, o problema é o mesmo: rearranjar os registros de um arquivo em ordem ascendente ou descendente.
A idéia consiste em ordenar arquivos de tamanho maior que a memória interna disponível.
As estruturas de dados têm de levar em conta o fato de que os dados estão armazenados em unidades de memória externa, com tempo de acesso relativamente muito mais lento do que na memória principal.
Na ordenação externa os algoritmos devem diminuir o número de acesso as unidades de memória externa.
Idéia ...
Ziviane, cap 4
3
Nas memórias externas (ex.: fitas, discos e tambores magnéticos), os dados são armazenados como um arquivo seqüencial, em que apenas um registro pode ser acessado em um dado momento. 
Essa é uma restrição forte se comparada com as possibilidades de acesso da estrutura de dados do tipo vetor.
Logo, os métodos de ordenação interna são inadequados para ordenação externa, e então técnicas de ordenação completamente diferentes devem ser utilizadas.
Fatores importantes que tornam os algoritmos para ordenação externa diferentes da ordenação interna:
Custo
Restrições de acesso aos dados
Métodos de ordenação
 Custo para acessar um item é algumas ordens de grandeza maior do que os custos de processamento na memória interna.
 O custo principal na ordenação externa está relacionado com o custo de transferir dados entre a memória interna e externa.
Fatores importantes que tornam os algoritmos para ordenação externa diferentes da ordenação interna:
Custo
Restrições de acesso aos dados
Métodos de ordenação
Existem restrições severas de acesso aos dados.
Ex.: Os itens armazenados em fita magnética só podem ser acessados de forma seqüencial. 
Os itens armazenados em disco magnético podem ser acessados diretamente, mas a um custo maior do que o custo para acessar sequencialmente, o que contra-indica o uso do acesso direto. 
Fatores importantes que tornam os algoritmos para ordenação externa diferentes da ordenação interna:
Custo
Restrições de acesso aos dados
Métodos de ordenação externa
 O desenvolvimento desses métodos é muito dependente do estado atual da tecnologia.
 A variedade de tipos de unidades de memória externa torna os métodos de ordenação dependentes de vários parâmetros que afetam seus desempenhos.
Por esta razão, veremos apenas métodos gerais de ordenação em memória externa.
Não veremos refinamentos de algoritmos
 até o nível de um programa, como C.
	
Minimizar o número de vezes que cada item é transferido entre a memória interna e externa.
Cada transferência deve ser realizada de forma tão eficiente quanto as características que os equipamentos disponíveis permitem.
Para desenvolver um método de ordenação externa eficiente:
	Método de ordenação externa mais importante: ordenação por intercalação.
Intercalar significa combinar dois ou mais blocos ordenados em um único bloco ordenado.
A intercalação é utilizada como uma operação auxiliar na ordenação.
Estratégia geral utilizada pelos métodos de ordenação externa:
Realize a 1ª passada sobre o arquivo, quebrando-o em blocos do tamanho da memória interna disponível.
Ordene cada bloco na memória interna.
Intercale os blocos ordenados, fazendo várias passadas sobre o arquivo.
Crie, a cada passada, blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
1. Realize a 1ª passada sobre o arquivo, quebrando-o em blocos do tamanho da memória interna disponível.
15 2 10 4 8 5 1 9 3 6 5 8
Arquivo de tamanho 12
Tamanho da memória = 6
1. Realize a 1ª passada sobre o arquivo, quebrando-o em blocos do tamanho da memória interna disponível.
15 2 10 4 8 5 1 9 3 6 5 8
2. Ordene cada bloco na memória interna.
 2 4 5 8 10 15
 1 3 5 6 8 9
15 2 10 4 8 5 1 9 3 6 5 8
3. Intercale os blocos ordenados, fazendo várias passadas sobre o arquivo.
4. Crie, a cada passada, blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
 2 4 5 8 10 15
 1 3 5 6 8 9
 1
3. Intercale os blocos ordenados, fazendo várias passadas sobre o arquivo.
4. Crie, a cada passada, blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
 2 4 5 8 10 15
 1 3 5 6 8 9
 1 2
3. Intercale os blocos ordenados, fazendo várias passadas sobre o arquivo.
4. Crie, a cada passada, blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
 2 4 5 8 10 15
 1 3 5 6 8 9
 1 2 3
3. Intercale os blocos ordenados, fazendo várias passadas sobre o arquivo.
4. Crie, a cada passada, blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
 2 4 5 8 10 15
 1 3 5 6 8 9
 1 2 3 4
3. Intercale os blocos ordenados, fazendo várias passadas sobre o arquivo.
4. Crie, a cada passada, blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
 2 4 5 8 10 15
 1 3 5 6 8 9
 1 2 3 4 5
3. Intercale os blocos ordenados, fazendo várias passadas sobre o arquivo.
4. Crie, a cada passada, blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
 2 4 5 8 10 15
 1 3 5 6 8 9
 1 2 3 4 5 5
3. Intercale os blocos ordenados, fazendo várias passadas sobre o arquivo.
4. Crie, a cada passada, blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
 2 4 5 8 10 15
 1 3 5 6 8 9
 1 2 3 4 5 5 6 ...
Importante saber...
Os algoritmos para ordenação externa devem reduzir o número de passadas sobre o arquivo.
Como a maior parte do custo é para as operações de entrada/saída de dados na memória interna, uma boa medida de complexidade de um algoritmo de ordenação por intercalação é o número de vezes que um item é lido ou escrito na memória auxiliar.
Os bons métodos de ordenação geralmente envolvem no total menos do que dez passadas sobre o arquivo. 
Intercalação Balanceada de Vários Caminhos
	Considere um arquivo armazenado em uma fita de entrada:
Objetivo:
 Ordenar os 22 registros e colocá-los em uma fita de saída.
Os registros são lidos um após o outro.
Considere uma memória interna com capacidade para três registros.
Considere que esteja disponível seis unidades de fita magnética.
I N T E R C A L A C A O B A L A N C E A D A
22
Intercalação Balanceada de Vários Caminhos
	A intercalação possui duas fases:
Fase de criação dos blocos ordenados;
Fase de intercalação dos blocos ordenados.
23
Intercalação Balanceada de Vários Caminhos
	Fase de criação dos blocos ordenados:
I N T E R C A L A C A O B A L A N C E A D A
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
 I N T
24
Intercalação Balanceada de Vários Caminhos
	Fase de criação dos blocos ordenados:
I N T E R C A L A C A O B A L A N C E A D A
C E R
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
C E R
25
Intercalação Balanceada de Vários Caminhos
	Fase de criação dos blocos ordenados:
I N T E R C A L A C A O B A L A N C E A D A
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
A A L
A A L
C E R
26
Intercalação Balanceada de Vários Caminhos
	Fase de criação dos blocos ordenados:
I N T E R C A L A C A O B A L A N C E A D A
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
A C O
A C O
A A L
C E R
27
Intercalação Balanceada de Vários Caminhos
	Fase de criação dos blocos ordenados:
I N T E R C A L A C A O B A L A N C E A D A
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
A B L
A B L
A C O
A A L
C E R
28
Intercalação Balanceada de Vários Caminhos
	Fase de criação dos blocos ordenados:
I N T E R C A L A C A O B A L A N C E A D A
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
A C N
A C N
A B L
A C O
A A L
C E R
29
Intercalação Balanceada de Vários Caminhos
	Fase
de criação dos blocos ordenados:
I N T E R C A L A C A O B A L A N C E A D A
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
A D E
A D E
A C N
A B L
A C O
A A L
C E R
30
Intercalação Balanceada de Vários Caminhos
	Fase de criação dos blocos ordenados:
I N T E R C A L A C A O B A L A N C E A D A
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
A
A
A D E
A C N
A B L
A C O
A A L
C E R
31
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
O primeiro registro de cada fita é lido
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I N T
I C A
A
A D E
A C N
A B L
A C O
A A L
C E R
32
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
O primeiro registro de cada fita é lido
Retire o registro contendo a menor chave
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I C A
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
Menor chave
33
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
O primeiro registro de cada fita é lido
Retire o registro contendo a menor chave 
Armazene-o em uma fita de saída e leia um novo registro
				 	da fita de onde o registro
					retirado é proveniente
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I C A
A 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
34
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I C L
A A 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
35
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I E L
A A C 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
36
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
I R L
A A C E 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
37
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
O primeiro registro de cada fita é lido
Retire o registro contendo a menor chave 
Armazene-o em uma fita de saída e leia um novo registro
				 	da fita de onde o registro
					retirado é proveniente
					4. Ao ler o terceiro registro de
					 um dos blocos, sua fita fica
					 inativa
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
N R L
A A C E I 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
38
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
N R
A A C E I L 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
39
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
T R
A A C E I L N 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
40
Intercalação Balanceada de Vários Caminhos
	Fase de intercalação – Primeira passada:
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
T
A A C E I L N R 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
41
	Fase de intercalação – Primeira passada:
O primeiro registro de cada fita é lido
Retire o registro contendo a menor chave 
Armazene-o em uma fita de saída e leia um novo registro
				 	da fita de onde o registro
					retirado é proveniente
					4. Ao ler o terceiro registro de
					 um dos blocos, sua fita fica
					 inativa
					5. Neste instante um bloco de
					 nove registros ordenados foi
					 formado na fita de saída.
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
42
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
A A A
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
5. Repita o processo para os blocos restantes, armazenando em uma nova fita.
43
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C A A
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A
44
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C B A
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A
45
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C B C
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A A
46
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C L C
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A A B
47
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
O L C
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A A B C
48
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
O L N
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A A B C C
49
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
O N
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A A B C C L
50
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
O 
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A A B C C L N
51
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
 
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A A B C C L N O
52
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
 
A A C E I L N R T 
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
	Fase de intercalação – Primeira passada:
A A D E
A A A B C C L N O
	 Resultado da primeira passada da segunda etapa
53
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
A A A
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
54
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
A A A
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A 
55
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
A A A
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A A 
56
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
A A A
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A A A 
57
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C A A
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A A A A 
58
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C A A
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A A A A A 
59
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C A D
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A A A A A A 
60
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C B D
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A A A A A A A 
61
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
C C D
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A A A A A A A B 
62
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
E C D
A A C E I L N R T 
	Fase de intercalação – Segunda passada:
A A D E
A A A B C C L N O
A A A A A A A B C 
63
Intercalação Balanceada de Vários Caminhos
Fita 1
Fita 2
Fita 3
Fita 4
Fita 5
Fita 6
A A C E I L N R T 
	Fase de intercalação
– Segunda passada:
A A D E
A A A B C C L N O
A A A A A A A B C C C D E E I L L N N O R T 
	 Resultado da segunda passada da segunda etapa
64
Quantas passadas são necessárias para ordenar um arquivo de tamanho arbitrário?
Seja n o número de registros do arquivo;
Suponha que cada registro ocupa m palavras na memória interna;
A primeira etapa produz n/m blocos ordenados;
Seja P(n) o número de passadas para a fase de intercalação;
Seja f o número de fitas utilizadas em cada passada;
Assim:
Quantas passadas são necessárias para ordenar um arquivo de tamanho arbitrário?
No exemplo utilizado: 
n = 22
m = 3
f = 3 P(n) = log 3
			 P(n) = log 3 8 = 2
22 
 3
3x = 8
x=2
Outra estratégia: usar f + 1 fitas
Para uma intercalação-de-3-caminhos foram utilizadas 6 fitas, ou seja, foram utilizadas 2f fitas para uma intercalação-de-f-caminhos.
É possível usar apenas f + 1 fitas:
Encaminhe todos os blocos para uma única fita.
Redistribua estes blocos entre as fitas de onde eles foram lidos.
O custo envolvido é uma passada a mais em cada intercalação.
Outra estratégia: usar f + 1 fitas
A intercalação dos blocos a partir das fitas 1, 2 e 3 seria toda dirigida para a fita 4.
Fita 1
Fita 2
Fita 3
Fita 4
I N T
A
A D E
A C N
A B L
A C O
A A L
C E R
A A C E I L N R T 
A A D E
A A A B C C L N O
Outra estratégia: usar f + 1 fitas
A intercalação dos blocos a partir das fitas 1, 2 e 3 seria toda dirigida para a fita 4.
Ao final, o segundo e o terceiro blocos ordenados de nove registros seriam transferidos de volta para as fitas 1 e 2.
Fita 1
Fita 2
Fita 3
Fita 4
A A C E I L N R T 
A A D E
A A A B C C L N O
Outra estratégia: usar f + 1 fitas
A intercalação dos blocos a partir das fitas 1, 2 e 3 seria toda dirigida para a fita 4.
Ao final, o segundo e o terceiro blocos ordenados de nove registros seriam transferidos de volta para as fitas 1 e 2.
E a ordenação final ficaria na fita 3.
Fita 1
Fita 2
Fita 3
Fita 4
A A C E I L N R T 
A A D E
A A A B C C L N O
A A A A A A A B C C C D E E I L L N N O R T 
Mostre os passos para a ordenação externa dos número inteiros com as especificações abaixo, considerando o método de intercalação balanceada de vários caminhos (estratégia geral com blocos de tamanho fixo).
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Memória interna para 5 registros
8 unidades de fita (intercalação-de-4-caminhos)
Exercício 31 da lista
No exercício anterior, se estivessem disponíveis apenas 5 fitas, mostre como seria a intercalação usando 4+1 fitas.
Exercício 32 da lista
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
13 23 45 67 89
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
12 21 43 65 98
12 21 43 65 98
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
12 43 55 66 99
12 21 43 65 98
12 43 55 66 99
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
32 37 59 61 62
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
4 5 7 8 11
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
4 5 7 8 11
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
10 20 40 60 90
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
4 5 7 8 11
10 20 40 60 90
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
2 3 6 8 30
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
4 5 7 8 11
10 20 40 60 90
2 3 6 8 30
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
23 26 62 76 98
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
4 5 7 8 11
10 20 40 60 90
2 3 6 8 30
23 26 62 76 98
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
 0 8 9 13 28
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
4 5 7 8 11
10 20 40 60 90
2 3 6 8 30
23 26 62 76 98
0 8 9 13 28
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
18 19 21 25 27
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
4 5 7 8 11
10 20 40 60 90
2 3 6 8 30
23 26 62 76 98
0 8 9 13 28
18 19 21 25 27
Arquivo com os dados (53 registros):
13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Quebrar em blocos de tamanho 5
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
37 71 73
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
4 5 7 8 11
10 20 40 60 90
2 3 6 8 30
23 26 62 76 98
0 8 9 13 28
18 19 21 25 27
37 71 73
Intercalar os blocos ordenados, fazendo várias passadas sobre o arquivo e criando blocos ordenados cada vez maiores.
Resolvendo o exercício 31
Fita 1
Fita 2
Fita 3
Fita 4
13 23 45 67 89
13 12 12 32
12 21 43 65 98
12 43 55 66 99
32 37 59 61 62
4 5 7 8 11
10 20 40 60 90
2 3 6 8 30
23 26 62 76 98
0 8 9 13 28
18 19 21 25 27
37 71 73
Fita 5
Fita 6
Fita 7
Fita 8
Bibliografia consultada
Livro:
Projeto de algoritmos com implementações em PASCAL e C – Nivio Ziviani