Classificação Externa
Inhaúma Neves Ferraz
Departamento de Ciência da Computação
Universidade Federal Fluminense
[email protected]
Sumário
Introdução e Conceito
Geração de Partições Classificadas
Intercalação das Partições
Classificadas
2
Introdução e Conceito
Aplicações usando Classificação
Os programas desenvolvidos para algumas áreas
de aplicação, como processamento de dados
comercial, podem gastar a maior parte do seu
tempo de computação em atividades de
classificação e/ou pesquisas para produzir
relatórios, tabelas formatadas, etc.
Calcula-se que cerca da quarta parte de todo o
tempo consumido em máquina seja gasto em
atividades de classificação
4
Tipos de Classificação
A classificação de registros de um arquivo
pode ser de dois tipos:
Classificação interna: com utilização
exclusiva de memória principal
Classificação externa: com utilização de
memória secundária
5
Conceito de Classificação Externa
Classificação interna: lista de registros pode ser mantida inteiramente
na memória principal durante a classificação
Classificação externa: há mais registros a serem classificados do que
é possível manter na memória principal em qualquer momento
Na classificação externa o parâmetro fundamental é o número de
operações de entrada e saída.
Pode-se classificar um arquivo sobre ele mesmo ou utilizar
armazenamento auxiliar

A classificação sobre ele mesmo poupa espaço porém corre o risco de
inconsistência em caso de término anormal de processamento
A Classificação Externa divide os arquivos em pequenas frações que
são ordenadas e intercaladas em dois estágios:


Classificação
Intercalação.
6
Modelo da Classificação Externa
7
Estágio de Classificação
Uma partição é uma seqüência classificada
de n registros.
Registros são lidos de arquivos de entrada
(não classificados) e de partições
(classificadas)
Estes registros são classificados e gravados
em arquivos de saída ou partições
classificadas.
8
Geração de Partições Classificadas
Métodos do Estágio de Classificação
Métodos
Classificação interna
 Seleção com substituição
 Seleção natural.

Considera-se que a memória principal tenha
capacidade para armazenar M registros do
arquivo a classificar
10
Classificação Interna
Classificação Interna
Critério fundamental de eficiência da classificação
interna: número de comparações entre chaves de
registros
Consiste na leitura de MAX_MEMO registros
para a memória, classificação desses registros por
qualquer processo de classificação interna e
gravação desses registros classificados em uma
partição.
Todas as partições classificadas contém
MAX_MEMO registros, exceto, talvez, a última
12
Processos de classificação
interna
Troca: bubble sort, bubble com
“flag”, shaker sort, quick sort
Seleção: direta, heap sort,
Inserção: simples, shell sort
Outros: merge sort, etc.
13
Visão geral da Geração de partições
Classificadas
14
Seleção com Substituição
Seleção com Substituição
1.
2.
3.
4.
Aproveita a possível classificação parcial do arquivo de entrada
Algoritmo:
Ler MAX_MEMO registros do arquivo para a memória
Selecionar, no “array” em memória, o registro com menor chave
Gravar na partição de saída o registro com menor chave
Substituir, no “array” em memória, o registro gravado na saída pelo
próximo registro do arquivo de entrada
1.
Caso a chave deste último seja menor do que a chave recém-gravada,
considerá-lo "congelado" e ignorá-lo no restante do processamento
5. Caso existam em memória registros não "congelados" voltar ao passo
dois
6. Caso contrário, fechar a partição de saída, "descongelar" os registros
"congelados", abrir nova partição de saída e voltar ao passo dois
Em média, o tamanho das partições obtidas pelo processo de seleção
com substituição é de 2 * MAX_MEMO
16
Seleção Natural
Seleção Natural
Desvantagem da seleção com substituição - no final da
partição grande parte do espaço em memória principal está
ocupado com registros “congelados”
Na seleção natural, reserva-se um espaço de memória
secundária ("o reservatório") para abrigar os registros
"congelados" num processo de substituição
A formação de uma partição se encerra quando o
reservatório estiver cheio ou quando terminarem os
registros de entrada
Para a memória comportando MAX_MEMO registros
supõe-se um reservatório comportando max_reserv
registros
Para MAX_MEMO= max_reserv o comprimento médio
das partições é de MAX_MEMO * e, onde e = 2,718... .
18
Comparação dos Processos
A classificação interna gera as menores partições
mas simplifica o estágio de intercalação por usar
partições de mesmo comprimento
Os processos de seleção exigem intercalação mais
elaborada, porém, gerando partições maiores,
reduzem o tempo total de processamento
A seleção natural sofre o ônus adicional de utilizar
mais operações de entrada e saída
19
Exemplo
Considere-se ser necessário classificar um
arquivo cujas chaves de registros estejam
representadas a seguir
Suponha-se a possibilidade de manter na
memória, simultaneamente, 6 registros
Pede-se exibir as partições que seriam
obtidas utilizando cada um dos métodos de
geração de partições
20
Chaves dos registros a classificar
29
56
5
54
3
14
20
19
78
60
76
26
50
43
36
75
4
55
38
47
59
21
25
51
31
6
65
66
32
80
7
22
57
58
74
49
77
13
48
11
12
73
46 10 18
16 8 15
30 17 9
79 27 1
21
Partições obtidas por
classificação interna
Memória
29
Área de trabalho
14 76 75 59
Memória
7
74
48
46
10
18
7
10
18
46
48
74
Memória
56
20
26
4
21
65
4
20
21
26
56
65
Memória
22
49
11
16
8
15
8
11
15
16
22
49
Memória
5
19
50
55
25
66
5
19
25
50
55
66
Memória
57
77
12
30
17
9
9
12
17
30
57
77
Memória
54
78
43
38
51
32
32
38
43
51
54
78
Memória
58
13
73
79
27
1
1
13
27
58
73
79
Memória
3
60
36
47
31
80
3
31
36
47
60
80
6
6
Partições obtidas
14 29 59 75
76
22
Partições obtidas por seleção com substituição
Registros
3 substituição
a
2 substituição
a
1 substituição
Memória
a
a
2 substituição
a
1 substituição
Memória
a
3 substituição
a
2 substituição
a
1 substituição
Memória
a
3 substituição
a
2 substituição
a
1 substituição
Memória
a
1 substituição
Memória
1
Área de trabalho
2
3 4
5
6
20
10 18
74
46 48 4 26 56 7
29 14 76 75 59 6
4
5
Partições obtidas
6
7 8
9 10 11 12 13 14 15
1
2
3
6
7
14 29 46 48 59 74 75 76
a
A 1 partição ficou com 10 registros
19 16 11
15
65 22 21 8
5 49
10 18 4 26 56 20
4
10 18 20 21 22 26 49 56 65
a
A 2 partição ficou com 10 registros
43
78 9 12 17 30 54
77 57 25 55 50 66
19 16 11 8
5 15
5
8
60
36 73 27 13 3
79 38 51 32 58 1
43 9 12 17 30 54
9
12 17 30 32 38 43 51 54 58 73 79
a
A 4 partição ficou com 12 registros
80 31 47
36 60 27 13 3 1
1
3
11 15 16 19 25 50 55 57 66 77 78
a
A 3 partição ficou com 13 registros
13 27 31 36 47 60 80
a
A 5 partição ficou com 9 registros
Legenda
Registros congelados
Divisão de regiões na tabela
23
Partições obtidas por classificação seleção natural
Registros
2 substituição
a
1 substituição
Memória
Reservatório
a
Área de trabalho
2 3 4 5
1
6
56
74
46 48
7
29 14 76 75 59 6
10 18 20 26 4 21
4
Partições obtidas
6 7 8 9 10 11 12 13 14 15
1
2
3
5
6
7
14 29 46 48 56 59 74 75 76
a
A 1 partição ficou com 11 registros
a
1 substituição
Memória
Reservatório
a
3 substituição
a
2 substituição
a
1 substituição
Memória
Reservatório
a
2 substituição
a
1 substituição
Memória
Reservatório
a
1 substituição
Memória
Reservatório
22 49
65
10 18 20 26 4 21
11 16 8 15 5 19
4
10 18 20 21 22 26 49 65
a
A 2 partição ficou com 9 registros
54
30
78
25 57 55 66 50 77
11 16 8 15 5 19
12 17 9 43 38 51
5
8
11 15 16 19 25 30 50 54 55 57 66 77 78
a
A 3 partição ficou com 15 registros
79
58 73 32 47 60
12 17 9 43 38 51
13 27 1 3 36 31
9
12 17 32 38 43 47 51 58 60 73 79
a
A 4 partição ficou com 12 registros
80
13 27 1
3
36 31
1
3
13 27 31 36 80
a
A 5 partição ficou com 7 registros
24
Intercalação das Partições
Classificadas
Generalidades
Consiste na transformação de um conjunto de seqüências
de registros, classificadas por determinado critério, em
uma única seqüência contendo todos os registros de todas
as seqüências originais do conjunto, sendo esta seqüência
única classificada pelo mesmo critério de classificação das
seqüências iniciais
Considere-se a existência de R partições geradas pelo
processo de geração de partições
Seria ideal poder intercalar todas as partições de uma só
vez e obter o arquivo classificado

Contudo, os Sistemas Operacionais estabelecem número máximo
de arquivos abertos simultaneamente, número esse que pode ser
bem menor do que o número de partições existentes
A intercalação vai exigir uma série de fases durante cada
qual registros são lidos de um conjunto de arquivos e
gravados em outro (partições)
26
Estágio de Intercalação
Estratégias de distribuição e intercalação:
1. Intercalação balanceada de N caminhos.
2. Intercalação ótima.
3. Intercalação polifásica.
27
Medida de Eficiência
Uma medida de eficiência de estágio de
intercalação é dada pelo número de passos sobre
os dados, assim definido:
Numero total de registros lidos
Numero de passos 
Numero total de registros no arquivo classficado
O número de passos é o número médio de vezes
que um registro é lido (ou gravado) durante o
estágio de intercalação.
28
Intercalação balanceada de N
caminhos
Intercalação Balanceada de n caminhos (1)
Arquivos disponíveis são distribuídos, tão
equilibradamente quanto possível, em dois
conjuntos
Partições inicias são distribuídas, tão
equilibradamente quanto possível nos arquivos de
um dos conjuntos
Durante cada fase da intercalação são lidos
registros dos arquivos no conjunto que recebeu as
partições iniciais (conjunto de entrada) e o
resultado das intercalações é gravado nos arquivos
do conjunto de saída, ciclicamente
30
Intercalação Balanceada de n caminhos (2)
No final de cada fase, o conjunto de entrada tornase o conjunto de saída e vice-versa
O balanceamento do processo baseia-se em
colocar nos arquivos de entrada aproximadamente
o mesmo número de registros
Considerando-se F possíveis arquivos abertos, um
dos conjuntos conterá os arquivos numerados de 1
a N e o outro conterá os arquivos numerados de
N+1 até F
Define -se uma variável
conjunto_inicial_de_entrada para identificar qual
é o conjunto de entrada em cada fase
31
Intercalação Balanceada de n caminhos (3)
A intercalação termina quando, em uma
fase, grava-se apenas uma partição. O
número de passos é igual ao número de
fases
A intercalação utiliza no máximo F/2
caminhos, quando o ideal seria F-1
caminhos
Pode ocorrer que partições sejam copiadas
de um arquivo para outro sem qualquer
processamento
32
Exemplo – Intercalação Balanceada (1)
Considere-se a existência de 20 partições
classificadas cada qual com 100 registros a
intercalar
Supõe-se ser possível manter abertos
simultaneamente 4 arquivos
A notação i x j significa i partições de j
registros cada
33
Exemplo – Intercalação Balanceada (2)
Instante
INICIALMENTE
Após a fase 1
Após a fase 2
Após a fase 3
Após a fase 4
Após a fase 5
Arquivo 1 Arquivo 2 Arquivo 3
Arquivo 4
10 x 100
10 x 100
5 x 200
5 x 200
3 x 400
2 x 400
1x800,1x400 1 x 800
1 x 1600
1 x 400
1 x 2000
34
Intercalação Ótima
Intercalação Ótima
Partições iniciais gravadas em arquivos, cada qual com
uma única partição
Durante cada fase do algoritmo, as F-1 menores partições
são intercaladas e gravadas em uma partição ou arquivo de
saída
Do conjunto inicial de partições removem-se as partições
intercaladas e a ele agrega-se a partição gerada na
intercalação
Termina quando este conjunto tiver apenas uma partição.
Cada partição de conter seu número de registros, ou o
Sistema Operacional deve determinar o tamanho dos
arquivos para verificar quais deles devem ser intercalados
em cada momento (os F-1 menores)
36
Exemplo – Intercalação Ótima (1)
Considere-se a existência de 20 partições
classificadas cada qual com 100 registros a
intercalar
Supõe-se ser possível manter abertos
simultaneamente 4 arquivos
Será utilizada a notação x:y significando a
partição de número x contendo y registros
37
Exemplo – Intercalação Ótima (2)
Fase Arquivo1 Arquivo2 Arquivo3 Arquivo4 N. de leituras
1
1:100
2:100
3:100
21:300
300
2
4:100
5:100
6:100
22:300
300
3
7:100
8:100
9:100
23:300
300
4
10:100
11:100
12:100
24:300
300
5
13:100
14:100
15:100
25:300
300
6
16:100
17:100
18:100
26:300
300
7
19:100
20:100
21:300
27:500
500
8
22:300
23:300
24:300
28:900
900
9
25:300
26:300
27:500
29:1100
1100
10
28:900
29:1100
---------- 30:2000
2000
TOTAL
6300
Número de passos 
6300
 3,15
2000
38
Intercalação Polifásica
Intercalação Polifásica (1)
Para eliminar as cópias de partições sem
que elas sejam intercaladas pode-se fazer
sempre intercalações de ordem F-1
A Intercalação polifásica opera desta
maneira, exigindo entretanto que a fase de
classificação interna distribua as partições,
entre os F-1 arquivos disponíveis para
entrada, de maneira especialmente
determinada para otimização do algoritmo
40
Intercalação Polifásica (2)
Considere-se a notação i x j representando i
partições e j registros
Em cada fase do algoritmo intercalam-se F1 arquivos até chegar ao final de qualquer
uma delas
Nesse ponto, interrompe-se a fase deixando
o restante dos arquivos para a fase seguinte
41
Exemplo inicial de Intercalação Polifásica
Considere-se , por exemplo, a intercalação de
31 partições com F = 4
Instante
Inicialmente
Após fase 1
Após fase 2
Após fase 3
Após fase 4
Após fase 5
Arq1
13 X 100
6 X 100
2 X 100
--------1 X 1700
---------
Arq2
11 X 100
4 X 100
-------2 X 900
1 X 900
---------
Nú mero de passos 
Arq3
7 X 100
--------4 X 500
2 X 500
1 X 500
---------
Arq4
N. de leituras
---------------7 X 300
2100
3 X 300
2000
1 X 300
1800
-------1700
1 X 3100
3100
TOTAL
10700
10700
 3,45
3100
42
Intercalação Polifásica (3)
A intercalação polifásica para ser otimizada necessita
de uma distribuição consistente de partições iniciais
Considere-se, por exemplo, F = 4

Na penúltima fase os 3 primeiros arquivos conterão 1, 1 , 1
partições
Em geral, se em uma fase existem (a, b, c) partições,
na fase anterior existiam (a+b,a+c,a) partições
Após a intercalação são produzidos a partições,
sendo a = min (a+b ; a+c ; a)
43
Intercalação Polifásica (4)
O comportamento ótimo do processo ocorre
quando o número total de partições iniciais
pertence a uma série de Fibonacci
generalizada.
Ti  1 ........ i  F
;
Ti 
i 1

k i  F 1
Tk
........i  F
Para F = 4, os primeiros termos da série
são: 1 , 1 , 1 , 3 , 5 , 9 , 17 , 31 , 57 , ... .
44
Caso particular e caso geral
A intercalação polifásica pode ocorrer em
duas situações:
Caso particular mais favorável quando o
número de partições classificadas a intercalar
usando F arquivos pertence à Série de
Fibonacci de ordem F
 Caso geral quando o número de partições não
pertence àquela série

45
Algoritmo do caso particular
A partir do valor de F, busca-se a configuração final (1, 1, 1, ..., 1, 0) e
recupera-se as anteriores pelo esquema anteriormente exibido
a = min (a+b ; a+c ; a)
Para F = 4 o que se obtém é
46
Tabelas alvo e de vazios (1)
O algoritmo da distribuição das partições pelos F - 1
arquivos utiliza duas tabelas auxiliares, cada qual
com F colunas e sempre com última coluna contendo
o valor zero:


Tabela de alvos indicando quantas partições serão
necessárias para completar uma fase de distribuição de
partições entre os arquivos
Tabela de vazios indicando quantas partições poderão ser
gravadas em cada arquivo para completar a fase de
distribuição de partições corrente
47
Tabelas alvo e de vazios (2)
Tabela de alvos



A primeira linha, ou primeiro nível, da tabela de alvos de ordem 4 contém
1, 1, 1, 0 significando que, para ordem 4, se houver uma partição no
arquivo 1, uma partição no arquivo 2 e uma partição no arquivo 3 a
situação é ótima para a eficiência do método de intercalação polifásica
A soma dos elementos de cada linha pertence a uma série de Fibonacci de
ordem F, sendo para o primeiro nível o termo de ordem F, para o segundo
nível o termo de ordem F + 1 e assim sucessivamente
As tabelas alvo não são atualizadas nem consultadas diretamente durante o
distribuição de partições
Tabela de vazios


Para passar da tabela alvo de nível i para o nível i + 1 existe uma tabela de
diferenças ou tabela de vazios de nível i
As tabelas de vazios são consultadas e atualizadas controlando a
distribuição de partições
48
Ordem de Intercalação Polifásica (1)
De uma maneira geral, supondo F = 4 o quarto arquivo seria reservado
para obter o resultado das intercalações e a distribuição de partições
nos primeiro, segundo e terceiro arquivos seria a seguinte
Nível Tabelas
1
A 1,1,1,0
V 1,1,1,0
2
A 2,2,1,0
V 1,1,0,0
3
A 4,3,2,0
V 2,1,1,0
4
A 7,6,4,0
V 3,3,2,0
5
A 13,11,7,0
V 6,5,3,0
Ordem de gravação
1,2,3
1,2
1,1,2,3
1,2,1,2,3,1,2,3
1, 1, 2, 1, 2, 1, 2,3,1,2,3,1,1,1
49
Ordem de Intercalação Polifásica (2)
Nível Tabelas
1
A 1,1,1,0
V 1,1,1,0
2
A 2,2,1,0
V 1,1,0,0
3
A 4,3,2,0
V 2,1,1,0
4
A 7,6,4,0
V 3,3,2,0
5
A 13,11,7,0
V 6,5,3,0
Ordem de gravação
1,2,3
1,2
1,1,2,3
1,2,1,2,3,1,2,3
1, 1, 2, 1, 2, 1, 2,3,1,2,3,1,1,1
50
Caso Geral (1)
A melhor intercalação polifásica ocorre quando o número
de partições pertence a uma série de Fibonacci.
O algoritmo da distribuição das partições pelos F - 1
arquivos funciona em diversos níveis.


No primeiro nível, distribuem-se partições buscando uma tabela
alvo cuja soma de linhas pertence a uma série de Fibonacci (termo
de ordem F - 1)
No segundo nível a tabela alvo tem como soma da linha o termo da
ordem F da mesma série e assim sucessivamente
Para passar da tabela alvo de nível i para o nível i + 1
existe uma tabela de diferenças ou tabela de vazios de
nível i
51
Caso Geral (2)
A tabela de vazios é decrementada cada vez
que se grava uma partição nos arquivos de
entrada correspondentes.
Quando uma linha ou nível da tabela de
vazios só contém zeros é porque foi atingida
a linha correspondente da tabela alvo e
incrementa-se o nível da distribuição para o
prosseguimento do processo.
52
Exemplo – Intercalação Polifásica (1)
Considere-se a notação i x j representando i
partições e j registros
Em cada fase do algoritmo intercalam-se F1 arquivos até chegar ao final de qualquer
uma delas
Nesse ponto, interrompe-se a fase deixando
o restante dos arquivos
53
Exemplo – Intercalação Polifásica (2)
Instante
Inicialmente
Após fase 1
Após fase 2
Após fase 3
Após fase 4
Após fase 5
Arq1
13 X 100
6 X 100
2 X 100
--------1 X 1700
---------
Arq2
11 X 100
4 X 100
-------2 X 900
1 X 900
---------
Arq3
7 X 100
--------4 X 500
2 X 500
1 X 500
---------
Arq4
N. de leituras
---------------7 X 300
2100
3 X 300
2000
1 X 300
1800
-------1700
1 X 3100
3100
TOTAL
10700
10700
Nú merode passos 
 3,45
3100
54
Outro Exemplo – Intercalação
Polifásica (1)
Considere-se 20 partições
Como 20 não pertence à série de Fibonacci
generalizada (1, 1, 1, 3, 5, 9, 17, 31, ...),
acrescentam-se 11 partições vazias
Supõe-se ser possível manter abertos
simultaneamente 4 arquivos
55
Outro Exemplo – Intercalação
Polifásica (3)
Situação
Após a fase 4
(11 leituras)
Após a fase 5
(20 leituras)
Arquivo 1
PARTrgkabilpfhg
Partições nos arquivos
Arquivo 2 Arquivo 3
PARTsjmden
Arquivo 4
PARTotc
PARTabcdefghijklmnopqrst
Número de leituras = (10 + 9 + 12 + 11 + 20 ) / 20 = 62 / 20 = 3,1
56
Outro
Exemplo –
Intercalação
Polifásica (2)
Situação
Inicialmente
Arquivo 1
Arquivo 2
Arquivo 3
VAZIA
VAZIA
VAZIA
VAZIA
PARTa
PARTd
PARTf
PARTg
PARTj
PARTl
PARTo
PARTr
PARTs
VAZIA
VAZIA
VAZIA
VAZIA
PARTb
PARTe
PARTh
PARTk
PARTm
PARTp
PARTt
VAZIA
VAZIA
VAZIA
PARTc
PARTi
PARTn
PARTq
Após a fase 1
(10 leituras)
PARTg
PARTj
PARTl
PARTo
PARTr
PARTs
PARTk
PARTm
PARTp
PARTt
Após a fase 2
(9 leituras)
PARTr
PARTs
Após a fase 3
(12 leituras)
PARTrgkabi
PARTsjmden
Arquivo 4
VAZIA
VAZIA
VAZIA
PARTc
PARTabi
PARTden
PARTfhq
PARTgk
PARTjm
PARTlp
PARTotc
PARTabi
PARTden
PARTfhq
PARTlp
PARTotc
PARTfhq
57
Intercalação Polifásica
(Parte do algoritmo - distribuição)
vazios[ponteiro]  vazios[ponteiro] - 1
/* Geração e distribuição das demais partições pelos arquivos de trabalho */
i  i + 1
Abrir (arquivo = nome_do_array[i]) para leitura
Enquanto ((i≠ número_de_partições) e (não EOF(ent)))
/* Escolha do arquivo de gravação da partição corrente */
Se (vazios[ponteiro] < vazios[ponteiro +1])
então
/* Esta condição significa que o número de vazios referente ao arquivo
corrente está menor do que o número de vazios de seu sucessor e que, portante
as novas gravações de partições devam ocorrer em seu sucessor */
ponteiro  ponteiro+1
senão
Se (vazios[ponteiro] = 0)
então
/* Nesta situação não há mais vazios e deve-se mudar de
alvo */
nível  nível+1
temp  alvos[1]
Para
k variando de 1 até número_de_arquivos - 1
vazios[k]  temp+ alvos[k+1] - alvos[k]
alvos[k]  temp + alvos[k+1]
Fim do Para
Fim do Se
/* (vazios[ponteiro] = 0)
*/
ponteiro  1
/* as gravações iniciam-se no primeiro arquivo
*/
Fim do Se
/*
(vazios[ponteiro] < vazios[ponteiro +1])
*/
58
Intercalação Polifásica
(Parte do algoritmo - gravação)
/*
Geração de uma partição e gravação em arq[ponteiro]
*/
chave(auxiliar)  chave_válida
Repetir
Ler de (arquivo = nome_do_array[i])) auxiliar
Se (EOF(nome_do_array[i]))
então
chave(auxiliar)  HIGH_VALUE
Fim do Se
Gravar em (arquivo = arq[j]) auxiliar
até (chave(auxiliar) = HIGH_VALUE)
Fechar (arquivo = nome_do_array[i])
vazios[ponteiro]

vazios[ponteiro] - 1
i  i + 1
Abrir (arquivo = nome_do_array[i]) para leitura
Fim do Enquanto /* (i número_de_partições) e (não EOF(ent)) */
/* Fechamento dos arquivos que receberam as partições */
59
Intercalação Polifásica
(Parte do algoritmo - intercalação)
/*intercalação*/
Enquanto (nível > 0)
Repetir
* até EOF(arq[número_de_arquivos-1])) */
sem_vazios  0
Para
i variando de 1 até número_de_arquivos - 1
Se (vazios[i]) = 0
então
sem_vazios  sem_vazios +1
Fim do Se
Fim do Para
Se (sem_vazios = 0)
então
/* Todos os arquivos tem partições vazias
Para
i variando de 1 até número_de_arquivos-1
vazios[i]  vazios[i] - 1
Fim do Para
vazios[número_de_arquivos]  vazios[número_de_arquivos] + 1
/* A saída ganha partição vazia */
senão /* Existem arquivos com partições prontas para intercalar
Para
i variando de 1 até número_de_arquivos-1
Se (vazios[i])  0
então
vazios[i]  vazios[i] - 1
Fim do Se
Fim do Para
Fim do Se
*/
*/
60