Intercalação balanceada
Definição
A intercalação balanceada é um algoritmo de ordenação externa, para intercalar os elementos de dois ou mais caminhos (que seriam os nossos arquivos) de forma a preservar sua ordem original. O objetivo do algoritmo é produzir um único caminho ordenado que contenha todos os elementos dos caminhos de entrada em sua ordem original, minimizando o número de comparações necessárias para produzir o caminho final. Dentro dos caminhos, também separamos os registros em blocos, que podem ter um número máximo de registros.
Exemplo
Aqui está um exemplo de como o algoritmo de intercalação balanceada funciona:
Obs.: Para exemplos temos cinco registros por bloco e dois caminhos.
Entrada: Lista com vários números fora de ordem.
1
5
3
2
7
13
23
235
3
9
34
55
1634
29
1 - Separe a lista de números em blocos
2 - Ordene os blocos
3 - Distribua os blocos pelos caminhos de forma intercalada nos caminhos.
Obs.: O espaço branco é a separação entre um bloco e outro.
1
2
3
5
7
34
55
1634
29
13
23
235
3
9
4 - Faça leitura dos blocos dos caminhos, até o ponteiro do caminho chegar no final. Você irá ler os blocos em grupos, e irá colocar os registros dentro dos blocos de forma ordenada em um novo caminho.
Neste caso temos dois grupos: o primeiro que é formado pelo primeiro bloco do primeiro e segundo caminho, e o segundo grupo só tem o segundo bloco do primeiro caminho.
Antes
1
2
3
5
7
34
55
1634
29
13
23
235
3
9
Depois
1
2
3
3
5
7
9
13
23
253
29
34
55
1634
5 - Repita o passo quatro, até que o número de blocos seja igual ou menor do que o número de caminhos, dessa forma só um caminho novo será gerado e esta será a sua lista ordenada.
Saída: Lista com vários números ordenados.
1
2
3
3
5
7
9
13
23
29
34
55
235
1634
Nesta seção, você irá encontrar um exemplo em como fazer uma implementação simples do algoritmo usando números como o registro que queremos ordenar. Também recomendo bastante os vídeos do professor Marcos Kutova para a explicação do algoritmo além do custo computacional do mesmo.
Bons estudos!
Last updated