Buonasera a tutti,
sto lavorando da diversi giorni sul kMergeSort, ovvero il MergeSort che lavora su k partizioni.
Non riesco a capire dove il mio algoritmo non lavora bene.
Vi metto il codice che ho prodotto, se qualcuno mi riesce a dare dei consigli lo ringrazio anticipatamente.
#include <stdio.h>
#include <stdlib.h>
void printlist(int *A, int n) {
int i;
for(i=0; i<n; i++)
printf("%d ",A);
printf("\n");
}
int *readlist(char *file, int *n) {
FILE *in = fopen(file,"r");
int *list,i,x;
if(in==NULL) return NULL;
i=0;
while(fscanf(in,"%d",&x)!=EOF) i++;
*n=i;
if((list = (int *)calloc(*n,sizeof(int)))==NULL)
return NULL;
rewind(in);
i=0;
while(fscanf(in,"%d",&x)!=EOF) list[i++]=x;
fclose(in);
return list;
}
/*
* Implementazione della procedura di ordinamento.
*/
void Merge(int A[] ,int p, int q, int r) {
int i = p;
int j = q+1;
int k = 0;
int *B = (int*)malloc((r-p)*sizeof(int));
while ((i <= q) && (j <= r)) {
if (A <= A[j]) {
B[k] = A;
i++;
}
else {
B[k] = A[j];
j++;
}
k++;
}
while( i <= q ) {
B[k] = A;
i++;
k++;
}
while ( j <= r ) {
B[k] = A[j];
j++;
k++;
}
for(k = p; k < r ; k++)
A[k] = B[k-p];
free(B);
}
void InsertionSort ( int A[], int p, int r ) {
int i,j, key;
if (p < r) {
for (j= p+1; j <= r; j++) {
key = A[j];
i = j-1;
while (i >= 0 && A >= key) {
A[i+1] = A;
i--;
}
A[i+1] = key;
}
}
}
int* Split( int k, int p, int r) {
int *L = (int*)malloc((k+1)*sizeof(int));
int j = ( r-p+1 ) / k; // elementi per sub-array
int i;
for (i=0; i<k; i++)
L = p + (i*j);
L = r;
return L;
}
void kMerge( int* A, int* L, int k ) {
int i;
for (i=0; i<(k-2); i++)
Merge(A, L[0], L[i+1]-1, L[i+2]-1);
}
void kMergeSort( int* A, int k, int p, int r) {
if ( r - p + 1 <= k ) {
InsertionSort(A, p, r);
}
if ( r - p + 1 > k) {
int *L,i;
L = Split(k, p, r);
for (i=0; i<(k); i++) {
kMergeSort(A, k, L, L[i+1]-1);
}
kMergeSort(A, k, L, L[i+1]);
kMerge(A,L,k);
free(L);
}
}
int main(int argc, char *argv[]) {
int *list,n,k;
if(argc!=3) {
fprintf(stderr,"Usage: kMergesort <list> <k>\n");
return 1;
}
if((list=readlist(argv[1],&n))==NULL) {
fprintf(stderr,"Error reading %s\n",argv[1]);
return 1;
}
if((k=atoi(argv[2]))<2) {
fprintf(stderr,"Error: the k parameter %d should be >= 2\n",k);
return 1;
}
kMergeSort(list, k, 0, n);
printlist(list,n);
free(list);
return 0;
}