Trabalho AEDIS III

Prévia do material em texto

1- Apresente as características fundamentais que diferenciam os Métodos de 
Ordenação Interna dos Métodos de Ordenação Externa e apresente exemplos de 
métodos para cada um destes grupos. 
 
O Método de ordenação interna os objetos a serem ordenados cabem todos na memória 
principal da máquina. O principal fator de custo é o número de comparações entre as chaves 
e o número de movimento de objetos. 
 
No Método de ordenação externa é quando os objetos a serem ordenados não cabem todos 
na memória principal da máquina. O principal fator de custo é o número de acessos ao meio 
de armazenamento. Um exemplo é o Método de seleção. 
 
 
2- Explique o funcionamento do Método de Ordenação Interna conhecido como 
Ordenação por Seleção. 
 
É um dos algoritmos mais simples de ordenação e seu funcionamento ocorre com a 
seleção do menor item do vetor. Em seguida troque-o com item da primeira posição do vetor 
repetindo essa duas operações com os n-1 itens restantes, depois com n-2 itens, até que 
reste apenas um elemento. 
 
 
3- A maioria dos Métodos de Ordenação Externa baseia-se em algum mecanismo de 
Intercalação. Neste contexto, explique o que é Intercalação e porque ela se faz 
necessária. 
 
Intercalar significa combinar dois ou mais blocos ordenados em um único bloco ordenado. Ela 
e necessária para realiza-se uma passada sobre o arquivo, quebrando-o em blocos que 
caibam na memória interna. Cada bloco é ordenado na memória interna e colocado em 
arquivos auxiliares. Os blocos ordenados são intercalados quantas vezes forem necessárias 
para se obter uma ordenação final. A cada passada são formados blocos ordenados maiores, 
até que o conjunto inteiro esteja ordenado. 
 
 
4- Explique os dois Métodos de Ordenação Externa trabalhados na disciplina: 
Intercalação Balanceada de Vários Caminhos e Intercalação Polifásica. 
 
Na intercalação balanceada de vários caminhos, o primeiro registro de cada fita é lido. Retire 
o registro contendo a menor chave. Armazene-o em uma fita de saída. Leia um novo registro 
da fita de onde o registro retirado é proveniente. Ao ler o último registro de um dos blocos, 
sua fita fica inativa. A fita é reativada quando o último registro das outras fitas for lido, neste 
 
 
 
MEC/SETEC - Instituto Federal de Educação, Ciência e Tecnologia. 
Instituto Federal Minas Gerais – Campus São João Evangelista. 
Disciplina: AEDS III Professor: Rosinei Data: 04/09/2013 
Curso: Sistemas de Informação 
Nome: Victor Alberto de Souza 
Turma: 131 
instante um bloco ordenado formado pelos registros lidos foi formado na fita de saída. Repita 
o processo para os blocos restantes. Na intercalação polifásica os blocos ordenados são 
obtidos através de uma estrutura de Fila de Prioridades (com Heap). Os blocos ordenados 
são distribuídos de forma desigual entre as fitas disponíveis. Uma fita é deixada livre para ser 
utilizada como saída. Em seguida, a intercalação de blocos ordenados é executada até que 
uma das fitas de entrada se esvazie. A fita vazia torna-se a próxima fita de saída. 
 
 
5- No Método de Intercalação Polifásica, qual a vantagem de construir os blocos 
iniciais ordenados através de uma estrutura de Fila de Prioridades (com Heap)? 
 
Apresentação por meio de fila é compacta, além de permitir caminhar facilmente pelos nós da 
árvore. O procedimento refaz (cima_baixo) gastando no máximo (lg n) operações no pior 
caso. Logo, o heapsort gasta um tempo proporcional a O(nlg(n)), no pior caso. 
 
 
6- Explique o procedimento de criação de uma estrutura de Heap a partir de um vetor de 
dados qualquer. Execute esta atividade para o vetor de dados a seguir: 
 
 
A L G O R I T M U S E E S T R U T O R A S D E D A D O S 
A L G O R I T U U S E E S T R M T O R A S D E D A D O S 
A L G O R S T U U S E E I T R M T O R A S D E D A D O S 
A L G O R S T U U S E E O T R M T O R A S D E D A D I S 
A L G O S S T U U R E E O T R M T O R A S D E D A D I S 
A L G O S S T U U S E E O T R M T O R A R D E D A D I S 
A L G U S S T O U S E E O T R M T O R A R D E D A D I S 
A L G U S S T T U S E E O T R M T O R A R D E D A D I S 
A L T U S S G T U S E E O T R M O O R A R D E D A D I S 
A L T U S S T T U S E E O I R M O O R A R D E D A D I S 
A L T U S S T T U S E E O G R M O O R A R D E D A D I G 
A U T L S S T T U S E E O S R M O O R A R D E D A D I G 
A U T U S S T T L S E E O S R M O O R A R D E D A D I G 
A U T U S S T T R S E E O S R M O O L A R D E D A D I G 
U A T U S S T T R S E E O S R M O O L A R D E D A D I G 
U U T A S S T T R S E E O S R M O O L A R D E D A D I G 
U U T T S S T A R S E E O S R M O O L A R D E D A D I G 
U U T T S S T O R S E E O S R M A O L A R D E D A D I G 
 
 
7- Apresente o Heap construído na Questão 6 no formato de árvore. 
 
 
 
 
8- Execute a ordenação do vetor da Questão 6 utilizando o Método de Intercalação 
Balanceada de Vários Caminhos. Considere seis fitas disponíveis para a ordenação, sendo 
que três serão utilizadas em cada passada de intercalação, e uma memória principal de 
tamanho suficiente para o armazenamento de quatro registros. Apresente a divisão inicial dos 
blocos nas fitas e o estado delas em cada passada de intercalação. 
 
 
A G L O 
 
R S T U 
 
A D O S 
 I M R T 
 
A R T U 
 E E O S 
 
D D E S 
 
A E E G I L M O O R S T 
 A D D E R R S S T T U U 
A D O S 
 
A A A D D D E E E G I L M O O O R R R S S S S T T T U U