Escolha o algoritmo de ordenação [C/C++]

Escolha o algoritmo de ordenação

Publicado por José (última atualização em 03/04/2019)

[ Hits: 2.499 ]

Download OrdenaRegistros.c

4 0

Denuncie Favoritos Indicar
Programinha que fiz quando estudava C e que ordena estruturas, permitindo ao usuário escolher o algoritmo de ordenação (dentre os mais conhecidos). Testei e funcionou à época.
Esconder código-fonte
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include <ctype.h>
       
      
 typedef struct 
 {
    char Mat[12]; char Nome[40];
 } REGISTRO;
      
    
 const unsigned int TAM_REG = sizeof(REGISTRO);
   
   
 /*----------------------------------------------------------------*/
  
    
 void BubbleSort(FILE *Fluxo)
 {
    REGISTRO Reg1, Reg2;
    int flag = 1;
    unsigned int pos;
    
    while(flag)
    {
       flag = pos = 0; rewind(Fluxo); 
       
       fread(&Reg1, TAM_REG, 1, Fluxo); 
       
       while(fread(&Reg2, TAM_REG, 1, Fluxo))        
      {                                            
          if(atoi(Reg1.Mat) > atoi(Reg2.Mat))
          {                                         /*Bloco em que se procede à troca dos registros desordenados*/
             fseek(Fluxo, pos*TAM_REG, SEEK_SET); 
          fwrite(&Reg2, TAM_REG, 1, Fluxo); fwrite(&Reg1, TAM_REG, 1, Fluxo);
               
           fseek(Fluxo, (2+pos)*TAM_REG, SEEK_SET);
              
             flag = 1;
          }
          else
             Reg1 = Reg2; 
              
         pos++;                        
       }
    } 
 }   
   
  
 /*----------------------------------------------------------------*/
 
 
 void SelectionSort(FILE *Fluxo, unsigned int num_reg)
 {
    REGISTRO Reg, Reg_Pos;
    unsigned int i, pos, maior;
    
    while(num_reg > 1)
    {
       pos = 0L; rewind(Fluxo); 
       
       fread(&Reg, TAM_REG, 1, Fluxo); maior = atoi(Reg.Mat);
       
       for(i = 1; i < num_reg; i++)       
      {                                       
         fread(&Reg, TAM_REG, 1, Fluxo);
                                                      
          if(maior < atoi(Reg.Mat))
          {                                         
             pos = ftell(Fluxo)/TAM_REG - 1; 
             maior = atoi(Reg.Mat);
          }
       }
       
       if(pos != (num_reg - 1))
       {
          fseek(Fluxo, (long) pos*TAM_REG, SEEK_SET); fread(&Reg_Pos, TAM_REG, 1, Fluxo);
           
          fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg, TAM_REG, 1, Fluxo);
          
          fseek(Fluxo, (long) (num_reg - 1)*TAM_REG, SEEK_SET); fwrite(&Reg_Pos, TAM_REG, 1, Fluxo);
       }
       
       num_reg--;
    }     
 }   
   
  
 /*----------------------------------------------------------------*/   
 
 
 void InsertionSort(FILE *Fluxo)   /*Optamos aqui por uma versão do InsertionSort sem uso de arquivo auxiliar*/
 {   
   REGISTRO Reg, Reg_Aux;
    unsigned int pos = 1, inicio, fim = 1, mediana;
    unsigned long int pos_aux;
    
    fseek(Fluxo, (long) TAM_REG, SEEK_SET);
      
    while(fread(&Reg, TAM_REG, 1, Fluxo)) 
    {
       /*Pesquisa binária entre os (pos-1) primeiros registros já ordenados, a fim de descobrir onde encaixar o atual*/   
       
       mediana = fim/2; inicio = 1;
       
       while(fim >= inicio)
       {
          pos_aux = (mediana - 1)*TAM_REG;
        
        fseek(Fluxo, pos_aux, SEEK_SET); fread(&Reg_Aux, TAM_REG, 1, Fluxo);
        
        if(atoi(Reg.Mat) < atoi(Reg_Aux.Mat))
           inicio = mediana + 1; 
        else
           fim = mediana - 1; 
        mediana = (fim + inicio)/2;   
      }
      
      /*Passa-se agora a inserir o registro atual nos (pos-1) primeiros registros, já ordenados*/
      
      if(atoi(Reg.Mat) < atoi(Reg_Aux.Mat))
      {
         do
        {
           pos_aux = ftell(Fluxo);
          
          fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg, TAM_REG, 1, Fluxo);
          
          Reg = Reg_Aux;
          
          fseek(Fluxo, pos_aux, SEEK_SET);   
        }  while(fread(&Reg_Aux, TAM_REG, 1, Fluxo)); 
        
        fwrite(&Reg, TAM_REG, 1, Fluxo);   
      }
      else
      {
         while(fread(&Reg_Aux, TAM_REG, 1, Fluxo))
        {
           pos_aux = ftell(Fluxo);
          
          fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg, TAM_REG, 1, Fluxo);
          
          Reg = Reg_Aux;
          
          fseek(Fluxo, pos_aux, SEEK_SET);
        }   
        
        fwrite(&Reg, TAM_REG, 1, Fluxo);
      }
                  
       fim = ++pos; fseek(Fluxo, (long) pos*TAM_REG, SEEK_SET);
   }
 }   
   
  
 /*----------------------------------------------------------------*/
  
 
 void QuickSort(FILE *Fluxo, unsigned int inicial, unsigned int final)
 {
    REGISTRO Reg1, Reg2;
    unsigned int posi_pivo = (inicial + final)/2, posi_1 = inicial, posi_2 = final;
    long int pivo;
          
    fseek(Fluxo, (long) posi_pivo*TAM_REG, SEEK_SET); fread(&Reg1, TAM_REG, 1, Fluxo); pivo = atoi(Reg1.Mat);
        
    while(posi_1 < posi_2)
   {   
      fseek(Fluxo, (long) posi_1*TAM_REG, SEEK_SET); fread(&Reg1, TAM_REG, 1, Fluxo);       
       while(atoi(Reg1.Mat) < pivo)  
      {
         posi_1++; fread(&Reg1, TAM_REG, 1, Fluxo);   
      } 
      
      fseek(Fluxo, (long) posi_2*TAM_REG, SEEK_SET); fread(&Reg2, TAM_REG, 1, Fluxo);
      while(pivo < atoi(Reg2.Mat))
      {
         posi_2--; fseek(Fluxo, - (long) 2*TAM_REG, SEEK_CUR); fread(&Reg2, TAM_REG, 1, Fluxo);   
      }
              
      if(posi_1 < posi_2)
      {
         fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg1, TAM_REG, 1, Fluxo);
        
        fseek(Fluxo, (long) posi_1*TAM_REG, SEEK_SET); fwrite(&Reg2, TAM_REG, 1, Fluxo);   
      }
    }
    
    if(posi_1 > (inicial + 1))
       QuickSort(Fluxo, inicial, posi_1 - 1);
    
   if((final - 1) > posi_2)
      QuickSort(Fluxo, posi_2 + 1, final);
 }   
   
    
 /*----------------------------------------------------------------*/
  
 
 void MergeSort(FILE *Fluxo, unsigned int inicial, unsigned int final) 
 {
    REGISTRO Reg1, Reg2, VetReg[final - inicial + 1];
    unsigned int mediana = (inicial + final)/2, posi_1 = inicial, posi_2 = mediana + 1, i = 0;
    
   if(inicial < final) 
   {
       MergeSort(Fluxo, inicial, mediana);
      MergeSort(Fluxo, mediana + 1, final); 
      
      fseek(Fluxo, (long) posi_1*TAM_REG, SEEK_SET); fread(&Reg1, TAM_REG, 1, Fluxo); posi_1++;   
      fseek(Fluxo, (long) posi_2*TAM_REG, SEEK_SET); fread(&Reg2, TAM_REG, 1, Fluxo); posi_2++;         
      
      while(1)
      {
         fseek(Fluxo, (long) posi_1*TAM_REG, SEEK_SET); 
         while(atoi(Reg1.Mat) <= atoi(Reg2.Mat)) 
         {
            VetReg[i++] = Reg1;         
          
          if(posi_1 <= mediana)
          {
             fread(&Reg1, TAM_REG, 1, Fluxo); posi_1++;
           }
          else
           {
              fseek(Fluxo, (long) posi_2*TAM_REG, SEEK_SET);
                while(posi_2 <= (final + 1))
              {
                 VetReg[i++] = Reg2;
               
               fread(&Reg2, TAM_REG, 1, Fluxo); posi_2++;     
              }
               
              fseek(Fluxo, (long) inicial*TAM_REG, SEEK_SET); fwrite(VetReg, TAM_REG, final - inicial + 1, Fluxo); return;      
           }
        } 
        
        fseek(Fluxo, posi_2*TAM_REG, SEEK_SET);
        while(atoi(Reg1.Mat) > atoi(Reg2.Mat))
        {
           VetReg[i++] = Reg2;   
          
          if(posi_2 <= final)
          {
             fread(&Reg2, TAM_REG, 1, Fluxo); posi_2++;
          }
           else
           {
              fseek(Fluxo, (long) posi_1*TAM_REG, SEEK_SET);
              while(posi_1 <= (mediana + 1))
              {
                 VetReg[i++] = Reg1; 
                 
               fread(&Reg1, TAM_REG, 1, Fluxo); posi_1++;  
            }
              
              fseek(Fluxo, (long) inicial*TAM_REG, SEEK_SET); fwrite(VetReg, TAM_REG, final - inicial + 1, Fluxo); return;      
           }   
        }   
      }    
   } 
 }   
   
  
 /*----------------------------------------------------------------*/   
  
 
 void HeapSort(FILE *Fluxo, unsigned int num_reg)
 {
    REGISTRO Reg_pai, Reg_filho1, Reg_filho2;
    unsigned int posi_pai = num_reg/2, posi_filhos = num_reg;
    
       /*Função auxiliar de descida de elemento que perdeu posição em nó-pai*/
       
    void Descida(FILE *Fluxo, REGISTRO Reg_descendente, unsigned int posi_descendente, unsigned int num_reg)
   {
      REGISTRO Reg_filhote1, Reg_filhote2;
      unsigned int posi_filhotes = 2*posi_descendente;
         
      while(posi_filhotes < num_reg)
      {
         fseek(Fluxo, (long) (posi_filhotes - 1)*TAM_REG, SEEK_SET); fread(&Reg_filhote1, TAM_REG, 1, Fluxo); fread(&Reg_filhote2, TAM_REG, 1, Fluxo);
                                            
        if((atoi(Reg_filhote1.Mat) <= atoi(Reg_descendente.Mat))&&(atoi(Reg_filhote2.Mat) <= atoi(Reg_descendente.Mat)))
        {
            fseek(Fluxo, (posi_descendente - 1)*TAM_REG, SEEK_SET); fwrite(&Reg_descendente, TAM_REG, 1, Fluxo);
        
           return;
         }
                                        
         if(atoi(Reg_filhote1.Mat) > atoi(Reg_filhote2.Mat)) 
         {
          fseek(Fluxo, (long) (posi_descendente - 1)*TAM_REG, SEEK_SET); fwrite(&Reg_filhote1, TAM_REG, 1, Fluxo); 
         }
        else
        {                    
           fseek(Fluxo, (long) (posi_descendente - 1)*TAM_REG, SEEK_SET); fwrite(&Reg_filhote2, TAM_REG, 1, Fluxo); 
          
          posi_filhotes++;   
         }
                      
           posi_descendente = posi_filhotes; posi_filhotes *= 2;  
       }
      
      if(posi_filhotes == num_reg)
      {
           fseek(Fluxo, (long) (posi_filhotes - 1)*TAM_REG, SEEK_SET); fread(&Reg_filhote1, TAM_REG, 1, Fluxo); 
           
         if(atoi(Reg_filhote1.Mat) > atoi(Reg_descendente.Mat))
        {
           fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg_descendente, TAM_REG, 1, Fluxo);
                           
           fseek(Fluxo, (long) (posi_descendente - 1)*TAM_REG, SEEK_SET); fwrite(&Reg_filhote1, TAM_REG, 1, Fluxo);
          }
          else
          {
           fseek(Fluxo, (posi_descendente - 1)*TAM_REG, SEEK_SET); fwrite(&Reg_descendente, TAM_REG, 1, Fluxo);
         }
             
      }
      else
      {
         fseek(Fluxo, (posi_descendente - 1)*TAM_REG, SEEK_SET); fwrite(&Reg_descendente, TAM_REG, 1, Fluxo);
      }   
   }   
    
       /*Primeiramente, procede-se à montagem do max-heap*/
    
    if((num_reg % 2) == 0)
    {   
       fseek(Fluxo, (long) (posi_filhos - 1)*TAM_REG, SEEK_SET); fread(&Reg_filho1, TAM_REG, 1, Fluxo);
        
       fseek(Fluxo, (long) (posi_pai - 1)*TAM_REG, SEEK_SET); fread(&Reg_pai, TAM_REG, 1, Fluxo);
         
       if(atoi(Reg_pai.Mat) < atoi(Reg_filho1.Mat))
       {
          fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg_filho1, TAM_REG, 1, Fluxo);   
            
          fseek(Fluxo, (long) (posi_filhos - 1)*TAM_REG, SEEK_SET); fwrite(&Reg_pai, TAM_REG, 1, Fluxo);
      }
      
      posi_filhos -= 2; posi_pai = posi_filhos/2;
    }
    else
       posi_filhos--;    
           
   while(posi_pai)   
   {  
       fseek(Fluxo, (long) (posi_filhos - 1)*TAM_REG, SEEK_SET); fread(&Reg_filho1, TAM_REG, 1, Fluxo); fread(&Reg_filho2, TAM_REG, 1, Fluxo);
        
       fseek(Fluxo, (long) (posi_pai - 1)*TAM_REG, SEEK_SET); fread(&Reg_pai, TAM_REG, 1, Fluxo);
       
       if((atoi(Reg_filho1.Mat) > atoi(Reg_pai.Mat))||(atoi(Reg_filho2.Mat) > atoi(Reg_pai.Mat)))
         if(atoi(Reg_filho1.Mat) >= atoi(Reg_filho2.Mat))
          {
             fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg_filho1, TAM_REG, 1, Fluxo);   
          
                /*Como houve troca em nó-pai, desce-se o elemento menor, o que deixou de ser pai*/
          
           Descida(Fluxo, Reg_pai, posi_filhos, num_reg);
         }
         else
          {
             fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg_filho2, TAM_REG, 1, Fluxo);   
          
                /*Como houve troca em nó-pai, desce-se o elemento menor, que deixou de ser pai*/
          
           Descida(Fluxo, Reg_pai, posi_filhos + 1, num_reg);
         }
       
      posi_filhos -= 2; posi_pai = posi_filhos/2;
    }
       
       /*Agora à ordenação propriamente dita, com repetidas trocas entre o primeiro (pai do topo) e o último elemento (mais à direita na fileira mais ralé) e subseqüente exclusão deste, já como maior, do heap*/
    
    do
    {   
      rewind(Fluxo); fread(&Reg_pai, TAM_REG, 1, Fluxo);
            
       fseek(Fluxo, (long) (num_reg - 1)*TAM_REG, SEEK_SET); fread(&Reg_filho1, TAM_REG, 1, Fluxo);
        
       fseek(Fluxo, - (long) TAM_REG, SEEK_CUR); fwrite(&Reg_pai, TAM_REG, 1, Fluxo);
       
       num_reg--; 
           
      Descida(Fluxo, Reg_filho1, 1, num_reg);
           
    }  while(num_reg >= 2);        
 }   
   
  
 /*----------------------------------------------------------------*/   
         
         
 int main(void)
 {        
    char NomeArq[100];
    FILE* Fluxo;
    int opcao = 1;
    unsigned int num_reg;
     
    printf("\nDigite o nome do arquivo a abrir: "); fflush(stdin); gets(NomeArq);
    
    if((Fluxo = fopen(NomeArq, "r+b")) == NULL)
    {
       printf("\nImpossivel acessar o arquivo. FIM DO PROGRAMA"); getchar();
       exit(1);
    }
    
    fseek(Fluxo, 0L, SEEK_END); num_reg = ftell(Fluxo)/TAM_REG;
     
    while(opcao)
    {
       printf("\n\n\tEscolha o algoritmo de ordenacao:"
              "\n\t 1 - BubbleSort;"
              "\n\t 2 - SelectionSort;"
              "\n\t 3 - InsertionSort;"
              "\n\t 4 - QuickSort;"
              "\n\t 5 - MergeSort;"
              "\n\t 6 - HeapSort;"
              "\n\t 0 - Sair."
              "\n\n\t Opcao escolhida: ");
       fflush(stdin); scanf("%d", &opcao); puts("\n\n");
          
       if(opcao >= 0 && opcao <= 6)
          switch(opcao)
          {
             case 0: break;
             case 1: BubbleSort(Fluxo);
                     opcao = 0; break;
             case 2: SelectionSort(Fluxo, num_reg);
                     opcao = 0; break;
             case 3: InsertionSort(Fluxo);
                     opcao = 0; break;
             case 4: QuickSort(Fluxo, 0, num_reg - 1);
                  opcao = 0; break;
          case 5: MergeSort(Fluxo, 0, num_reg - 1);
                  opcao = 0; break;
           case 6: HeapSort(Fluxo, num_reg);
                  opcao = 0;                      
          }
       else
          printf("\nOpcao invalida. Repita a operacao.");
    }      
                   
    fclose(Fluxo);
    printf("\n\nFIM DO PROGRAMA"); getchar();
    exit(0);
 }
Scripts recomendados
Operações de Soma, Subtração, Multiplicação e Divisão
Simples calculadora em C
CAIXA ELETRÔNICO em c++ para Linux
Calculadora de fração
Calcula diferença entre o maior e menos número digitado
Comentários
Nenhum comentário foi encontrado.