AEDs III 22/06/2011

Intercalação polifásica.
Normalmente teriamos de usar o dobro de número de fitas que o número de caracteres que possuimos na nossa memória. ou seja f=2m
há a possibilidade de economizarmos fitas e colocarmos f=m+1 o que é prático.

O macete é o seguinte:
voce coloca os blocos distribuidos de maneira desigual:

f1: bloco1 bloco2 bloco3
f2: bloco4 bloco5 bloco6
f3: bloco7
f4:

No caso escrevemos a saida dos primeiros blocos em f4 e temos então:

f1: bloco2 bloco3
f2: bloco5 bloco6
f3:
f4: bloco1bloco4bloco7

Na vez seguinte nós intercalamos os primeiros blocos das fitas 1 2 4 e escrevemos na fita 3.

f1: bloco3
f2: bloco6
f3: bloco2bloco5bloco1bloco4bloco7
f4:

Por fim podemos intercalar os 3 ultimos blocos em uma das fitas livres.

Perceba que essa desigualdade de tamanho de bloco traz uma desvantagem porque voce perde parte do paralelismo de leitura, mas nem sempre.

Sendo portando o número de fitas limitado a 2m, voce deve sempre usar a Intercalação balanceada se voce possuir 2m fitas disponiveis, pois é mais eficiente.
Mas caso voce não tenha 2m fitas sobrando considere o uso da intercalação polifásica.

CONCEITO:
Quicksort Externo é um quicksort que minimiza o número de acessos a memória.

É um algoritomo insort e portanto não precisa de mais de uma memória primária. m=O(log n), m>3)

Porém sua memória deve ser de acesso randomico.

Como funciona?

Considere o vetor na memoria V={5 3 10 6 1 7 4} e uma memória com espaço suficiente M inicialmente igual à {vazio}
Leia-se alternadamente o elemento mais a direita do vetor e mais a esquerda e vai preenchendo sua memória e os ordenando ao mesmo tempo.
sendo m=3 leia 3 números e deixe:
M = {4 5 7};
// Pense nesse vetor como o nosso pivo. Tudo que for menor que isso vai para a esquerda dele tudo que for maior vai para a direita.
Após ler m números, voce lê o próximo se ele for menor do que o menor número do vetor em memória voce o escreve na primeira posição de V
Temos então ao ler 3:
V={3 3 10 6 1 7 4}
M={4 5 7}
lendo 1 temos:
V={3 1 10 6 1 7 4}
M={4 5 7}
lendo 10 temos:
V={3 1 10 6 1 7 10}
M={4 5 7}
lendo 6 temos um novo caso em que o número esta entre o máximo e mínimo.
Nesse caso escreva em V o máximo ou o mínimo e guarde esse novo valor em M, e reordene M
então temos:
V={3 1 10 6 1 7 10} // Escrevi 7 sobre o 7 por isso não aparenta ter mudado nada.
M={4 5 6}

Após isso não há mais números à se ler, escreva M no espaço de V que ainda não foi escrito.
Então temos:

V={3 1 4 5 6 7 10}
M={4 5 6}

E este foi um passo recursivo do quicksort.
Agora voce tem 3 partições: {3 1}{4 5 6}{7 10}

Repita o processo recursivamente para a partição mais a esquerda e para a mais a direita.
Quando houver apenas um número por partição ou não houver nova partição o Vetor estará ordenado.