Почему этот алгоритм сортировки слияния счетчиков ошибок дает неправильный ответ

Question

Вот код, который я написал для подсчета инверсии в C++. Если вы напишете какой-нибудь другой метод рекурсии. Пожалуйста, попробуйте объяснить это мне. Я храню счет инверсии в countI. Я получаю 2 как вывод для массива A [], который был объявлен в основной функции.

#include<iostream> 
#include<math.h> 


    using namespace std; 
    int countI = 0; 
    void merge(int A[], int p, int q, int r) 
    { 
     int n1 = q - p + 1; 
     int n2 = r - q; 
     int *L; 
     L = new int[n1]; 
     int *R; 
     R = new int[n2]; 
     for (int i = 1; i <= n1; i++) 
     { 
      L[i] = A[p + i - 1]; 
      // cout << A[p + i - 1]<<endl; 
      //cout << L[i]; 
     } 
     for (int j = 1; j <= n2; j++) 
      R[j] = A[q + j]; 
     int i = 1, j = 1; 

     // cout << "li " << L[n1]<<"\t"<<R[n2]; 

     for (int k = p; k <= r; k++) 
     { 

      if ((L[i] <= R[j] && i <= n1) || j>n2) 
      { 
       A[k] = L[i]; 
       //cout << A[k]; 
       i++; 

      } 
      else 
      { 
       A[k] = R[j]; 
       j++; 
       if (i<n1) 
       countI += n1 - i+1; //here I am counting the inversion. 
       //cout <<endl<<"R"<< R[j]; 
      } 
     } 
    } 
    void mergeSort(int A[], int p, int r) 
    { 
     if (p < r) 
     { 
      //  cout << A[8]; 
      int sum = p + r; 
      //int q = (sum)/2 + (sum % 2); 
      int q = (sum)/2; 
      mergeSort(A, p, q); 
      mergeSort(A, q + 1, r); 
      merge(A, p, q, r); 

     } 
    } 



    int main() 
    { 
     //I am considering array from index 1 
     int A[] = { 0, 1, 3, 5,2,4,6 }; 
    // int arr[100001]; 
     int i = 1; 
     int n = 0; 
     //while (scanf("%d", &n) != EOF) { arr[i++] = n; } 

     mergeSort(A, 1, 6); 
     for (int i = 1; i <= 6; i++) 
     { 
      cout << A[i] << " "; 
     } 
     cout << "\n " << countI; 
     system("pause"); 
     return 0; 
    } 

Answer 1

Следует отметить, что C++ использует 0 массивов на основе индексов. Первый элемент L и R равен 0, а не 1. То же самое, когда вы вызываете mergeSort в главном. try mergeSort (A, 0, 5)

Хотя вы согласны с вашей ошибкой индексирования, начиная с 1. Вы завершаете конец своих массивов на 1. Это может привести к сбою вашей программы; однако, когда вы этого не делаете, вы часто получаете странные ответы (которые трудно отлаживать), потому что вы неправильно получаете доступ и записываете память.

Вот несколько псевдокодов (для 0 индексированных массивов), которые будут подсчитывать инверсии при выполнении сортировки слияния.

merge(A, p, m , q){ 
    B = [] // array size of q - p + 1 
    i = p, j = m+1, k = 0, inv = 0 
    while (i <= m && j <= q){ 
    if (A[i] < A[j]) 
     B[k++] = A[i++] 
    else{ 
     B[k++] = A[j++] 
     inv += m - i + 1 
    } 
    } 
    while (i <= m)  // copy rest of left side to temp array 
    B[k++] = A[i++] // otherwise it may be overwritten 
    i = 0; 
    while (i < k){  // copy temp array elements back to A 
    A[p+i] = B[i] 
    ++i 
    } 
    return inv 
} 

merge_sort(A, p, q){ 
    if (p == q) 
    return 0; 
    m = floor((p + q)/2) 
    inv1 = merge_sort(A, p, m) 
    inv2 = merge_sort(A, m+1, q) 
    return inv1 + inv2 + merge(A, p, m, q) 
} 

// you can call it like this: 
A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} // 10 Elements 
inversions = merge_sort(A, 0, 9) // sort and count inversions from index 0 to index 9