Рекурсивная функция сортировки слияния Предоставление плохого результата

Question

Я пытаюсь понять, почему моя функция сортировки слияния не работает. Я считаю, что проблема заключается в части слияния(). вот мой код:

int mergeSort(int *data, int left, int right) { 
    //divide 
    if (left < right) { 
     int q = floor((left + right)/2); 
     //conquer 
     mergeSort(data, left, q); 
     mergeSort(data, q + 1, right); 
     //combine 
     merge(data, left, q, right); 
    } 

    //print results for testing purposes 
    for (int i = 0; i < n; i++) { 
     cout << data[i] << "\n"; 
    } 

    return 0; 
} 

И вот его часть слияния(). Я считаю, что проблема в этой части.

int merge(int *data, int left, int q, int right) { 
    int *temp = data; 
    int i = left, j = q + 1, z = left; 
    int t1 = 0, t2 = 0; 
    while (i <= q && j <= right) { //while both variables have not reached the end of their sub arrays 
     if (temp[i] <= temp[j]) { 
      data[z] = temp[i]; 
      i++; 
     } 
     else { 
      data[z] = temp[j]; 
      j++; 
     } 
     z++; 
    } 
    //if subarrays are both sorted and in order, combine them 
    if (i < q) { 
     t1 = z, t2 = i; 
     for (t1; t1 < right;) { 
      data[t1] = temp[t2]; 
      t1++; 
      t2++; 
     } 
    } 

    else if (j < right) { 
     int t1 = z; int t2 = j; 
     for (t1; t1 <= right;) { 
      data[t1] = temp[t2]; 
      t1++; 
      t2++; 
     } 
    } 

Я думаю, что моя проблема исходит от объявления int *temp = data; в начале merge(). Моя мысль заключается в том, что я получаю какой-то конфликт адресов памяти между этими двумя массивами, но я не уверен.

Я попытался упорядочить данные в другом порядке и обнаружил, что когда данные нужно переместить из индекса n в индекс n-i, каждый индекс между этими двумя индексами заменяется значением n. Например:

прохождение в массиве {4, 13, 8, 12, 9 } вернется {4, 8, 8, 9, 9}

Моя другая мысль о том, что I и J переменные корректно не приращением. Я неоднократно повторял этот код и не мог найти решение.

Answer 1

Это (первая строка функции merge)

int *temp = data; 

делает НЕ скопировать массив; он просто создает другой указатель, указывающий на одну и ту же память. Это заставляет ваш код перезаписывать ваши данные.

Вы, вероятно, нужно сделать что-то вроде этого:

int * temp = new int [right - left + 1]; 
memcpy (temp, data + left, (right - left + 1) * sizeof(int)); 

и не забудьте delete[] память для temp в конце вашей функции:

delete[] temp; 

Заметим, что вы будете необходимо изменить использование z; он должен начинаться с 0, а не с left.

(Следующие необязательные улучшения производительности, вы можете их игнорировать.) Выделение и освобождение памяти в каждой функции merge - плохая идея. Специально, поскольку мы точно знаем, сколько общей дополнительной памяти нам нужно для слияния: массив точно n целых чисел.

По этой причине лучше передать другой массив того же размера вместе с data в mergeSort, поэтому его можно использовать в качестве скреста памяти (то есть временной памяти) для слияния. Или, если вы действительно умны, вы можете пинг-понг между фактической и царапиной памятью, чтобы свести к минимуму копирование.