ordena.c
/**********************************************************/
/* Aluno: Tadeu Augusto Ferreira */
/* N?mero USP: 5123924 */
/* Exerc?cio-Programa 3 -- Ordena??o de Arquivos de Texto */
/* MAC122 -- BMAC -- 2008 -- Professor: Reverbel */
/* Compilador: DevC++ vers?o 4.9.9.2 */
/**********************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <time.h>
#define TAM_VETORZAO 40000000
int num_frases(char v[], int n);
int strcmpr(char *s1, char *s2);
int strcmpc(char *s1, char *s2);
int strcmpf(char *s1, char *s2);
int strcmpfr(char *s1, char *s2);
int numcmp(char *s1, char *s2);
int numcmpr(char *s1, char *s2);
void insercao(int n, char **v, int (*comp)(char *, char*));
void selecao(int n, char **v, int (*comp)(char *, char*));
void peneira (int p, int m, char **v);
void heapsort (int n, char **a, int (*comp)(char *, char *));
int separa (int p, int r, char **v, int (*comp)(char *, char*));
void quicksort (int p, int r, char **v, int (*comp)(char *, char*));
void quicksort2 (int n, char **a, int (*comp)(char *, char*));
void intercala (int p, int q, int r, char **v, int(*comp)(char *, char *));
void mergesort (int p, int r, char **v, int (*comp)(char *, char*));
void mergesort2 (int n, char **a, int (*comp)(char *, char*));
static int comp_util; /*comprimento UTILIZADO do vetorzao*/
static int opcao, relogio=0;
static void (*func_comp)(); /*apontador para funcao alguma funcao de ordenacao */
int main(int argc, char *argv[])
{
func_comp=&quicksort2;
FILE *arq;
int count=1;
arq=NULL;
if (argc>1){
while(count<argc) /*procura o arquivo a ser lido que e passado na linha de comando*/
{
if(argv[count][0]!='-'){
arq=fopen(argv[count],"r");
if(arq==NULL)
{
fprintf (stderr, "Nenhum arquivo recebido! \n");
exit(EXIT_FAILURE);
}
}
count++;
}
}
char *vetor; /* VAI SER O NOSSO VETORZ?O */
if(arq!=NULL){ /*vai fazer a leitura do arquivo fornecido. Antes calcula seu tamanho*/
fseek(arq, 0, SEEK_END);
comp_util=ftell(arq);
rewind(arq);
vetor=malloc(comp_util);
int i=0;
while(i<comp_util)
{
char c;
c=getc(arq);
if(c=='\n')
{
vetor[i]='\0';
}
else
vetor[i]=c;
i++;
}
}
else /*vai fazer a leitura da entrada padrao se for o caso*/
{
vetor=malloc(TAM_VETORZAO*sizeof(char));
int k=0;
char c;
do{
c = getc(stdin);
if(c=='\n')
{
vetor[k]='\0';
}
else
vetor[k]=c;
k++;
} while(c != EOF);
comp_util=k;
}
int b;
for(b=0; b<comp_util; b++)
printf("%c", vetor[b]);
int linhas; /*vai guardar o numero de linhas que tem no vetorzao/sera tambem o tamanho do vetor de ponteiros*/
linhas=num_frases(vetor, comp_util);
char **vp; /*o vetor de ponteiros */
vp=malloc(linhas*sizeof(char *));
int p;
for(p=0;p<linhas;p++)
vp[p]=NULL;
int e=0,d=0, f=0;
while(d<linhas)
{
do{
if(e==0){
vp[d]=&vetor[e];
d++;
}
if(vetor[e]=='\0')
vp[d]=&vetor[e+1];
e++;
}while(vp[d]==NULL);
d++;
e++;
}
opcao=1;
int acount=1;
while(acount<argc) /*nesse laco faremos o reconhecimento das opcoes de ordenacao passadas na linha de comando */
{
if(argv[acount][0]=='-')
{
if(argv[acount][1]=='a'){
if(argv[acount][2]=='H')
func_comp=&heapsort;
else if(argv[acount][2]=='I')
func_comp=&insercao;
else if(argv[acount][2]=='M')
func_comp=&mergesort2;
else if(argv[acount][2]=='Q')
func_comp=&quicksort2;
else if(argv[acount][2]=='S')
func_comp=&selecao;
else
func_comp=&quicksort2;
}
if(argv[acount][1]=='f'){
opcao=opcao*3;
}
if(argv[acount][1]=='n'){
opcao=opcao*5;
}
if(argv[acount][1]=='r'){
opcao=opcao*7;
}
if(argv[acount][1]=='t'){
relogio=1;
}
}
acount++;
}
float antes, depois;
antes=clock();
switch(opcao){ /*nesse switch executamos a ordenacao em conformidade com as opcoes de ordenacao */
case 1:
(*func_comp)(linhas,vp,strcmpc);
break;
case 3:
(*func_comp)(linhas,vp,strcmpf);
break;
case 5:
(*func_comp)(linhas,vp,numcmp);
break;
case 7:
(*func_comp)(linhas,vp,strcmpr);
break;
case 21:
(*func_comp)(linhas,vp,strcmpfr);
break;
case 35:
(*func_comp)(linhas,vp,numcmpr);
break;
default:
fprintf (stderr, "\nOPCAO DE ORDENACAO SEM SENTIDO!\n");
return EXIT_FAILURE;
}
depois=clock();
while(f<linhas){ /*impressao do arquivo ordenado na saida padrao */
printf("\n%s",vp[f]);
f++;
}
if(relogio)
printf("\n\nTempo decorrido para ordenacao: %f\n\n",(depois - antes)/ CLOCKS_PER_SEC);
free(vp);
free(vetor);
if(arq!=stdin){
fclose(arq);
}
/* system("PAUSE"); */
return 0;
}
/* funcao que recebe uma string e seu tamanho */
/* e retorna o numero de '\0' contidas na mesma */
int num_frases(char v[], int n)
{
int i,c=0;
for(i=0;i<n;i++)
{
if(v[i]=='\0')
c++;
}
return c;
}
/*funcao que recebe duas strings e retorna*/
/*valores contrarios ao retorno da funcao strcmp da biblioteca string.h */
int strcmpr(char *s1, char *s2)
{
return -strcmp(s1,s2);
}
/*funcao que recebe duas strings e retorna a comparacao de string feita pela funcao strcmp*/
int strcmpc(char *s1, char *s2)
{
return strcmp(s1,s2);
}
/*funcao que recebe duas strings e retorna a comparacao de strings*/
/*nao fazendo direfenciacao entre maiusculas e minusculas */
/*a funcao nao altera as strings originais */
int strcmpf(char *s1, char *s2)
{
for(;tolower(*s1)==tolower(*s2); s1++,s2++)
if(*s1=='\0')
return 0;
return tolower(*s1)-tolower(*s2);
}
/*funcao que recebe duas strings e retorna*/
/*valores contrarios ao retorno da funcao strcmpf */
int strcmpfr(char *s1, char *s2)
{
return -strcmpf(s1,s2);
}
/*funcao que recebe duas strings e retorna*/
/*-1 se s1<s2 0 se s1=s2 e 1 se s1>s2 e considerado os valores numericos de s1 e s2 */
int numcmp(char *s1, char *s2)
{
double v1, v2;
v1=atof(s1);
v2=atof(s2);
if(v1<v2)
return -1;
else if(v1>v2)
return 1;
else
return 0;
}
/*funcao que recebe duas strings e retorna*/
/*valores contrarios ao retorno da funcao numcmp */
int numcmpr(char *s1, char *s2)
{
return -numcmp(s1,s2);
}
/* Esta fun??o recebe o tamanho de v e uma funcao de comparacao*/
/* e rearranja o vetor v em ordem crescente ou decrescente dependendo da funcao de comparacao */
void insercao(int n, char **v, int (*comp)(char *, char*))
{
int i, j;
char *x;
for(j=1;j<n;j++){
x=v[j];
for(i=j-1; i>=0 && (((*comp)(v[i],x))==1); --i)
v[i+1]=v[i];
v[i+1]=x;
}
}
/* Esta fun??o recebe o tamanho de v e uma funcao de comparacao*/
/* e rearranja o vetor v em ordem crescente ou decrescente dependendo da funcao de comparacao */
void selecao(int n, char **v, int (*comp)(char *, char*))
{
int i, j, min;
char *p;
for (i = 0; i < n-1; ++i) {
min = i;
for (j = i+1; j < n; ++j)
if(((*comp)(v[j],v[min]))<0)
min = j;
p = v[i]; v[i] = v[min]; v[min] = p;
}
}
/* Esta fun??o recebe o tamanho de v e uma funcao de comparacao*/
/* e rearranja o vetor a em ordem crescente ou decrescente dependendo da funcao de comparacao */
void heapsort(int n, char **a, int (*comp)(char *, char *)) /*adapta??o de uma vers?o disponivel na Wikipedia */
{
int i = n/2, pai, filho;
char *t;
for (;;)
{
if (i > 0)
{
i--;
t = a[i];
}
else
{
n--;
if (n == 0)
return;
t = a[n];
a[n] = a[0];
}
pai = i;
filho = i*2 + 1;
while (filho < n)
{
if ((filho + 1 < n) && ((*comp)(a[filho + 1],a[filho]))>0)
filho++;
if (((*comp)(a[filho],t))>0)
{
a[pai] = a[filho];
pai = filho;
filho = pai*2 + 1;
}
else
break;
}
a[pai] = t;
}
}
/* Recebe vetor v[p..r] com p < r, e uma funcao de comparacao. Rearranja os */
/* elementos do vetor e devolve j em p..r tal que */
/* v[p..j-1] <= v[j] < v[j+1..r]. ou o contrario dependendo da funcao de comparacao */
int separa (int p, int r, char **v, int (*comp)(char *, char *))
{
{
char *c = v[p], *t;
int i = p+1, j = r;
while (i <= j) {
if(((*comp)(v[i], c))<=0)
++i;
else if ((*comp)(c,v[j])<0)
--j;
else {
t = v[i], v[i] = v[j], v[j] = t;
++i; --j;
}
}
v[p] = v[j], v[j] = c;
return j;
}
}
/* A fun??o recebe um vetor v[p..r], com p <= r+1, e uma funcao de comparacao*/
/* e rearranja o vetor em ordem crescente ou decrescente dependedo na funcao de comparacao*/
void quicksort (int p, int r, char **v, int (*comp)(char *, char*))
{
int j;
while (p < r) {
j = separa (p,r,v, comp);
if (j - p < r - j) {
quicksort (p, j-1, v, comp);
p = j + 1;
}
else{
quicksort (j+1, r, v, comp);
r = j - 1;
}
}
}
/*recebe so o vetor o tamando no mesmo e a funcao de comparacao*/
/*uma adaptacao da funcao quicksort para ficar nos moldes da outra funcoes*/
void quicksort2 (int n, char **a, int (*comp)(char *, char*))
{
quicksort(0, n-1, a, comp);
