ordena.c
/**************************************************/
/* Aluno: Felipe Junqueira */
/* N?mero USP: 5603871 */
/* Exerc?cio-Programa 3 -- Ordena??o */
/* MAC122 -- BMAC -- 2008 -- Professor: Reverbel */
/* Compilador: ... gcc 4.3.2 */
/**************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int reversa, fold, time, numerico, ePadrao; /*vari?veis que trat?o as op??espassadas pela linha de comando*/
int separa (char **v, int p, int r, int (*cmp)(char [], char []))
{/*m?todo auxiliar do quicksort*/
char *c, *aux;
int i, j;
i = p+1;
j = r;
c = malloc(sizeof(v[p]));
strcpy(c, v[p]);/*?ndice*/
while ( i <= j)
{ /*divide o vetor em outros 2, desordenados, um com as strings "menores" que o ?ndice e outro com as "maiores"*/
if((*cmp)(v[i], c) <= 0)
++i;
else if((*cmp)(c, v[j]) < 0)
--j;
else
{
aux = v[i]; v[i] = v[j]; v[j] = aux;
++i; --j;/*troca uma string maior que est? antes do ?ndice por uma menor que est? depois*/
}
}
v[p] = v[j]; v[j] = c;
return j;
}
void quicksort(char **v, int p, int r, int (*cmp)(char [], char []))
{
int j;
if (p < r)
{/*separa o vetor em 2 desordenados, e os ordena separadamente*/
j = separa (v, p, r, (*cmp));
quicksort (v, p, j-1, (*cmp));
quicksort (v, j+1, r, (*cmp));
}
return;
}
void intercala (int p, int q, int r, char **v, int (*cmp)(char [], char []))
{/*fun??o auxiliar do mergesort*/
int i, j, k;
char **w;
w = malloc((r-p)*sizeof(char)*sizeof(char *));
i = p; j = q;
k = 0;
while (i < q && j < r)
{/*percorre os 2 vetores e intercala as strings, com o aux?lio de w, de forma que o vetor fica ordenado percorrendo-o apenas uma vez*/
if ((*cmp)(v[i], v[j]) <=0)
w[k++] = v[i++];
else
w[k++] = v[j++];
}
while (i < q) w[k++] = v[i++];
while (j < r) w[k++] = v[j++];
for (i = p; i < r; ++i) v[i] = w[i-p];
free (w);
}
void mergesort (int p, int r, char **v, int (*cmp)(char [], char []))
{
if (p < r-1)
{/*divide o vetor em 2, de tamanho igual (ou quase), ordena-os e depois os intercala*/
int q = (p + r)/2;
mergesort (p, q, v, (*cmp));
mergesort (q, r, v, (*cmp));
intercala (p, q, r, v, (*cmp));
}
}
void insercao (int n, char** v, int (*cmp)(char [], char []))
{/*a cada passo, simplesmente insere um elemento na posi??o certa, movendo todos os outros*/
int i, j;
char *aux;
for (j = 1; j < n; j++)
{
aux = v[j];
for (i = j-1; i >= 0 && (*cmp)(v[i], aux) > 0; --i)
v[i+1] = v[i];
v[i+1] = aux;
}
}
void selecao (int n, char **v, int (*cmp)(char [], char []))
{/*organiza o vetor, a cada passo colocando a menor string na menor posi??o n?o ordenada*/
int i, j, min;
char *aux;
for (i = 0; i < n-1; ++i)
{
min = i;
for (j = i+1; j < n; ++j)
if((*cmp)(v[j], v[min]) < 0)
min = j;
aux = v[i]; v[i] = v[min]; v[min] = aux;
}
}
void peneira (int p, int m, char **v, int (*cmp)(char [], char []))
{/*m?todo auxiliar do heapsort*/
char *aux;
int f = 2*p;
aux = v[p];
while (f <= m)
{
if (f < m && (*cmp)(v[f], v[f+1]) < 0)
++f;
if ((*cmp)(aux, v[f]) >= 0)
break;
v[p] = v[f];
p = f; f = 2*p;
}
v[p] = aux;
}
void heapsort (int n, char **v, int (*cmp)(char [], char []))
{
int p, m;
char *aux;
for (p = n/2; p >= 1; --p)
peneira (p, n, v, (*cmp));
for (m = n; m >= 2; --m)
{
if (v[1] && v[m])
{
aux = v[1];
v[1] = v[m];
v[m] = aux;
peneira (1, m-1, v, (*cmp));
}
}
}
int compNum(char a[], char b[])
{/*diz qual ? maior, caso a op??o de ordenar pelo n?mero do come?o da linha esteja selecionada*/
if(a == NULL)
{
if(reversa)/*caso a ordena??o seja reversa, devolve a resposta contr?ria*/
return -1;
else
return 1;
}
if(b== NULL)
{
if(reversa)/*caso a ordena??o seja reversa, devolve a resposta contr?ria*/
return 1;
else
return -1;
}
if(a[0] < b[0])
{
if(reversa)/*caso a ordena??o seja reversa, devolve a resposta contr?ria*/
return 1;
else
return -1;
}
if(a[0] > b[0])
{
if(reversa)
return -1;
else
return 1;
}
else/*o contr?rio de 0 ? 0*/
return 0;
}
int compAlf(char a[], char b[])
{/*compara o primeiro caractere de cada linha, apresenta resultado invertido caso esteja no mode reverso*/
int i, tam;
if(fold)
{
tam = sizeof(a);
for(i = 0; i<tam; i++)
a[i] = tolower(a[i]);
tam = sizeof(b);
for(i=0; i<tam; i++)
b[i] = tolower(b[i]);
}
if(strcmp(a, b) > 0)
{
if(reversa)
return -1;
else
return 1;
}
else if(strcmp(a, b) < 0)
{
if(reversa)
return 1;
else
return -1;
}
else
return 0;
}
int main(int argc, char *argv[])
{
FILE *arq;
int i, j, k, l, linhas;
long int tam;
char a, *entrada, *texto, **v;
int (*cmp)(char [], char []);
entrada = malloc(100);
linhas = 0;
reversa = 0;
fold = 0;
time = 0;
numerico = 0;
ePadrao = 0;
tam = 0;
a = ' ';
if(argc == 1)
{/*caso n?o seja passado um arquivo na inha de comando, toma as providncias neess?rias para executar o programa nesse modo*/
ePadrao = 1;
texto = malloc(40000000);
while(scanf("%s", entrada) != -1 && (strlen(entrada) + tam + 1)<40000000)
{
strcat(texto, entrada);
tam += strlen(entrada);linhas++;
}
for(i=0; i<=tam; i++);
if(texto[i] == '\n')
{
texto[i] = '\0';
}
if(texto[tam] != '\0')
texto[++tam] = '\0';
}
else
{
for(i=1; i<argc-1; i++)
{/*l? os par?metros passados na linha de comando */
a = argv[i][1];
switch(a)
{
case 'f':
fold = 1;
break;
case 't':
time = 1;
break;
case 'n':
numerico = 1;
break;
case 'r':
reversa = 1;
break;
case 'a':
a = argv[i][2];
}
}
strcpy(entrada, argv[i]);
arq = fopen(entrada, "r");
fseek(arq, 0, SEEK_END);/*m?todo para descobrir o tamanho do texto*/
tam = ftell(arq);/*vai at? o fim, olha a posi??o e volta ao in?cio*/
texto = malloc(tam+1);
rewind(arq);
while(fgets(entrada, 100, arq))
{/*l? as palavras do texto e as concatena no vetor*/
strcat(texto, entrada);
linhas++;
}
j = strlen(texto);
for(i=0; i<j; i++)/*substitui os '\n' por \'0', garantindo o aspecto de frase*/
if(texto[i] == '\n')
texto[i] = '\0';
}
if(numerico == 1)/*decide se a ordem vai ser alfab?tica ou num?rica, selecionando a compara??o adequada*/
cmp = compNum;
else
cmp = compAlf;
v = malloc(linhas * sizeof(char *));
j = 0;
for(i=0; i<tam; i++)
{
for(k=0; texto[i] != '\0'; i++)
{/*l? uma das palavras*/
entrada[k++] = texto[i];
}
v[j] = malloc(k*sizeof(char));
for(l=0; l<k; l++)
{/*aloca mem?ria suficiente e armazena ela no vetor de ponteiros*/
v[j][l] = entrada[l];
}
j++;
}
switch(a)
{
case 'H':
heapsort(tam, v, (*cmp));
break;
case 'I':
insercao(tam, v, (*cmp));
break;
case 'M':
mergesort(0, tam, v, (*cmp));
break;
case 'S':
selecao(tam, v, (*cmp));
break;
default:
quicksort(v, 0, tam, (*cmp));
}
for(i=0; i<linhas; i++)
{/*imprime o vetor ordenado e libera a mem?ria alocada*/
printf("%s\n", v[i]);
free(v[i]);
}
free(v);
return 0;
}
