Quicksort ordinamento stringhe

[Misciu87]

Ciao a tutti,devo un set di stringhe prese in input da un file e restituirle ordinate in un file di output, la prima parte del codice(funzioni exchange,partition e sortlist servono per l'ordinamento le altre funzioni per il caricamento delle stringhe e quelle funzionano) il mio problema e nella funzione partition in quanto questo codice funziona con gli interi ma non con i char perche' nei confronti con <> per i char è diverso dovrei usare strcmp ma non riesco a farlo funzionare, qualcuno può aiutarmi a sistemare i confronti con la strcmp? grazie mille


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>



void readsize(char *inputlist, int *length, int *size) {
FILE *in=fopen("inputlist.txt","r");
int i=0,j=0;
char tmp;

while(fscanf(in,"%c",&tmp)!=EOF && tmp!='\n') j++;
rewind(in);
while(fscanf(in,"%*s\n")!=EOF) i++;
(*length)=i; (*size)=j;
fclose(in);
}

char *readline(FILE *in,int size) {
char *line=(char *)malloc(size*sizeof(char)), tmp;
int i=0;

while(i<size && fscanf(in,"%c",&line[i])!=EOF) i++;
fscanf(in,"%c",&tmp);
if(tmp!='\n')
{
printf("Error: malformed file\n");
return NULL;
}

return line;
}

char **loadlist(char *inputlist, int *length, int *size) {
int i;
char **list;
FILE *in=fopen("inputlist.txt","r");

readsize(inputlist,length,size);

list=(char **)malloc((*length)*sizeof(char *));

for(i=0; i<(*length); i++)
list[i]=readline(in,(*size));

fclose(in);

return list;
}
void exchange(char **list, int i, int j) {
char *tmp=list[i];
list[i]=list[j];
list[j]=tmp;
}

char partition(char **list, int p, int r) {
int i=p, j=r, x, v;
char *pivot;

x=rand()%(r-p+1)+p;
exchange(list,x,p);
pivot=list[p];

while(p<r)
{

while(j>p && strcmp(list[j],pivot)<0)
j--;
while(i<r && strcmp(list[j], pivot)>=0) i++;
if(i<j)
exchange(list,i,j);
}
exchange(list,p,j);
return q;

}
char **sortlist (char **list, int p, int r) {

char q,
int i;

if(p<r)
{

q=partition(list,p,r);

sortlist(list,p,q-1);
sortlist(list,q+1,r);
}
return list;
}
void printlist(char *outputlist, char **list, int length)
{
int i;
FILE *out=fopen("outputlist.txt","w");

for(i=0; i<length; i++)
fprintf(out,"%s\n",list[i]);
fprintf(out,"\n");
fclose(out);
}
int main(int argc, const char *argv[]) {

char **list;
int length,size;
time_t start, end;

if(argc!=3)
{
printf("Usage: stringsort <input list> <output list>\n");
return 1;
}

list=loadlist((char *)argv[1],&length,&size);
start=clock();

list=sortlist(list,length,size);
end=clock();

printf("%g\n",(int)(end-start)/(int)CLOCKS_PER_SEC);
printlist((char *)argv[2],list,length);

return 0;

}

[mondobimbi]

prima di tutto è meglio se il tuo codice lo racchiudi trai tag code o php , in modo che conservino la indentazione, altrimenti è praticamente illeggibile, infatti mi sono perso subito. Ho però notato la maniera per me alquanto strana con cui acquisisci l'input e fornisci l'output.
Mi sembrerebbe meglio leggere l'input dallo stdin e scrivere l'output sullo stdout, usufruendo così della possibilità di una ridirezzione dello stdin e stdout eventualemente su file o di inseririre con facilità il programma in un pipe.
ciao
sergio

[Misciu87]

Perche' io uso cygwin quindi quando eseguo il programma ci passo anche inputlist, outputlist.. il mio problema è per il confronto tra stringhe

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <string.h> 



void readsize(char *inputlist, int *length, int *size) { 
    FILE *in=fopen("inputlist.txt","r"); 
    int i=0,j=0; 
    char tmp; 

    while(fscanf(in,"%c",&tmp)!=EOF && tmp!='\n') j++; 
    rewind(in); 
    while(fscanf(in,"%*s\n")!=EOF) i++; 
    (*length)=i; (*size)=j; 
    fclose(in); 
} 

char *readline(FILE *in,int size) { 
    char *line=(char *)malloc(size*sizeof(char)), tmp; 
    int i=0; 

    while(i<size && fscanf(in,"%c",&line[i])!=EOF) i++; 
    fscanf(in,"%c",&tmp); 
    if(tmp!='\n') 
    { 
        printf("Error: malformed file\n"); 
        return NULL; 
    } 

    return line; 
} 

char **loadlist(char *inputlist, int *length, int *size) { 
    int i; 
    char **list; 
    FILE *in=fopen("inputlist.txt","r"); 
     
    readsize(inputlist,length,size); 

    list=(char **)malloc((*length)*sizeof(char *)); 

    for(i=0; i<(*length); i++) 
        list[i]=readline(in,(*size)); 
         
    fclose(in); 

    return list; 
} 
void exchange(char **list, int i, int j) { 
    char *tmp=list[i]; 
    list[i]=list[j]; 
    list[j]=tmp; 
} 

char partition(char **list, int p, int r) { 
    int i=p, j=r, x, v; 
    char *pivot; 
    char q;
    
    x=rand()%(r-p+1)+p; 
    exchange(list,x,p); 
    pivot=list[p]; 
     
    while(p<r) 
    { 
         
        while(j>p && (strcmp(list[j],pivot))<0) 
          j--; 
        while(i<r && (strcmp(list[j], pivot)>=0)) i++; 
        if(i<j) 
          exchange(list,i,j); 
    } 
    exchange(list,p,j); 
    return q; 
     
} 
char **sortlist (char **list, int p, int r) { 
     
     char q; 
     int i; 
     
    if(p<r) 
    { 
         
        q=partition(list,p,r); 
         
        sortlist(list,p,q-1); 
        sortlist(list,q+1,r); 
    } 
    return list; 
} 
void printlist(char *outputlist, char **list, int length) 
{ 
    int i; 
    FILE *out=fopen("outputlist.txt","w"); 
     
    for(i=0; i<length; i++) 
        fprintf(out,"%s\n",list[i]); 
    fprintf(out,"\n"); 
    fclose(out); 
} 
int main(int argc, const char *argv[]) { 

    char **list;     
    int length,size; 
    time_t start, end; 

    if(argc!=3) 
    { 
        printf("Usage: stringsort <input list> <output list>\n"); 
        return 1; 
    } 

    list=loadlist((char *)argv[1],&length,&size); 
    start=clock(); 

       list=sortlist(list,length,size); 
       end=clock(); 
         
    printf("%f\n",(double)(end-start)/(double)CLOCKS_PER_SEC); 
    printlist((char *)argv[2],list,length); 

    return 0; 
     
}

[mondobimbi]

scusami ma il caldo mi causa la comprensione lenta e non riesco a seguire il tuo codice, io la scriverei così

#include <stdio.h>

void quickSort( char *[], int, int);
int partition( char *[], int, int);


int main() 
{

	char * s[] = { "r", "t", "q", "a", "d", "w", "b", "z", "c"};

	int i;
	printf("\nArray non ordinata :  ");
	for(i = 0; i < 9; ++i)
		printf(" %s ", s[i]);
	printf("\n");

	quickSort( s, 0, 8);

	printf("\nArray ordinata :  ");
	for(i = 0; i < 9; ++i)
		printf(" %s ", s[i]);
	printf("\n");

}



void quickSort( char *a[], int l, int r)
{

   int j;

   if( l < r ) {
        j = partition( a, l, r);
       quickSort( a, l, j-1);
       quickSort( a, j+1, r);
   }
	
}



int partition( char * a[], int l, int r)
{

   char * pivot;
   char * t;	
   int i, j;

   pivot = a[l];
   i = l; j = r+1;
		
   while( 1) {

   	do ++i; while( (strcmp(a[i], pivot) <= 0) && i <= r );
   	do --j; while  (strcmp(a[j], pivot) > 0) ;
   	if( i >= j ) break;
   	t = a[i]; a[i] = a[j]; a[j] = t;

   }

   t = a[l]; a[l] = a[j]; a[j] = t;
   return j;
}

ciao
sergio

[Misciu87]

ora provo a me serviva solo la funzione partition perche' io le stringhe le devo prendere da un file inputlist.txt non posso fare come mi hai detto tu..

Ora provo a modificare la mia partition con la tua e ti dico come va, grazie per adesso

[Misciu87]

ho modificato cosi il codice ma non mi funziona ancora..

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <string.h> 



void readsize(char *inputlist, int *length, int *size) { 
    FILE *in=fopen("inputlist.txt","r"); 
    int i=0,j=0; 
    char tmp; 

    while(fscanf(in,"%c",&tmp)!=EOF && tmp!='\n') j++; 
    rewind(in); 
    while(fscanf(in,"%*s\n")!=EOF) i++; 
    (*length)=i; (*size)=j; 
    fclose(in); 
} 

char *readline(FILE *in,int size) { 
    char *line=(char *)malloc(size*sizeof(char)), tmp; 
    int i=0; 

    while(i<size && fscanf(in,"%c",&line[i])!=EOF) i++; 
    fscanf(in,"%c",&tmp); 
    if(tmp!='\n') 
    { 
        printf("Error: malformed file\n"); 
        return NULL; 
    } 

    return line; 
} 

char **loadlist(char *inputlist, int *length, int *size) { 
    int i; 
    char **list; 
    FILE *in=fopen("inputlist.txt","r"); 
     
    readsize(inputlist,length,size); 

    list=(char **)malloc((*length)*sizeof(char *)); 

    for(i=0; i<(*length); i++) 
        list[i]=readline(in,(*size)); 
         
    fclose(in); 

    return list; 
} 


int partition(char **list, int p, int r) { 
    int i,j;
    char *pivot; 
    char *t;
    
    i=p;j=r;
    pivot=list[p]; 
     
    while(i<j) 
    { 
         
         do ++i; while( (strcmp(list[i], pivot) <= 0) && i < r );
         do --j; while ( (strcmp(list[j], pivot) > 0 )&& j>p) ;
         if( i >= j ) break;
   	         t = list[i]; list[i] = list[j]; list[j] = t;
        /*while(j>p && (strcmp(list[j],pivot))<0) 
          j--; 
        while(i<r && (strcmp(list[j], pivot)>=0)) i++; 
        if(i<j) 
         */ 
    } 
     t = list[p]; list[p] = list[j]; list[j] = t;
    return j; 
} 

char **sortlist (char **list, int p, int r) 
{ 
     
     int j; 
     
    if(p<r) 
    { 
         
        j=partition(list,p,r); 
         
        sortlist(list,p,j-1); 
        sortlist(list,j+1,r); 
    } 
    return list; 
} 

void printlist(char *outputlist, char **list, int length) 
{ 
    int i; 
    FILE *out=fopen("outputlist.txt","w"); 
     
    for(i=0; i<length; i++) 
        fprintf(out,"%s\n",list[i]); 
    fprintf(out,"\n"); 
    fclose(out); 
} 

int main(int argc, const char *argv[]) { 

    char **list;     
    int length,size; 
    time_t start, end; 

    if(argc!=3) 
    { 
        printf("Usage: stringsort <input list> <output list>\n"); 
        return 1; 
    } 

    list=loadlist((char *)argv[1],&length,&size); 
    start=clock(); 

       list=sortlist(list,length,size); 
       end=clock(); 
         
    printf("%f\n",(double)(end-start)/(double)CLOCKS_PER_SEC); 
    printlist((char *)argv[2],list,length); 

    return 0; 
     
}