ne peut pas trouver l'erreur dans ce programme mergesort en c..always montre une erreur de segmentation

Question

Je ne peux pas trouver l'erreur dans ce programme Mergesort en C. Il montre toujours une erreur de segmentation.

C'est mon code par la voie pour Mergesort:

Je pense que le problème peut être ici:

void merge(int *a, int i, int mid, int n) { 
    int l, m, k, b[10]; 

    l = i; 
    m = mid + 1; 
    k = 0; 

    while (l <= mid && m <= n) { 
     if (a[l] > a[m]) 
      b[k++] = a[l++]; 

     if (a[m] > a[l]) 
      b[k++] = a[m++]; 
    } 

    while (l <= mid) 
     b[k++] = a[l++]; 

    while (m <= n) 
     b[k++] = a[m++]; 

    for (k = 0; k < n; k++) 
     a[i++] = b[k]; 

    return ; 
} 

Answer 1

Vers la fin de votre fonction (entre autres ..):

for(k=0;k<n;k++) // k = [0 -> n) 
    a[i++]=b[k]; // but b is declared as int b[10], this is surely not right. 

La boucle ci-dessus implique que vous attendez b pour contenir exactement n éléments à un certain point. Pourquoi 'b' n'est pas dimensionné correctement?

Answer 2

Il y a plusieurs problèmes dans votre code:

• l'argument mid semble être l'indice du dernier élément dans la moitié gauche et n l'index du dernier élément de la moitié droite. Ceci est incompatible avec la pratique courante en C, i est l'index à la moitié gauche, mid devrait être l'indice du premier élément de la moitié droite et n devrait être l'indice du premier élément au-delà de la moitié droite. De cette façon, les longueurs de tableau sont faciles à calculer en soustrayant l'indice initial de l'indice au-delà du dernier élément.

• b est allouée localement comme un tableau de taille 10. Ceci est incorrect si la taille du morceau à fusionner est plus grand que 10. Vous pouvez soit allouer un tableau de (n - i) éléments avec malloc() ou définir un tableau local int b[n - i]; si la taille du tableau à trier est pas trop grand (moins 1 million d'entrées pour un environnement 64 bits moderne).

• l est un mauvais choix pour le nom d'une variable locale: il est graphiquement trop proche de 1, créant des erreurs potentielles et de la confusion. Les tests dans la boucle de fusion principale sont à la fois redondants et incomplets: vous ne gérez pas le cas où l'élément de la moitié gauche est égal à celui de la moitié droite.

• la dernière boucle, la copie des données fusionnées de nouveau dans le tableau source est défectueuse: il faut lire:

  for (k = 0; k < n - i; k++) 
      a[i++] = b[k]; 
  

Voici une version corrigée pour les tableaux modérément petits:

void merge(int *a, int start, int mid, int end) { 
    int i, j, k, b[end - start]; 

    i = start; 
    j = mid; 
    k = 0; 

    while (i < mid && j < n) { 
     if (a[i] <= a[j]) 
      b[k++] = a[i++]; 
     else 
      b[k++] = a[j++]; 
    } 
    while (i < mid) { 
     b[k++] = a[i++]; 
    } 
    while (j < n) { 
     b[k++] = a[j++]; 
    } 
    for (i = start, k = 0; i < end; i++, k++) { 
     a[i] = b[k]; 
    } 
} 

void mersort(int *a, int length) { 
    if (length > 1) 
     int mid = length/2; 
     mergesort(a, mid); 
     mergesort(a + mid, length - mid); 
     merge(a, 0, mid, length); 
    } 
}