[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 ? :stordita:
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.