PDA

Visualizza la versione completa : [c] Funzione mergesort


Anna87_m
29-06-2009, 20:13
Sto cercando di ordinare un vettore di double con il metodo merge sort ma non riesco...io utilizzo questo codice


void Merge(double A[], int p, int q, int r)
{
int i, j, k;
double *B;

i = p;
j = q+1;
k = 0;
B=(double*)malloc (sizeof(double));
while (i<=q && j<=r) {
if (A[i]<A[j]) {
B[k] = A[i];
i++;
} else {
B[k] = A[j];
j++;
}
k++;
}
while (i<=q) {
B[k] = A[i];
i++;
k++;
}
while (j<=r) {
B[k] = A[j];
j++;
k++;
}
for (k=p; k<=r; k++)
A[k] = B[k-p];
return;
}

void MergeSort(double A[], int p, int r)
{
int q;

if (p<r) {
q = (p+r)/2;
MergeSort(A, p, q);
MergeSort(A, q+1, r);
Merge(A, p, q, r);
}
}

YuYevon
29-06-2009, 20:58
E' sbagliata la chiamata a malloc() nella funzione Merge(): cosė come l'hai scritta, allochi spazio per un solo elemento di tipo double, ma a te ne servono r - p + 1, quindi basta scrivere:

B = (double*) malloc ( ( r - p + 1 ) * sizeof(double) );

e dovrebbe andare. Tra l'altro ti consiglio pure di chiamare free() alla fine di Merge() prima di return

free(B);

in maniera tale da evitare memory leaks ;)

Loading