Escolha o algoritmo de ordenação
Publicado por José (última atualização em 03/04/2019)
[ Hits: 2.162 ]
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); }
Utilizando arrays, funções e arquivos de texto
Nenhum comentário foi encontrado.
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (15)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)
Pendrive não formata de jeito nenhum (4)