Ordena o Externa

Pontifícia Universidade Católica de Minas Gerais
Sistemas de Informação – Projeto de Algoritmos

ORDENAÇÃO EXTERNA

Charles Júnio de Paula Assunção
Breno Henrique Pereira de Oliveira
Grasiele A. de Oliveira Brustolom
Jefferson Carlos de Oliveira

Betim, maio de 2015
Índice

1. Introdução.................................................................................................................1
2. Métodos de Ordenação Externa.................................................................................2 2.1 Intercalação Balanceada de Vários Caminhos....................................................2 2.2 Seleção por Substituição...................................................................................3 2.3 Complexidade...................................................................................................5 3. Considerações Finais..................................................................................................5 4. Referências................................................................................................................6
1. Introdução
A ordenação externa envolve arquivos compostos por um número de registros que é maior do que a memória interna do computador pode armazenar.
Os métodos de ordenação externa são muito diferentes dos métodos de ordenação interna. Em ambos os casos o problema é o mesmo: rearranjar os registros de um arquivo em ordem ascendente ou descendente. Entretanto, na ordenação externa as estruturas de dados têm que levar em conta o fato de que os dados estão armazenados em unidades de memória externa, relativamente muito mais lentas do que a memória principal.
Nas memórias externas, tais como fitas, discos e tambores magnéticos, os dados são armazenados como um arquivo sequencial, onde apenas um registro pode ser acessado em um dado momento. Esta é uma restrição forte se comparada com as