atividade 3 - Ordenação Externa - Pesquisa, Ordenação e Técnicas de armazenamento

Prévia do material em texto

Intercalação Polifásica 
 
O método de intercalação polifásica distribui as séries iniciais de forma desequilibrada, de 
modo que menos passos sejam necessários para a classificação total. 
Os blocos ordenados são distribuídos de forma desigual entre as fitas disponíveis. Assim, 
uma fita é deixada livre. 
 Em seguida, a intercalação de blocos ordenados é executada até que uma das fitas 
esvazie. Neste ponto, uma das fitas de saída troca de papel com a fita de entrada. 
 
Aplicabilidade 
 
A implementação da intercalação polifásica é simples. A parte mais delicada está na 
distribuição inicial dos blocos ordenados entre as fitas. 
 
QuickSort 
 
Proposto por Hoare em 1960 e publicado em 1962, é o algoritmo de ordenação interna mais 
rápido que se conhece para uma ampla variedade de situações. Provavelmente é o mais 
utilizado na ordenação externa. A ideia básica é dividir o problema de ordenar um conjunto 
de ​n​ itens em dois problemas menores. Os problemas menores são ordenados 
independentemente. Por fim, os resultados são combinados para produzir a solução final. 
 
Aplicabilidade 
 
A técnica utilizada é a de dividir para conquistar e esse processo é feito através de um pivô 
A parte mais delicada do método é o processo de partição que é feita através do pivô. 
• O vetor A[Esq..Dir] é rearranjado por meio da escolha arbitrária de um pivô x. • O vetor A é 
particionado em duas partes: – A parte esquerda com chaves menores ou iguais a x. – A 
parte direita com chaves maiores ou iguais a x. 
 
É percorrido o vetor a partir da esquerda até que A[i] ≥ x. 3. E também a partir da direita até 
que A[j] ≤ x. Depois acontece a troca de A[i] com A[j], e este processo continuará até os 
apontadores ​i ​e ​j ​se cruzarem e os elementos estejam todos ordenados. 
 
Diferenças 
 
A intercalação polifásica inicia seu processo deixando uma fita livre, já o do Quicksort se 
inicia escolhendo um pivô e particionando seus elementos maiores a esquerda e maiores a 
direita. 
 
A análise de complexidade do QuickSort é O (log n), já a análise da intercalação polifásica 
é complicada, o que se sabe é que ela é ligeiramente melhor do que a intercalação 
balanceada para valores pequenos de f. Para valores de f > 8, a intercalação balanceada 
pode ser mais rápida. 
 
 
 
 
 
Fita com 25 registros 
 
(B T P S U J M H B M E N F S H J M H F Y B N Q M F) 
 ​B T P​ S U J​ M H B​ M E N ​F S H​ J M H ​F Y B​ N Q M ​F 
 
Fita 1: B T P E M N Y B F 
Fita 2: J S U S F H Q M N 
Fita 3: B M H J H M F 
 
 
 
 
 
Fita 4: B B H J M P S T U 
Fita 5: E F H H J M M N S 
Fita 6: B F F M N Q Y 
 
Resultado final: 
 
Fita 1: B B B B E F F F H H H J J M M M M N N P Q S T U Y 
Fita 2: 
 Fita 3: 
Fita 4: B M J B B H T U P 
Fita 5: E F H H J M M N S 
Fita 6: B F F M N Q Y 
 
BJB B 
MJB B 
JBH H 
SBH B 
BHU B 
HUT P 
UP S 
P T 
 U