AEDs III 20/06/2011

CONCEITO:
Intercalação Balanceada
É um metodo de ordenação que considera um disco em forma de fitas, e uma memória com espaço de armazenamento N.

A ideia é a seguinte, voce carrega N letras do vetor e ordene-as da forma que preferir.
Então guarde-as em uma fita 1%N, repita o processo com N letras seguintes e armazene na fita 2%N, e assim por diante armazenando na fita i%N as N ultimas letras lidas
já ordenadas.

dessa forma considerando memória de tamanho 3 e a palavra intercalacaobalanceada
teremos as seguintes fitas:

1: int aco ade
2: cer abl a
3: aal acn

Repare agora que a cada 3 letras escritas nas fitas já estão parcialmente ordenadas.
Se eu escolher sempre entre as menores letras das fitas a menor delas e ir escrevendo em outra quarta fita, terei um vetor com 9 letras ordenadas.
repito isso para o segundo bloco de N letras nas 3 fitas, ou seja, intercalo de maneira ordeanda as substrings: aco, abl e acn,
e por fim faço o mesmo com o ultimo bloco.

terei então nas fitas 4, 5 e 6 o seguinte:
1: aaceilnrt
2: aaabcclno
3: aade

// Note que tenho 1 único bloco de caracteres por fita, cada bloco contendo até 9 caracteres.
// Se houvessem mais letras poderia ter mais blocos de 9 caracteres.

Por fim posso agora repetir o processo de intercalação porem dessa vez cada uma das fitas 4 5 e 6 possuem um único bloco.
Vou gravar essa intercalação ordenada na fita 1 cujos dados eu já li. e terei portanto:
// Note que estou escrevendo na fita 1 mas na verdade é na fita 1%N, porque se houvessem mais blocos de tamanho 9 eu faria 2%N, 3%N, etc..

1: aaaaaaabcccdeetllnnort

E assim consegui meu vetor ordenado utilizando poucas leituras e escritas nas fitas.

Uma otimização desse sistema é utilizar um heap para ordenar os elementos na memória, e vai retirando o menor deles a cada vez.
Se voce recebe uma letra que é menor do que as letras que voce já escreveu na fita, então voce diz que ela pertence ao próximo bloco.
Repare que isso não garante que todos os blocos terão o mesmo tamanho, mas isso otimiza o processo.

O resto do processo é analogo, porem em nenhum momento vai haver garantia de blocos com o mesmo tamanho.

Nota Importante: Repare que quando voce carregar uma letra que pertença ao próximo bloco de acordo com o critério que expliquei acima, ainda existem letras
                 que pertencem ao bloco anterior, termine de escreve-las no bloco anterior antes de pular para o próximo bloco.
                 Outra coisa é que depois de carregar uma letra para o próximo bloco voce ainda pode carregar letras para o bloco atual.
                 e só pula para a próxima fita uma vez que não houverem mais letras pertencentes ao bloco atual.

// isso ficou confuso vou re-escrever

// Essa aula eu não peguei totalmente, pode ser útil re-estudar isso separadamente.
// acho que ao menos o importante deu pra entender. a ideia é ordenar por partes, e realiza intercalaçoes para aproveitar o que já foi ordenado.