losowe wartości przy użyciu scalania w seryjnej sortowania C++

Question

Za niewielką zadanie domowe, mam napisać prostą funkcję scalania, której prototyp wygląda następująco:

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

kierunki powiedzieć, że dla uproszczenia, że przyjmują tylko jedną tablicę, a[] i tę right_low = left_high + 1. . Jesteśmy również przechowywanie końcowe wartości oryginalnej tablicy a[] który został przekazany w istocie do tablicy z wartościami a[] = {1,3,10,4,7,8} wygląda to tak:

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

Dla tego zadania, mamy kilka testów musimy przejść . Pierwszy to proste połączenie dwóch tablic. Druga funkcja to funkcja merge_sort, którą wywołuje na niektórych losowo posortowanych tablicach. Oto moja realizacja 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]; 
} 

Kiedy nazywa pierwszy test, gdzie tylko sprawdza połączenie dwóch tablic, moja funkcja działa, a pojedyncza tablica jest teraz posortowana. Jednakże, gdy wywołuje funkcję merge_sort, kończę na uzyskiwaniu wartości śmieci. Oto jego funkcje testowe:

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

I z jakiegoś powodu moje wyjście kończy się wyglądać jak ten:

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 

Co jest nie tak z moim kodem seryjnej, które mogłyby być przyczyną tego?

Answer 1

Problem polega na tym, że niepoprawnie obliczasz liczbę wpisów w temp: Twój kod uważa, że ​​jest to right_high + 1, ale prawidłową formułą jest right_high - left_low + 1.

Na przykład, gdy wywołanie daje indeksy 10, 15, 16, 26, twój kod próbuje scalić 27 wartości, podczas gdy powinno się scalać tylko 17 (tj. Indeksy od 10 do 26 włącznie).

Nie ma znaczenia, kiedy left_low ma wartość zero, więc twój przypadek testowy działa dobrze. Ale gdy tylko left_low stanie się niezerowe, np. kiedy prawa połowa tablicy jest sortowana, twój kod "przereguluje" obie tablice, umieszczając wartości śmieci w tmp i zapisując wartości również w tablicy a.

Również zadania w ostatnim for pętli muszą być przesunięte left_low także:

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