[C] ordinamento

[andreapav]

ciao! ho un programma di ordinamento (mergesort iterativo o non-ricorsivo, che dir si voglia...) e ho bisogno che ordini grandi quantità di dati...
il problema è che con ad esempio 100000 si pianta...con problemi di memoria ma non ben chiari sinceramente...

ho pensato che sia che ho gli indici del vettore in int e che magari vada in overflow ma però mi scrive i numeri correttamente (1000000 ad esempio) e quindi non so...

ho pensato anche che possa essere un problema che alloco troppa memoria e allora ho aggiunto un free ma non cambia una cippa...

vi posto il codice... se qualcuno ha qualche idea... io intanto provo a usare long come indici ma...non son convinto sia quello...

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

#define SIZE 100000

/*vettore contenente i dati*/
long *vector;

void getData2()
{
	int i;
	vector = (long*)malloc(SIZE*sizeof(long));
	for (i=0; i < SIZE; i++)
	{
		vector[i] = (long)rand(); 
	}
	printf("creati %d dati...\n",i);
}

/*funzione che verifica il corretto ordinamento*/
int ordinati(long v[], int numero)
{
	long a = v[0];
	long b;
	int i;
	for (i = 1; i < numero; i++)
	{
		b = v[i];
		if (b < a) return i;
		a = b;
	}
	return i;
}

void merge(long a[], int start, int center, int end, int size) {
        int i, j, k; 
        long *app;
	app = (long*)malloc(size*sizeof(long));
        i = start;
        j = center+1;
        k = 0;
 
        while ( (i <= center) && (j <= end) ) 
        {
             if (a[i] <= a[j]) 
  	  {
                        app[k++] = a[i++];
               }
	else 
	 {
                        app[k++] = a[j++];
              }
        }
 
        while ( i <= center ) 
                app[k++] = a[i++]; 
 
        while ( j <= end ) 
                app[k++] = a[j++]; 
 
        for (k = start; k <= end; k++)
                a[k] = app[k-start];
        
        free(app);     //QUESTO è IL FREE CHE SECONDO ME NON SERVE...
}

/*funzione che fa il mergesort non ricorsivo/iterativo*/ 
void mergesortI(long a[],int size) {
        int sizetomerge = size-1;
        int i;
        int n=2;

        size-- ;
 
        while ( n < sizetomerge*2 ) 
        {
             for (i = 0; (i+n-1) <= sizetomerge; i += n ) 
	{
                     merge(a,i,(i+i+n-1)/2,i+(n-1),sizetomerge); 
             }
             i--;
            if ( (sizetomerge + 1)%n != 0 ) 
	{
                   if (size > sizetomerge)
                                merge (a,sizetomerge -((sizetomerge)%n),sizetomerge,size,size);
                   sizetomerge=sizetomerge-((sizetomerge+1)%n);
  	}
            n = n*2;
        }

        if (size > sizetomerge) 
                merge (a,0,size-(size-sizetomerge),size,size);
}


/*main*/
int main(int argc, char** argv[])
{
	double numero = SIZE;    /*numero di dati da ordinare*/

	srand((int)time(NULL));
	getData2();

	/*sorting:*/
	printf("sorting...");
	mergesortI(vector,(int)numero);
	printf("completato.\n");

	/*controllo:*/
	creati = ordinati(vector,(int)numero);
	if (creati == (int)numero) 
		printf("Ordinamento effettuato correttamente. \n");
	else 
		printf("Ordinamento errato a: %d .\n",creati);

	return 0;
}

[andreapav]

sul mio computer va fino a 23108...

il problema credo sia che usa un'enormità di memoria (guardando con il task manager arriva fino a 2.8GB...) però è un metodo che non dovrebbe usare cosi tanta memoria...

free(..) deve essere sbagliata perchè mi pianta tutto anche con piccoli numeri

grazie in anticipo a chi mi da un suggerimento...

[goldorak]

Perche' non controlli il valore di ritorno della malloc ?
Il free non serve a niente se malloc non riesce ad allocarti la memoria necessaria.

[andreapav]

alòr... trovato l'inghippo...

il free forse, se scritto giusto potrebbe essere una soluzione, infatti succedeva che a ogni chiamata a merge allocava TOT spazio per usarlo solo a quella chiamata di merge.

SOLUZIONE: avere un long *app esterno a main e a ogni metodo comune a tutti insomma, la memoria allocata 1 volta sola, alla chiamata di mergesortI, in modo poi che in merge venga usato sempre lo stesso spazio di memoria e non ne allochi di nuova ogni volta.