Quicksort externa

Estamos acostumados a estudar métodos de ordenação onde todos os itens, os quais precisamos ordenar, cabem na memória interna. Assim, nossa única preocupação em relação a esses algoritmos são o tamanho, número de comparações entre chaves, número de movimentações de itens do arquivo, e ainda outro aspecto importante, a quantidade extra de memória auxiliar utilizada pelo algoritmo.

A ordenação externa envolve arquivos compostos por um número de registros que é maior do que a memória interna que um computador pode armazenar. Esses métodos, por sua vez, possuem particularidades que os diferenciam dos métodos de ordenação interna, nas próximas seções discutiremos esta parte de forma mais profunda.

Quicksort externo

Na primeira fase do trabalho deverá ser implementado em C os métodos de ordenação externa mencionados, considerando-se arquivos de valores inteiros quaisquer. Já a segunda fase corresponde ‘a analise experimental da complexidade dos métodos mencionados, considerando-se os seguintes quesitos:

Número de transferências de itens da memória externa para a memória interna;

Número de transferências de valores da memória interna para a memória externa;

Número de comparações entre valores internos;

Tempo de execução.

Para a realização dos testes, deverão ser considerados arquivos contendo 100, 500, 1.000, 2.000, 5.000, 10.000, 50.000, 100.000 e 500.000 valores inteiros quaisquer a serem ordenados ascendentemente. Ademais. As seguintes distintas situações de ordem do arquivo devem ser consideradas para cada conjunto de inteiros.