C: Fusionner-Trier d’un tableau avec un nombre impair d’éléments

J’ai travaillé sur une affectation pour ma classe de programmation procédurale où nous avons reçu un programme de fusion-sorting qui ne fonctionne pas complètement. Il effectue un sorting par fusion sur des tableaux comportant un nombre pair d’entiers, mais génère une erreur de segmentation avec un nombre impair d’entiers.

Je comprends comment fonctionne le sorting et que la faute de segmentation est renvoyée car le nombre impair est à l’origine de la faute de segmentation car le tableau est surchargé d’une manière ou d’une autre. Je comprends également que la solution va impliquer un test pour savoir si le tableau d’origine est pair ou impair, puis passer les valeurs à la fonction de fusion différemment en fonction de cela. En dépit de ce que je comprends du programme, je me suis cogné la tête contre le mur pendant des semaines pour que cela fonctionne correctement et j’espère que quelqu’un pourra me donner des conseils.

J’ai beaucoup cherché les réponses avant de publier ceci, mais tous les autres exemples impliquent des programmes de fusion-sorting avec des structures, ce qui va au-delà de ce que j’ai appris jusqu’à présent. Vous verrez dans le code que je poste ci-dessous. En outre, le programme complet implique quelques autres fichiers, mais j’ai inclus uniquement les fichiers mergesort.c et merge.c qui, comme l’a assuré mon professeur, sont les seuls emplacements où des modifications doivent être apscopes. . Le fichier main fonctionne parfaitement et n’est responsable que du remplissage du tableau et de l’appel de la fonction mergesort . Si les autres fichiers sont nécessaires, faites-le moi savoir et je les posterai. La seule raison pour laquelle je ne l’ai pas fait, c’est parce que nous utilisons un shell Linux et que je n’ai pas trouvé de moyen pratique de copier et coller du code du shell dans mon propre système d’exploitation et qu’il faut un certain temps pour l’écrire.

Merci d’avance pour tous les conseils que vous pouvez fournir. Voici le code.

mergesort.c

 #include  void mergesort(int key[], int n) //key is the array, n is the size of key { int j, k, m, *w; w = calloc(n, sizeof(int)); assert(w != NULL); for (k = 1; k < n; k *= 2) { for (j = 0; j < n - k; j += 2 * k) { merge(key + j, key + j + k, w + j, k, k); } for (j = 0; j < n; ++j) { key[j] = w[j]; } } free(w); } 

fusionner.c

 #include "mergesort.h" void merge(int a[], int b[], int c[], int m, int n) { int i = 0, j = 0, k = 0; while (i < m && j < n) { if (a[i] < b[j]) { c[k++] = a[i++]; } else { c[k++] = b[j++]; } } while (i < m) { c[k++] = a[i++]; } while (j < n) { c[k++] = b[j++]; } } 

Votre code a quelques problèmes:

  • La directive d’inclusion du préprocesseur est incorrecte, utilisez #include "mergesort.h" ou #include .

  • Vous devez calculer correctement la taille des tableaux transmis à merge() afin que le contenu ne soit pas lu au-delà de la fin du dernier bloc. Dans l’état actuel du code, n doit être une puissance de 2 pour éviter tout comportement indéfini.

Voici une version corrigée de mergesort.c pour votre objective:

 #include "mergesort.h" void mergesort(int key[], int n) { // key is the array, n is the number of elements int i, j, k, m; int *w; // allocate the working array w = calloc(n, sizeof(int)); // abort the program on allocation failure assert(w != NULL); // for pairs of chunks of increasing sizes for (k = 1; k < n; k *= 2) { // as long as there are enough elements for a pair for (j = 0; j + k < n; j = j + k + m) { // compute the size of the second chunk: default to k m = k; if (j + k + m > n) { // chunk is the last one, size may be smaller than k m = n - j - k; } // merge adjacent chunks into the working array merge(key + j, key + j + k, w + j, k, m); // copy the resulting sorted list back to the key array for (i = 0; i < k + m; i++) { key[j + i] = w[j + i]; } } } free(w); } 

Voici quelques remarques supplémentaires sur cet exercice, mais vous n'êtes peut-être pas assez avancé et il est probablement interdit de modifier l'API:

  • L'utilisation de 2 fichiers sources différents semble excessive. La routine de merge est une fonction auxiliaire qui mérite d'être static . Il sera étendu en ligne par les compilateurs modernes.

  • Les tailles de tableau doivent être passées en tant que size_t juste après le pointeur correspondant (pour la cohérence).

  • Au lieu d'affirmer le succès de l'allocation, vous devez renvoyer un code d'échec et laisser le gestionnaire de l'appelant l'échec en douceur.

  • Vous pouvez utiliser le début du tableau de travail pour toutes les opérations de fusion. Cela améliore l'efficacité du cache.

Voici une version avec toutes ces modifications:

 #include "mergesort.h" static void merge(int a[], size_t m, int b[], size_t n, int c[]) { size_t i = 0, j = 0, k = 0; while (i < m && j < n) { if (a[i] < b[j]) { c[k++] = a[i++]; } else { c[k++] = b[j++]; } } while (i < m) { c[k++] = a[i++]; } while (j < n) { c[k++] = b[j++]; } } int mergesort(int key[], size_t n) { // key is the array, n is the size of key // return 0 for success, -1 for failure with error code in errno size_t i, j, k, m; int *w; w = calloc(n, sizeof(int)); if (w == NULL) return -1; for (k = 1; k < n; k *= 2) { for (j = 0; j + k < n; j += k + m) { m = k; if (j + k + m > n) { m = n - j - k; } merge(key + j, k, key + j + k, m, w + j); // copy the sorted chunk back to the key array for (i = 0; i < k + m; i++) { key[j + i] = w[i]; } } } free(w); return 0; } 

Vous pouvez encore améliorer l'implémentation en supprimant près de la moitié des tests sur les variables d'index dans la fonction merge() :

 static void merge(int a[], size_t m, int b[], size_t n, int c[]) { /* always called with m > 0 and n > 0 */ for (size_t i = 0, j = 0, k = 0;;) { if (a[i] < b[j]) { c[k++] = a[i++]; if (i == m) { while (j < n) { c[k++] = b[j++]; } break; } } else { c[k++] = b[j++]; if (j == n) { while (i < m) { c[k++] = a[i++]; } break; } } } } 

Vous pouvez améliorer mergesort et merge avec ces autres idées:

  • La comparaison du dernier élément de a et du premier élément de b en merge permet d’améliorer considérablement la vitesse des tableaux partiellement ou totalement sortingés.

  • merge peut renvoyer le nombre d'éléments à copier, en supprimant toute la copie dans le cas sortingé.

  • en copiant le bloc de gauche dans le tableau temporaire et en le fusionnant dans le tableau de key , vous pouvez réduire la taille du tableau temporaire.

  • La fusion de tailles de blocs équilibrés au lieu de puissances de 2 réduit le nombre total de comparaisons sans puissance de 2 tailles de masortingce, mais il est plus facile de la mettre en œuvre avec une approche récursive.

J’ai donc trouvé l’origine de votre erreur de segmentation. Si vous regardez de plus près la première boucle for interne de votre mergesort:

  for(j = 0; j < n - k; j += 2 * k) { merge(key + j, key + j + k, w + j, k, k); } 

vous remarquerez que la condition ne coïncide pas vraiment avec ce que vous donnez à la fonction de fusion en tant que limites pour vos tranches du tableau. La condition est j < n - k donc la valeur maximale de j est n - k - 1 . Mais dans les arguments de votre fusion, la seconde tranche de tableau que vous passez commence à la key + j + k et vous dites qu'elle a la taille k , vous vous retrouvez donc à l’indice j + k + k - 1 , si vous remplacez votre j par son la valeur maximale que vous obtenez n - k - 1 + k + k - 1 = n . Ce qui signifie que vous dites à la fonction de fusion qu'il peut aller jusqu'à l'indice n . Comme la taille de la clé est n, elle n’a pas d’indice n Alors, comment devez-vous réécrire votre condition? Nous venons de calculer l'indice maximal auquel la fusion accédera: j + k + k - 1 . Cela signifie donc que vous devez simplement définir j + k + k - 1 < n comme condition. ça signifie:

  for(j = 0; j <= n - (k*2); j += 2 * k) { merge(key + j, key + j + k, w + j, k, k); } 

Maintenant que nous nous sums débarrassés des erreurs de segmentation, nous pouvons passer à la deuxième partie: le faire fonctionner pour toutes les tailles. La raison pour laquelle cela ne fonctionne que pour les tailles qui ont une puissance de 2 (pas même toutes les tailles égales: essayez de sortinger ceci [2, 3, 5, 6, 4, 1] vous verrez) est à cause de votre k . C'est k qui détermine la taille des tranches qui seront fusionnées dans la boucle. k est multiplié par 2 après chaque tour, ainsi il n’obtiendra que des tailles d’une puissance de 2! Quand ce n'est pas une puissance de 2, il va simplement ignorer la partie qui "dépasse" la puissance de 2 ... si vous obtenez ce que je veux dire? Avant que nous apportions ce changement qui résolvait l'erreur de segmentation, il aurait simplement essayé de le faire mais échouerait pour cette raison (et renverrait une erreur). Ce que nous devons faire maintenant, c’est de faire en sorte que la dernière tranche qu’il ignore est sortingée. Je ne ferai que copier la fonction mergesort car c'est la seule chose qui va changer:

 void mergesort(int key[], int n) //key is the array, n is the size of key { int j, k, neglected, *w; w = calloc(n, sizeof(int)); assert(w != NULL); for(k = 1; k < n; k *= 2){ for(j = 0; j <= n - (k*2); j += 2 * k){ merge(key + j, key + j + k, w + j, k, k); } //size of part that got neglected (if it could fully be divided in slices of 2*k, this will be 0) neglected = n % (2*k); //copy everything except the neglected part (if there was none, it will copy everything) for(j = 0; j < n-neglected; ++j) { key[j] = w[j]; } if(neglected != 0 && neglected < n){ //couldn't devide it fully in slices of 2*k ==> the last elements were left out! merge them together with the last merged slice merge(key + n - (2*k) - neglected, key + n-neglected, w + n - (2*k) - neglected, 2*k, neglected); for(j = n - (2*k) - neglected; j < n; ++j) { //copy the part we just merged key[j] = w[j]; } } for(j = 0; j < n; ++j) { key[j] = w[j]; } } free(w); } 

De plus, mon compilateur se plaignait d'une variable que vous n'utilisiez pas: m