mergesort C mise en œuvre

Question

J'ai écrit ce code en langage C sur Xcode en suivant l'algorithme de mergesort. Le problème est que parfois j'obtiens EXC_BAD_ACCESS et je ne peux pas gérer où l'erreur est! L'algorithme de fusion devrait fonctionner (je l'ai essayé en dehors de la fonction mergesort et fonctionne!). Merci pour votre aide et votre patience!

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define DIM 6 

void mymerge (int v[], int i1,int i2, int last); //mergesort core: merge two ordinated arrays in one bigger ordinated array 
void mymergesort (int v[], int lower, int upper);//mergesort 
void printv (int v[],int lower, int upper); 

int main() { 
    int i; 
    srand((unsigned int)time(NULL)); 
    int v[DIM]; 
    for (i=0; i<DIM; i++) 
     v[i]=rand()%15; 
    printv(v, 0, DIM-1); 
    getc(stdin); 
    mymergesort(v, 0, DIM-1); 
    printv(v, 0, DIM-1); 
} 
void printv (int v[],int lower, int upper){ 
    int i; 
    for (i=lower; i<=upper; i++) 
    printf("%d\t",v[i]); 
} 
void mymergesort (int v[], int lower, int upper){ 
    int mid=(upper+lower)/2; 
    if (upper<lower) { 
     mymergesort(v, lower, mid); 
     mymergesort(v, mid+1, upper); 
     mymerge(v,lower,mid+1,upper); 
    } 
} 
void mymerge (int v[], int i1,int i2, int last){ 
    int i=i1,j=i2,k=i1,*vout; 
    vout=(int*)malloc((last-i1+1)*sizeof(int)); 
    while (i<i2 && j<=last) { 
     if (v[i]<=v[j]) { 
      vout[k++]=v[i++]; 
     }else { 
      vout[k++]=v[j++]; 
     } 
    } 
    for (;i<i2;i++) vout[k++]=v[i]; 
    for (;j<=last;j++) vout[k++]=v[j]; 
    for (k=i1; k<=last; k++) v[k]=vout[k]; 
free(vout); 
} 

EDIT: merci beaucoup! mais je pense qu'il y a un autre problème, quand j'essaye de trier un plus grand tableau (200 éléments), le programme ne fonctionne pas (j'obtiens une erreur malloc: la somme de contrôle incorrecte pour l'objet libéré a probablement été modifiée). Mais si je l'exécute à partir du débogueur xCode tout fonctionne bien

Answer 1

Ceci: vout=(int*)malloc((last-i1)*sizeof(int)); est faux.

D'abord, le nombre d'éléments que vous voulez est last-i1+1, pas last-i1 - classique off-by-1. Ce genre d'erreur est l'une des raisons pour lesquelles la convention en code C est de rendre les limites inférieures inclusives et les limites supérieures exclusives - moins +1 et -1 que vous devez faire, moins d'occasions de bousiller. L'erreur la plus grave est que vous indiquez vout à partir de i1. Si vous le faites de cette façon, vous devez allouer last+1 élément pour vout, et vous n'utilisez jamais le premier i1 (index 0 .. i1-1). Correction: Tout d'abord, allouez les éléments last-i1+1. Deuxièmement, initialisez k à 0 au début, pas i1. Troisièmement, modifiez la copie finale pour être

for (k=i1; k<=last; k++) v[k] = vout[k-i1]; 

Answer 2

Vous avez deux problèmes. La première est que votre calcul du point milieu est incorrect - vous utilisez (upper - lower)/ 2, mais ce n'est pas garanti entre lower et upper. Ce que vous voulez réellement, c'est lower + (upper - lower)/2. Il est également pas nécessaire de faire un travail s'il n'y a que 1 nombre dans l'intervalle à trier - donc la fonction mymergesort() devrait ressembler à:

void mymergesort (int v[], int lower, int upper) 
{ 
    if (upper > lower) { 
     int mid = lower + (upper - lower)/2; 

     mymergesort(v, lower, mid); 
     mymergesort(v, mid+1, upper); 
     mymerge(v,lower,mid+1,upper); 
    } 
} 

Le deuxième problème est celui de la fonction mymerge() déjà signalé par Fabian Giesen .

Answer 3

#include<stdio.h> 
#include<conio.h> 
#define max 20 
/*** function for merging the adjecent subarrays in sorted order ***/ 
void merge(int A[max],int n,int low,int high, int mid) 
{ 
    int i=low,j=mid+1,k,temp; 
    while((i<=j)&&(j<=high))  
    { 
     if(A[i]>A[j])   /** if element of the second half is greater then exchg and shift **/ 
     { 
      temp=A[j]; 
      for(k=j;k>i;k--) /** shifting the elements **/ 
      { 
      A[k]=A[k-1]; 
      } 
      A[i]=temp; 
      j++; 
     } 
     i++; 
    } 
} 
/******* iterative function for merge sort ********/ 
void merge_sort(int A[max],int n,int low,int high) 
{ 
    int mid; 
    if(low<high)      /** terminating condition **/ 
    { 
     mid=(high+low)/2;   /** calculating the mid point ***/ 
     merge_sort(A,n,low,mid);  /*** recursive call for left half of the array ***/ 
     merge_sort(A,n,mid+1,high); /*** recursive call for right half of the array ***/ 
     merge(A,n,low,high,mid); /** merging the both parts of the array **/ 
    } 
} 
/******* begening of the main function **********/ 
int main() 
{ 
    int A[max],n,i; 
    /** reading the inputs fro users **/ 
    printf("\n enter the size of the array\n"); 
    scanf("%d",&n); 
    printf("\n enter the array \n"); 
    for(i=0;i<n;i++) 
    { 
     scanf("%d",&A[i]);     
    } 
    /*** calling merge sort ***/ 
    merge_sort(A,n,0,n-1); 
    /** printing the sorted array **/ 
    for(i=0;i<10;i++) 
    { 
     printf("\n\t%d",A[i]);     
    } 
    getch(); 
    return 0; 
} 

Answer 4

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

void merge(int *a, int n1, int *b, int n2, int *arr) 
{ 
    int i=0, j=0, n=0; 
    while(i<n1 && j<n2) 
    { 
    if (a[i] < b[j]) 
    { 
     arr[n++] = a[i]; 
     i++; 
    } 
    else 
    { 
     arr[n++] = b[j]; 
     j++; 
    } 
    } 
    while(i < n1) 
    arr[n++] = a[i++]; 
    while(j < n2) 
    arr[n++] = b[j++]; 
} 
void merge_sort(int *a, int n) 
{ 
    int left[n/2], right[n-n/2],i=0; 
    if (n<=1) 
    return ; 
    while(i<n/2) 
    left[i] = a[i++]; 
    while(i<n) 
    right[i - n/2] = a[i++]; 
    merge_sort(left, n/2); 
    merge_sort(right, n-n/2); 
    merge(left, n/2, right, n-n/2, a); 
} 
void main() 
{ 
    int a[] = { 6, 5, 3, 1,9, 8, 7, 2, 4},i; 
    merge_sort(a,sizeof(a)/sizeof(a[0])); 
    for(i=0;i<9;i++) 
    printf("--%d",a[i]); 
    printf("\n"); 
} 


-- s.k