Escolha o algoritmo de ordenaēćo
Publicado por José (śltima atualizaēćo em 03/04/2019)
[ Hits: 2.281 ]
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.
#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
Ordenar vetor - ordenaēćo bolha
Comentįrios
Nenhum comentįrio foi encontrado.
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Artigos
Como gerar um podcast a partir de um livro em PDF
Automatizando digitação de códigos 2FA no browser
Resolver problemas de Internet
Como compartilhar a tela do Ubuntu com uma Smart TV (LG, Samsung, etc.)
Dicas
Conheēa a 4Devs, caixa de ferramentas online para desenvolvedores
Como converter um vķdeo MP4 para um GIF para publicar no README.md do seu repositório Github
Como Instalar o Microsoft Teams no Linux Ubuntu
Tópicos
Top 10 do mês
-
Xerxes
1° lugar - 74.716 pts -
Fábio Berbert de Paula
2° lugar - 58.643 pts -
Buckminster
3° lugar - 19.348 pts -
Mauricio Ferrari
4° lugar - 17.410 pts -
Alberto Federman Neto.
5° lugar - 15.374 pts -
Daniel Lara Souza
6° lugar - 14.379 pts -
edps
7° lugar - 13.738 pts -
Diego Mendes Rodrigues
8° lugar - 13.682 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
9° lugar - 13.417 pts -
Andre (pinduvoz)
10° lugar - 10.708 pts
Scripts
A maior comunidade GNU/Linux da América Latina! Artigos, dicas, tutoriais, fórum, scripts e muito mais. Ideal para quem busca auto-ajuda.
Site hospedado por:
