Zusammenführen von zwei sortierten Arrays mit for-Schleife

Question

Ich habe eine Funktion, die zwei sortierte Arrays zu einem vereinigt und einen Zeiger darauf zurückgibt. Ich möchte eine for-Schleife statt einer Weile verwenden. In einigen Testfällen sind jedoch die letzten 1 oder 2 Elemente des Merge-Arrays nicht an ihrem Platz. Ich würde schätzen, wenn jemand helfen kann, dieses Problem zu lösen, das die for Schleife behält.

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

Ihr Problem besteht darin, dass Sie nicht damit umgehen, über das Ende der Eingabearrays hinauszugehen. Wenn es nicht initialisierten Speicher gibt - Sie erhalten undefiniertes Verhalten.

Sie können dies vermeiden, indem Sie Ihre Arrays mit einem Sentinel-Wert beendet wird, zum Beispiel INT_MAX, die immer größer sein sollte als alle möglichen Werte in den Arrays:

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

Oder Sie können passieren die tatsächlichen Längen der beiden Arrays und zu handhaben, sie richtig:

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

Das beantwortet nicht die Frage, was mit Ihrem Code falsch ist, aber die Frage zu beantworten, wie zwei sortierte Bereiche verschmelzen ich std::merge vorschlagen würde:

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; 
    } 

auch int len zu int len1, int len2 weil Sie änderte ich Sie müssen die Längen der einzelnen Arrays kennen, nicht nur ihre kombinierte Länge, um zu vermeiden, dass über das Ende der Eingabearrays hinaus gelesen wird.