Ordenação de N inteiros

Isnard_Oak
(usa Kalango)

Enviado em 09/11/2014 - 22:20h

Eu tenho que resolver o seguinte problema:
Entrada: um arquivo texto com N inteiros a1, a2, ... aN, N < 2^25.
Saída: um arquivo texto com os N inteiros da entrada ordenados.
Restrição 1: o seu executável nunca deverá usar mais do que 2Mb de memória RAM do recurso do sistema

Minha ideia: Criar uns 200 arquivos de textos, cada um com cerca de 160000 números ordenados, para poder gastar pouca memória. Depois disso, verifico os primeiros elementos dos 200 arquivos, vejo o menor e jogo no arquivo de texto final. Vou fazendo isso até completar o arquivo final com os N números iniciais.

Meu problema:
Estou criando os arquivos via

for(i=0;i<160000;i++) {fscanf(text,"%d",&p[i]);n=i;}

mergeSort(p,n);
FILE *text1=fopen("Lista1.txt","w");
for(i=0;i<160000;i++)fprintf(text1,"%d ",p[i]);
fclose(text1);

Como colocar essa estrutura dentro de um for que rodará 200 vezes para criação de 200 arquivos?

P.S. Ainda não sei exatamente como ordenarei os números dos 200 arquivos para o arquivo final. Se tiver uma sugestão ou ideia, agradecerei...
P.S. 2 O mergeSort() é um algoritmo de ordenação, mas isso vcs devem saber...

paulo1205
(usa Ubuntu)

Enviado em 10/11/2014 - 02:04h

Por favor, edite sua postagem original e coloque seu código compreendido entre as tags “[code]” e “[/code]”. Além de ficar mais fácil de ler, vai evitar o problema, que aconteceu, de a sequência ”[i]” ter sido interpretada como início de texto em itálico.

Seu exercício todo é de aplicação do Merge Sort, pois vai requerer a aplicação sucessiva da técnica de dividir blocões (ou listões, pois entendo que o acesso ao arquivo é sequencial) e juntar os blocos divididos num bloco maior, ordenando-os. Esse juntar ordenando é a fase de “merge” do Merge Sort. Talvez você queira estudar um pouco mais essa fase.

Talvez você ache interessante ler, na Wikipedia em Inglês, o artigo sobre Merge Sort, particularmente a seção que fala de uso com drives de fita (que são sequenciais por natureza). O resumo da ópera é que você talvez não precise de 200 arquivos, mas de apenas quatro (ou cinco, se você não puder -- e provavelmente não pode -- sobrescrever o arquivo original).