Escolha o algoritmo de ordenação
Publicado por José (última atualização em 03/04/2019)
[ Hits: 2.005 ]
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); }
Soma de números através de strings
Máximo Divisor Comum (algoritmo de Euclides)
Acendedor de leds pela porta paralela
Calcula Força Centrípeta Corrigido
Nenhum comentário foi encontrado.
Agora temos uma assistente virtual no fórum!!! (247)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
iso de sistema 32 bit em atividade (13)
Agora temos uma assistente virtual no fórum!!! (247)
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (27)