Escolha o algoritmo de ordenaēćo
Publicado por José (śltima atualizaēćo em 03/04/2019)
[ Hits: 2.204 ]
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
Escrevendo um arquivo Unicode em C#
Calcular taxa de juros com constante em C
Comentįrios
Nenhum comentįrio foi encontrado.
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Artigos
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Tķtulo: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Dicas
Instalando Brave Browser no Linux Mint 22
vķdeo pra quem quer saber como funciona Proteēćo de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Pśblico/Anōnimo de forma simples, rįpido e fįcil
Tópicos
Programa duplicado no "Abrir com" e na barra de pesquisa do ... (1)
VMs e Interfaces de Rede desapareceram (13)
Como abrir o pycharm no linux [RESOLVIDO] (4)
Top 10 do mês
-
Xerxes
1° lugar - 75.304 pts -
Fábio Berbert de Paula
2° lugar - 54.918 pts -
Mauricio Ferrari
3° lugar - 16.978 pts -
Andre (pinduvoz)
4° lugar - 15.821 pts -
Alberto Federman Neto.
5° lugar - 15.561 pts -
Daniel Lara Souza
6° lugar - 15.187 pts -
Diego Mendes Rodrigues
7° lugar - 15.009 pts -
Buckminster
8° lugar - 13.685 pts -
edps
9° lugar - 12.572 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
10° lugar - 11.965 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:
