segunda-feira, 5 de agosto de 2013

QuickSort with Big Files....


Abaixo um codigo para ordenação de arquivos grandes usando QuickSort.
50%, estou trabalhando nele ainda portando do TurboC para o GCC...




#include 
#include 
#include 
#include 
#include 
#include 


int ConverteArquivo();
struct pessoa *StrToPessoa(char str[]);
void load(void);
void quick_disk(FILE *fp, int count, char campo);
void qs_disk(FILE *fp, int left, int right, char campo);
void qs_swap_all_fields(FILE *fp, long i, long j);
void reiniciaOrdenacao();
int copyFile(char source_file[255], char target_file[255]);

char arquivoOriginalEspacos[]  = {"c:\\TEMP\\ListaOrigem.txt"};    /*arquivo do prof usado apenas para conversao*/
char arquivoOrigemFormatado[] = {"c:\\TEMP\\ListaDestino.txt"};   /*arquivo formatado usado como fonte selecao do usuario*/
char arquivoTemporario[]      = {"c:\\TEMP\\lTMP.txt"};
char arquivoTemporarioOrd[]   = {"c:\\TEMP\\lTMP2.txt"}; //arquivo ordenado
/* selecao usuario, nunca
  exibido apenas usado como fontes para ordenacao, por causa das
  estatisticas*/


struct pessoa
{
 char ID[8];
 char CPF[13];
 char nome[50];
 char meio[10];
 char sobrenome[50];
};

struct est_ordenacao
{
 char metodo[50];
 int  trocas;
 int  testes;
 int  tempo;
};

struct est_busca
{
 char metodo[50];
 int  ocorrencias;
 int  posicao; //buffer para esta versao
 int  numero_testes;
 int  tempo;
};




struct pessoa ainfo; //buffer auxiliar

struct est_busca     dat_est_busca[2]={

  "Sequencial", 0 , 0 , 0 , 0,
  "Binaria"   , 0 , 0 , 0 , 0
};



struct est_ordenacao dat_est_ord[6] = {
  "Bolha"       , 0 , 0 , 0 ,
  "Insercao"    , 0 , 0 , 0 ,
  "Selecao"     , 0 , 0 , 0 ,
  "Intercalacao", 0 , 0 , 0 ,
  "Orde Rapida" , 0 , 0 , 0 ,
  "Outro Metodo", 0 , 0 , 0
};


unsigned long n;
int Q;



void metodo_ordenacao_rapida(char campo, char ordem){
 reiniciaOrdenacao();
 FILE *fp;
 if((fp=fopen(arquivoTemporarioOrd,"rb+"))==NULL){
  printf("O arquivo nao pode ser aberto para leitura/escrita\n");
  exit(1);
 }
 quick_disk(fp,Q,campo);
 fclose(fp);

}


void metodo_bolha(char campo, char ordem){

}


void metodo_insercao(char campo, char ordem){

}

void metodo_selecao(char campo, char ordem){

}

void metodo_intercalacao(char campo, char ordem){

}

void metodo_outraOrdenacao(char campo, char ordem){

}


void ordenar(char campo, char ordem){

 metodo_bolha(campo, ordem);
 metodo_insercao(campo, ordem);
 metodo_selecao(campo, ordem);
 metodo_intercalacao(campo, ordem);
 metodo_outraOrdenacao(campo, ordem);
 metodo_ordenacao_rapida(campo, ordem);

 printf("\nPressione qualquer tecla para continuar...");
 getche();

}
void buscar(char campo, char metodo){
printf("\nNao disponivel...");
printf("\nPressione qualquer tecla para continuar...");
getche();

//TODO fazer a busca
}


void estatisticas_ordenacao(){

 printf("\nEstatistica de Ordenacao");
 printf("\n========================");

 for(int i=0; i<5;i++){
  printf("\n Metodo: [%s]",        dat_est_ord[i].metodo);
  printf(" Trocas: [%d]",        dat_est_ord[i].trocas);
  printf(" Testes: [%d]",        dat_est_ord[i].testes);
  printf(" Tempo: [%d]", dat_est_ord[i].tempo);
 }
}

void estatisticas_busca(){

 printf("\nEstatistica de Busca");
 printf("\n====================");


 for(int i=0; i<2;i++){
  printf("\n Metodo: %s",       dat_est_busca[i].metodo);
  printf(" Ocorrencias: [%d]",  dat_est_busca[i].ocorrencias);
  printf(" Posicao: [%d]",  dat_est_busca[i].posicao);
  printf(" Testes: [%d]",      dat_est_busca[i].numero_testes);
  printf(" Tempo: [%d]",      dat_est_busca[i].tempo);

 }
}

void estatisticas(){
  estatisticas_ordenacao();
  estatisticas_busca();
  printf("\nPressione qualquer tecla para continuar...");
  getche();


}

void show(){
 FILE *fpOrigem;

 if((fpOrigem=fopen(arquivoTemporarioOrd,"rb")) == NULL){
  printf("[error] - o arquivo de Origem pode ser aberto.\n");
  exit(0);
 }



 printf("\nLista de pessoas");
 printf("\n----------------");

 struct pessoa *p;

 for(int i=0;i<Q;i++){
   fread(p, sizeof(struct pessoa), 1, fpOrigem);
   printf("\n %d  CPF:%s Nome:%s Meio: %s SobreNome: %s", (i+1), p->CPF, p->nome, p->meio, p->sobrenome);
   free(p);

 }

 free(p);
 fclose(fpOrigem);
 printf("\nPressione qualquer tecla para continuar...");
 getche();
}

int menu(){

 int sair = 0;
 clrscr();

 printf("\nMenu");
 printf("\n====");
 printf("\n(O)rganizar");
 printf("\n(B)uscar");
 printf("\n(E)statisticas");
 printf("\n(S)air\n");

 char op = toupper(getche());
 switch(op){

  case 'O': {
   printf("\n(N)ome");
   printf("\n(S)obrenome");
   printf("\n(C)PF\n");
   char campo=toupper(getche());

   printf("\n(C)rescente");
   printf("\n(D)ecrecente\n");
   char ordem=toupper(getche());

   ordenar(campo,ordem);
   show();

  }
  break;

  case 'B':{

   printf("\n(N)ome");
   printf("\n(S)obrenome");
   printf("\n(C)PF\n");
   char campo=toupper(getche());

   printf("\nBusca (L)inear");
   printf("\nBusca (N)ormale");
   printf("\nBusca (R)ecursiva\n");
   char metodo=toupper(getche());
   buscar(campo,metodo);

  }
  break;
  case 'E':{
   estatisticas();

  }
  break;
  case 'S':{

   sair = 1;
  }
 }

 return sair;


}




int main(void)
{
 //ConverteArquivo() //opcional
 clrscr();
 printf("\nCarga inicial...");

 printf("\nDigite N:");
 scanf("%ld",&n);

 printf("\nDigite Q:");
 scanf("%d",&Q);

 load();
 int sair=0;
 do{
  sair=menu();
 }while(sair!=1);

 printf("\n Pressione qualquer tecla para sair...");
 getche();
 return 0;

}


//Executa a leitura dos N arquivos para Memoria
void load(void){
 FILE *fp;
 FILE *fpTemporario;

 if((fp=fopen(arquivoOrigemFormatado,"rb")) == NULL){
  printf("[error] - o arquivo nao pode ser aberto.\n");
  exit(0);
 }

 struct pessoa *p = (pessoa *) malloc(sizeof(struct pessoa));


 fseek(fp, n * sizeof(struct pessoa), SEEK_SET);


 if((fpTemporario=fopen(arquivoTemporario,"wb"))==NULL)
 {

  printf("\n [error] - O arquivo nao pode ser aberto");

 }


 for(int i=0;i<Q;i++){
  fread(p, sizeof(struct pessoa), 1, fp);
  if(fwrite(p, sizeof(struct pessoa),1,fpTemporario)!=1){
   printf("[error] Falha ao gravar");
  }

 }

 fclose(fp);
 fclose(fpTemporario);
 reiniciaOrdenacao();
}
void reiniciaOrdenacao(){

 FILE *fp;
 FILE *fpTemporario;

 if((fp=fopen(arquivoTemporario,"rb")) == NULL){
  printf("[error] - o arquivo nao pode ser aberto.\n");
  exit(0);
 }

 struct pessoa *p = (pessoa *) malloc(sizeof(struct pessoa));


 fseek(fp, n * sizeof(struct pessoa), SEEK_SET);


 if((fpTemporario=fopen(arquivoTemporarioOrd,"wb"))==NULL)
 {

  printf("\n [error] - O arquivo nao pode ser aberto");

 }


 for(int i=0;i<Q;i++){
  fread(p, sizeof(struct pessoa), 1, fp);
  if(fwrite(p, sizeof(struct pessoa),1,fpTemporario)!=1){
   printf("[error] Falha ao gravar");
  }

 }

 fclose(fp);
 fclose(fpTemporario);

}


//Rotina auxiliar de conversao do arquivo, utilizado para gerar o arquivo
//de Struct para melhorar a performance de FSEEK
int ConverteArquivo(){
 FILE *fpOrigem;
 FILE *fpDestino;

 if((fpDestino=fopen(arquivoOrigemFormatado,"wb"))==NULL)
 {

  printf("\n [error] - O arquivo nao pode ser aberto");

 }


 if((fpOrigem=fopen(arquivoOriginalEspacos,"rb")) == NULL){
  printf("[error] - o arquivo de Origem pode ser aberto.\n");
  return 0;
 }


 char str[100];
 char buf[2];
 strcpy(str,"\0");
 char ch;
 unsigned long count = 0;

 while(!feof(fpOrigem)){

     ch = getc(fpOrigem);
     buf[0] = ch;
     buf[1] = '\0';
     strcat(str,buf);

     if(ch=='\n'){

      struct pessoa *p= StrToPessoa(str);
      clrscr();
      printf("%ld - %s",count, str);
      count++;


      if(fwrite(p, sizeof(struct pessoa),1,fpDestino)!=1)
      {
        printf("[error] Falha ao gravar");
      }
      free(p);
      strcpy(str,"\0");
     }


 }


 fclose(fpOrigem);
 fclose(fpDestino);

 return 1;

}

//converte uma string em um objeto Pessoa
struct pessoa *StrToPessoa(char str[]){

 struct pessoa *p;
 p = (pessoa *) malloc(sizeof(struct pessoa));
 if(p==NULL){
  printf("[error] - Falha na alocacao de memoria!");
  exit(1);
 }

 char * pch;

 pch = strtok (str," ");
 strcpy(p->ID,pch);
 pch = strtok (NULL, " ");
 strcpy(p->CPF,pch);
 pch = strtok (NULL, " ");
 strcpy(p->nome,pch);
 pch = strtok (NULL, " ");
 strcpy(p->meio,pch);
 pch = strtok (NULL, " ");
 strcpy(p->sobrenome,pch);
 return p;
}
/*
=====================================================================

                 Quick Sort

=====================================================================
*/

/*Devolve um ponteiro para o campo correto*/

char *qs_get_campo(FILE *fp, long rec, char campo){

 struct pessoa *p;
 p=&ainfo;
 fseek(fp,rec*sizeof(ainfo),SEEK_SET);
 fread(p,sizeof(ainfo),1,fp);

 switch(campo){
 case 'I':
  return ainfo.ID;

 case 'C':
  return ainfo.CPF;

 case 'N':
  return ainfo.nome;

 case 'M':
  return ainfo.meio;

 case 'S':
  return ainfo.sobrenome;

 default:
  return ainfo.nome;

 }


}


/*um quicksort para arquivos*/
void quick_disk(FILE *fp, int count, char campo)
{

 qs_disk(fp, 0, count-1, campo);
}


void qs_disk(FILE *fp, int left, int right, char campo){

 dat_est_ord[4].testes++;
 dat_est_ord[4].tempo+=2;

 long int i, j;
 char x[100];
 i = left; j = right;

 strcpy(x, qs_get_campo(fp,(long)(i+j)/2, campo)); //obtem o cep intermediario



 do{


  while(strcmp(qs_get_campo(fp,i, campo),x)<0 && i<right) i++;

  while(strcmp(qs_get_campo(fp,j, campo),x)>0 && j>left)  j--;



  if(i<=j){
   qs_swap_all_fields(fp, i, j);
   i++; j--;
  }

 }while(i<=j);

 if(left<j)  qs_disk(fp, left,(int) j,   campo);
 if(i<right) qs_disk(fp, (int) i, right, campo);

}

void qs_swap_all_fields(FILE *fp, long i, long j){

 dat_est_ord[4].trocas++;
 dat_est_ord[4].tempo+=5;

 char a[sizeof(ainfo)], b[sizeof(ainfo)];

 /*primeiro le os registros i e j*/

 fseek(fp, sizeof(ainfo)*i, SEEK_SET);
 fread(a,  sizeof(ainfo), 1, fp);
 fseek(fp, sizeof(ainfo)*j, SEEK_SET);
 fread(b,  sizeof(ainfo), 1, fp);

 /*em seguida escreve-os de volta em posicoes diferentes*/

 fseek(fp, sizeof(ainfo)*j, SEEK_SET);
 fwrite(a, sizeof(ainfo),1, fp);

 fseek(fp, sizeof(ainfo)*i, SEEK_SET);
 fwrite(fp,sizeof(ainfo),1,fp);


}
/*Rotinas de Copia de Arquivos*/

/*
  Copia um arquivo de uma origem para um destino
*/
int copyFile(char source_file[255], char target_file[255]){
  char ch;
  FILE *source, *target;

  source = fopen(source_file, "rb");

  if( source == NULL )
  {
   printf("[error] - Falha abrir origem...\n");
   exit(EXIT_FAILURE);
  }

  target = fopen(target_file, "wb");

  if( target == NULL )
  {
   fclose(source);
   printf("[error] - Falha ao abrir destino...\n");
   exit(EXIT_FAILURE);
  }

  while( ( ch = fgetc(source) ) != EOF )
  {
   fputc(ch, target);
  }
   fclose(source);
   fclose(target);
 
   return 0;
    
}


Postar um comentário