Fusion de deux tableaux triés avec la boucle for

Question

J'ai une fonction qui fusionne deux tableaux triés en un et lui renvoie un pointeur. Je veux utiliser une boucle for plutôt que d'un moment. Cependant, dans certains cas de test, les 1 ou 2 derniers éléments du tableau de fusion ne sont pas à leur place. J'apprécierais que quelqu'un puisse aider à résoudre ce problème en gardant la boucle for.

int * mergeSort(int arr1[], int arr2[],int len) 
{ 

    /* len is the combined length of the two arrays */ 

    static int sorted[100]; 

    int pos1=0, pos2=0; 

    for (int i=0; i<len; i++) 
    { 
     if (arr1[pos1]<=arr2[pos2]) 
     { 
      sorted[i]=arr1[pos1]; 
      pos1++; 
     } 
     else 
     { 
      sorted[i]=arr2[pos2]; 
      pos2++; 
     } 
    } 

    return sorted; 
} 

Answer 1

Votre problème est que vous ne semblez pas gérer dépassant la fin des tableaux d'entrée. S'il y a de la mémoire non initialisée, vous obtenez un comportement indéfini.

Vous pouvez éviter cela en mettant fin à vos tableaux d'une valeur sentinelle, par exemple INT_MAX, qui doit toujours être plus grand que toutes les valeurs possibles dans les tableaux:

int a[] = { 1, 2, 104, INT_MAX}; 
int b[] = { 101, 102, 105, INT_MAX}; 

int* ptr = mergeSort(a,b,6); 

for(int i = 0; i < 6; i++){ 
    cout << i << " " << ptr[i] << endl; 
} 

live demo

Ou vous pouvez passer les longueurs réelles des deux tableaux et les gérer correctement:

int * mergeSort(int arr1[], int len1, int arr2[],int len2) 
{ 

    /* len is the combined length of the two arrays */ 

    static int sorted[100]; 

    int pos1=0, pos2=0; 

    for (int i=0; i< len1 + len2; i++) 
    { 
     if ((pos2 == len2) || (arr1[pos1] <= arr2[pos2] && (pos1 < len1))) 
     { 
      sorted[i]=arr1[pos1]; 
      pos1++; 
     } 
     else 
     { 
      sorted[i]=arr2[pos2]; 
      pos2++; 
     } 
    } 

    return sorted; 
} 

live demo

Answer 2

Cela ne répond pas à la question de ce qui ne va pas avec votre code, mais pour répondre à la question de savoir comment fusionner deux gammes triées je suggère std::merge:

int * mergeSort(int arr1[], int arr2[], int len1, int len2) 
    { 
     //I am not condoning the use of a static buffer here, 
     //I would probably use a std::vector or std::array, 
     //possibly a boost::static_vector if really necessary 
     static int sorted[100]; 
     std::merge(arr1, arr1 + len1, arr2, arr2 + len2, sorted); 
     return sorted; 
    } 

J'ai aussi changé int len à int len1, int len2 parce que vous besoin de connaître les longueurs des réseaux individuels, pas seulement leur longueur combinée, pour éviter de lire au-delà de la fin des tableaux d'entrée.