[C] algoritmo counting sort

[MrX87]

Ciao a tutti...stavo provando a capire un pò l'algoritmo del counting sort...e inizialmente avevo imparato a farlo manualmente, adesso stavo provando ad implementarlo (uso devC++ su winXP)...posto il codice così si capisce meglio...

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

int* read_seq ( int* seq, int* dim );
int search_max ( int* seq, int dim );
int end ( int* v, int max );

int main ()
{
    int *seq;
    int *vR, *vS;
    int i, j, k;
    int dim=0, max;
    
    seq = read_seq ( seq, &dim );   
    
    max = search_max ( seq, dim );
    
    vR = (int*)malloc((max)*sizeof(int));  //allocazione vettore ricorrenze//
    vS = (int*)malloc((max)*sizeof(int));  //allocazione vettore somma//

    for ( k=0; k<max; k++ ) {
        vR[k]=0;
        vS[k]=0;
    }
    
    for ( k=0; k<max; k++ ) {
        for ( j=1; j<=dim; j++ ) {
            if ( seq[j] == k ) {
                vR[k]++;
            }
        }
    }

    vS[0] = vR[0];
    for ( k=1; k<max; k++ ) {
        vS[k] = vS[k-1] + vR[k];
    }
    
    j=k=0;
    do {
        for ( k=0; k<max; k++ ) {
            if ( vS[k]!=0 && vR[k]!=0 ) {
               i = vS[k];
               seq[i] = k;    
               vS[k]--;
               vR[k]--;
            } 
        }
    } while ( end( vR, max ) == 1 );
    
    //stampa vettore ordinato//
    for ( k=1; k<=dim; k++ ) {
        printf ("%3d", seq[k]);
    }
    printf ("\n");
    
    free(seq);
    free(vS);
    free(vR);
    
    system("pause");
    return(1);
}
int* read_seq ( int* seq, int* dim ) 
{
    int i, k;
    FILE *aptr;

    aptr = fopen ("sequenza.txt","r");
    
    if ( aptr == NULL ) {
         printf ("Errore apertura file\n");
         exit(1);
    }
    while ( fscanf(aptr,"%d", &k) != EOF ) {
          (*dim)++;
    }
    seq = (int*)malloc((*dim)*sizeof(int));
    if ( seq == NULL ) {
         printf ("Errore di allocazione\n");
         exit(1);
    }
    rewind(aptr);
    i=1;
    while ( fscanf(aptr,"%d", &seq[i]) != EOF && i<=(*dim) ) {
          i++;
    }
    fclose(aptr);
    return (seq);
}
int search_max ( int* seq, int dim )
{
     int i, max;
     
     max = seq[1];
     for ( i=1; i<=dim; i++ ) {
        if ( max < seq[i] ) {
            max = seq[i];
        }
     }
     return(max+1);
}
int end ( int* v, int max )
{
    int i;
    int r=0;

    for ( i=0; i<max; i++ ) {
        if ( v[i] == 0 ) {
           r++;
        }
    }
    if ( r == max ) {
        return(-1);
    }
    else return 1;
}

ecco..questo è quello che ho provato a scrivere...però...inizialmente funzionava...poi ad un tratto ho provato a cambiare sequenza nel fine "sequenza.txt" e ad un tratto non legge più!! ovvero la riga:

while ( fscanf(aptr,"%d", &k) != EOF ) {
          (*dim)++;
    }

non so perchè, ma clicla all'infinito...eppure non ho cambiato niente...mah...
comunque volevo sapere anche se come implementazione può essere considerata decente...o se è completamente inefficiente...
grazie mille

[Samuele_70]

Ad un primo sguardo al codice, si direbbe un errore di indicizzazione.
Ti ricordo che in C/C++ gli indici dei vettori iniziano dall'elemento 0,
e non dall'elemento B]1[/B].

[MrX87]

ma noi abbiamo scritto volutamente in quel modo perchè altrimenti co dava problemi se nella sequenza c'era il numero zero...