funcoes_auxiliares.c
/******************************************************/
/**** Aluno: Cristiano Alves Ba? ****/
/**** Numero USP: 6430686 ****/
/**** Exerc?cio Programa 3-- Ordena??o ****/
/**** MAC122 -- BMAC -- 2008 --Professor Reverbel ****/
/**** Compilador Dev-C++4.9.9.2 ****/
/******************************************************/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
/*FUN??O QUE TESTA SE ? NUMERO*/
int eh_numero(char c){
switch(c){
case '0':
return 1;
break;
case '1':
return 1;
break;
case '2':
return 1;
break;
case '3':
return 1;
break;
case '4':
return 1;
break;
case '5':
return 1;
break;
case '6':
return 1;
break;
case '7':
return 1;
break;
case '8':
return 1;
break;
case '9':
return 1;
break;
default:
return 0;
break;
}
}
/*FUN??O QUE DEVLOLVE A LINHA EM LETRAS SEM DISTIM?AO DE MAIUSCULA E MINUSCULA*/
char *letra(char *s){
int i, j;
char *copia_letra;
copia_letra = (char*)malloc(strlen(s) * sizeof(char));
i=0;
j=0;
while(s[i]!= '\0'){
if(!eh_numero(s[i]))
copia_letra[j++] = s[i];
i++;
}
return copia_letra;
}
/*FUN??O QUE DEVLOLVE A LINHA EM LETRAS E MAIUSCULAS*/
char *minuscula_em_maiuscula(char *s){
int i, j;
char *copia_maiuscula;
copia_maiuscula = (char*)malloc(strlen(s) * sizeof(char));
i=0;
j=0;
while(s[i]!= '\0'){
if(!eh_numero(s[i])){
if(s[i] >= 97 && s[i] <= 122 )
copia_maiuscula[j++] = s[i]-32;
else
copia_maiuscula[j++] = s[i];
}
i++;
}
return copia_maiuscula;
}
/*FUN??O QUE CALCULA x^n*/
int expoente(int x, int n){
int i;
int mult = 1;
for(i=n; n>0; n--)
mult = mult * x;
return mult;
}
/*TROCA-SE LETRA POR NUMERO*/
int troca_por_numero(char c){
switch(c){
case '0':
return 0;
break;
case '1':
return 1;
break;
case '2':
return 2;
break;
case '3':
return 3;
break;
case '4':
return 4;
break;
case '5':
return 5;
break;
case '6':
return 6;
break;
case '7':
return 7;
break;
case '8':
return 8;
break;
case '9':
return 9;
break;
}
}
/*TROCA-SE SEQUENCIA DE LETRAS EM UM INTEIRO*/
int char_para_int(char *s){
int i=0, j=0, soma=0;
while(eh_numero(s[i]))
i++;
i--;
while(i>=0){
soma = soma + (troca_por_numero(s[i])*expoente(10,j));
j++;
i--;
}
return soma;
}
/*FUN??O QUE COMPARA STRING SEM DISTIN??O DE LETRAS MAIUSCULAS E MINUSCULAS*/
int strcmpf(char *s1, char *s2){
return strcmp(minuscula_em_maiuscula(s1),minuscula_em_maiuscula(s2));
}
/*FUN??O QUE COMPARA STRING NA ORDEM REVERSA*/
int strcmpr(char *s1, char *s2){
return (strcmp(letra(s1),letra(s2))) * (-1);
}
/*FUN??O QUE COMPARA NUMERO*/
int strcmpn(char *s1, char *s2){
if((char_para_int(s1)) == (char_para_int(s2)))
return 0 ;
else if((char_para_int(s1)) > (char_para_int(s2)))
return 1 ;
else
return -1 ;
}
/*FUN??O QUE COMPARA NUMERO NA ORDEM REVERSA*/
int strcmpnr(char *s1, char *s2){
return strcmpn(s1,s2) * -1;
}
/*FUN??O QUE COMPARA STRING NA ORDEM REVERSA SEM DISTIN??O DE LETRAS MAIUSCULAS E MINUSCULAS*/
int strcmpfr(char *s1, char *s2){
return strcmpf(s1,s2) * -1;
}
/*FUN??O QUE COMPARA STRING*/
int strcmp_original(char *s1, char *s2){
return strcmp(s1,s2);
}
/*FUNCAO IMPRIME O TEXTO ORDENADO NA TELA E NO ARQUIVO*/
void imprime(int ini, int fim,char *s[],char *nome_ordem){
FILE *sai;
int i;
sai = fopen("saida.txt","w");
printf("\n%s\n\n",nome_ordem);
//fprintf(sai,"\n%s\n\n",nome_ordem);
for(i=ini ; i <= fim && s[i]!='\0'; i++){
printf("%s\n",s[i]);
fprintf(sai,"%s\n",s[i]);
}
fclose(sai);
}
funcoes_ordenacao.c
/******************************************************/
/**** Aluno: Cristiano Alves Ba? ****/
/**** Numero USP: 6430686 ****/
/**** Exerc?cio Programa 3-- Ordena??o ****/
/**** MAC122 -- BMAC -- 2008 --Professor Reverbel ****/
/**** Compilador Dev-C++4.9.9.2 ****/
/******************************************************/
#include <stdlib.h>
/*FUN??O AUXILIAR PARA O HEAP_SORT*/
void peneira(int p, int m, char *s[], int (*cmp)(char s1[], char s2[])){
int f;
char *c = s[p];
if (p==0)
f=1;
else
f=2*p;
while(f<=m){
if(f<m && (*cmp)(s[f],s[f+1])==-1)
f++;
if((*cmp)(c,s[f])==1)
break;
s[p] = s[f];
p=f;
f= 2*p;
}
s[p] = c;
}
void heap_sort(char *s[], int n, int (*cmp)(char s1[], char s2[])){
int p,m;
char *c;
for(p=n/2; p>=0; p--)
peneira(p,n,s,cmp);
for(m=n;m>=1;m--){
c=s[0];
s[0] =s[m];
s[m] =c;
peneira(0,m-1,s,cmp);
}
}
/*FUN??O AUXILIAR PARA O MERGE_SORT*/
void intercala(int ini, int meio, int fim, char *s[], int (*cmp)(char s1[], char s2[])){
int i,j,k;
char **w;
w = (char**)malloc((fim - ini)* sizeof (char*));
i = ini;
j = meio;
k = 0;
while(i < meio && j < fim){
if((*cmp)(s[i],s[j])<=0)
w[k++] = s[i++];
else
w[k++] = s[j++];
}
while(i < meio)
w[k++] = s[i++];
while(j < fim)
w[k++] = s[j++];
for(i=ini; i < fim ; i++)
s[i] = w[i-ini];
free(w);
}
void merge_sort(char *s[], int ini,int fim, int (*cmp)(char s1[], char s2[])){
if(ini < fim - 1){
int meio = (ini + fim)/2;
merge_sort(s,ini,meio,cmp);
merge_sort(s,meio,fim,cmp);
intercala(ini,meio,fim,s,cmp);
}
}
void selection_sort(char *s[], int n, int (*cmp)(char s1[], char s2[])){
int i, j, j_min;
char *c;
for(i=0; i < n-1 ; i++){
j_min = i;
for(j=i+1; j<n; j++)
if((*cmp)(s[j],s[j_min])== -1)
j_min = j;
c = s[i];
s[i] = s[j_min];
s[j_min] = c;
}
}
void insertion_sort(char *s[], int n, int (*cmp)(char s1[], char s2[])){
int i,j;
char *c;
for(j=1;j<n;j++){
c = s[j];
for(i=j-1; (i>=0)&& ((*cmp)(s[i],c) == 1);i--)
s[i+1] = s[i];
s[i+1] = c;
}
}
/*FUN??O AUXILIAR PARA O QUICK_SORT*/
int separa(char *s[], int ini, int fim, int (*cmp)(char *s1, char *s2)){
char *c = s[ini], *t;
int i = ini +1, j = fim;
while (i <= j){
if((*cmp)(s[i],c) <= 0)
i++;
else if((*cmp)(s[j],c) == 1)
j--;
else{
t = s[i];
s[i] = s[j];
s[j] = t;
}
}
s[ini] = s[j];
s[j] = c;
return j;
}
void quick_sort(char *s[], int ini, int fim, int (*cmp)(char s1[], char s2[])){
int j;
if (ini < fim){
j = separa(s,ini,fim,cmp);
quick_sort(s,ini,j-1,cmp);
quick_sort(s,j+1,fim,cmp);
}
}