Zufallswerte, wenn in Mergesort C++

Question

Für eine kleine Hausaufgabe mit verschmelzen, ich bin eine einfache Merge-Funktion, die schreiben soll Prototyp dies wie folgt aussieht:

void merge(int a[], int left_low, int left_high, int right_low, int right_high) 

die Richtungen sagen, dass die Einfachheit halber, wir nehmen nur ein einziges Array, a[] und das right_low = left_high + 1. . Wir sind auch die endgültigen Werte im ursprünglichen Array Speicherung a[], die übergeben wurde im Wesentlichen für ein Array mit Werten a[] = {1,3,10,4,7,8} es sieht wie folgt aus:

a = {1, 3,  10 ,   4, 7,  8} 
    ^  ^  ^   ^
    left_low left_high right_low  right_high 

Für diese Aufgabe haben wir ein paar Tests haben wir weitergeben . Die erste ist eine einfache Zusammenführung zwischen zwei Arrays. Die zweite ist die Lehrer eigene merge_sort Funktion, die er auf einige nach dem Zufallsprinzip sortiert Arrays anruft. Hier ist meine Implementierung von merge():

void merge(int a[], int left_low, int left_high, 
        int right_low, int right_high) { 
    int temp[right_high + 1]; // temporary array to store the result 
    int left_i = left_low, right_i = right_low, temp_i = 0; 

    // while the temporary array is not filled 
    while(temp_i != right_high + 1) 
    { 
     if(left_i == left_high + 1) 
      temp[temp_i++] = a[right_i++]; 
     else if(right_i == right_high + 1) 
      temp[temp_i++] = a[left_i++]; 
     else if(a[left_i] < a[right_i]) 
      temp[temp_i++] = a[left_i++]; 
     else 
      temp[temp_i++] = a[right_i++]; 
    } // end while 
    for(int i = 0; i < temp_i; ++i) 
     a[i] = temp[i]; 
} 

Wenn er ruft den ersten Test, wo er prüft nur die Verschmelzung von zwei Arrays, meine Funktion arbeitet, und die einzelne Array wird nun sortiert. Wenn er jedoch seine merge_sort-Funktion aufruft, bekomme ich am Ende Müllwerte. Hier sind seine Testfunktionen:

template<class T> 
void print (std::string label, T a[], int length, bool report_sorted) { 
    bool sorted = true; 
    std::cout << label; 
    for (int i=0; i<length; ++i) { 
    std::cout << a[i]; 
    if (i == length-1) 
     std::cout << std::endl; 
    else { 
     std::cout << ", "; 
     if (a[i] > a[i+1]) 
     sorted = false; 
    } 
    } 
    if (report_sorted) 
    std::cout << (sorted ? " Sorted" : " Not Sorted") << std::endl; 
} 

void shuffle(int values[], int length) { 
    std::vector<int> v_values; 
    for (int i=0; i<length; ++i) 
    v_values.push_back(values[i]); 
    std::random_shuffle(v_values.begin(),v_values.end()); 
    for (int i=0; i<length; ++i) 
    values[i] = v_values[i]; 
} 

//Recursive Merge Sort 
template<class T> 
void merge_sort(T a[], int low, int high) { 
    if (high - low < 1)    //Base case: 0 or 1 value to sort -> sorted 
    return; 
    else { 
    int mid = (low + high)/2;  //Split in 1/2 
    merge_sort(a, low, mid);  //Recursively sort low to mid 
    merge_sort(a, mid+1, high);  //Recursively sort mid+1 to high 
    merge(a, low,mid, mid+1,high); //Merge sorted parts of array 
    } 
} 

//Standard Merge Sort (calls a generalized one, with more parameters) 
template<class T> 
void merge_sort(T a[], int length) { 
    merge_sort(a, 0, length-1); 
} 

std::cout << "\n\nTesting merge in merge sort" << std::endl; 
    int test_merge_sort[10] = {1,2,3,4,5,6,7,8,9,10}; 
    for (int i=0; i<5; i++) { 
     shuffle(test_merge_sort, 10); 
     print("\n Array before sort: ", test_merge_sort, 10, false); 
     merge_sort(test_merge_sort, 10); 
     print(" Array after sort: ", test_merge_sort, 10, true); 
    } 

Und aus irgendeinem Grund, meine Ausgabe endet wie folgt aussehen:

Array before sort: 3, 9, 2, 5, 8, 4, 6, 10, 1, 7 
    Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146 
    Not Sorted 

    Array before sort: 1995111146, 1975317641, 4, 0, -944749486, 5443192, 5443196, 5439488, 4, -944749486 
    Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146 
    Not Sorted 

    Array before sort: -944749486, -944749486, 5443196, 4, 5439488, 1995111146, 5443192, 1975317641, 0, 4 
    Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146 
    Not Sorted 

    Array before sort: 1975317641, -944749486, 4, 4, 5439488, 5443192, 5443196, -944749486, 0, 1995111146 
    Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146 
    Not Sorted 

    Array before sort: -944749486, 5443192, 5443196, 1975317641, 4, 0, -944749486, 5439488, 1995111146, 4 
    Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146 
    Not Sorted 

Was läuft falsch mit meinem merge-Code, der dies verursacht werden könnte?

Answer 1

Das Problem ist, dass Sie die Anzahl der Einträge in temp falsch berechnen: Ihr Code denkt, dass es right_high + 1 ist, aber die richtige Formel ist right_high - left_low + 1.

Zum Beispiel, wenn ein Aufruf gibt Ihnen die Indizes 10, 15, 16, 26, versucht Ihr Code 27 Werte zu verschmelzen, während es nur 17 zusammengeführt werden sollte (d. H. Indizes 10 bis einschließlich 26).

Das macht keinen Unterschied, wenn left_low Null ist, also läuft Ihr Testfall gut. Sobald jedoch left_low ungleich Null wird, z. Wenn die rechte Hälfte des Arrays sortiert wird, "überstrahlt" Ihr Code beide Arrays und setzt die Werte für den Speicher in tmp und überschreibt die Werte im Array a.

Auch die Zuordnungen in der letzten for Schleife müssen bei left_low auch versetzt sein:

for(int i = 0; i < temp_i; ++i) 
    a[i+left_low] = temp[i];