Ошибка сегментации: 11 на малом входе для массива/вектора

Question

Есть несколько вопросов, связанных с этой ошибкой в ​​stackoverflow, и я понимаю, что это связано с избыточным использованием памяти массивом или при использовании указателей (я пробовал это с помощью векторов, а также), но используя небольшой массив, он все еще показывает эту ошибку. Тот же самый код раньше работал нормально (для сортировки по объему массива).

Мой вход был следующим:

Выход:

вина Сегментация: 11

#include<iostream> 
#include<vector> 
using namespace std; 

void merge(vector <int> ar, int l, int m, int r){ 
    int n1 = m-l+1; 
    int n2 = r-m; 

    int L[n1]; 
    int R[n2]; 

    for (int i = 0; i < n1; ++i) 
    { 
     L[i]=ar[l+i]; 
    } 

    for (int j = 0; j < n2; ++j) 
    { 
     R[j]=ar[m+j+1]; 
    } 

    int i,j; 
    i = j = 0; 
    int k = i; 


    while(i<n1 && j<n2){ 

     if (L[i]<R[j]) 
     { 
      ar[k]=L[i]; 
      i++; 
     } 
     else if (R[j]<L[i]) 
     { 
      ar[k]=R[j]; 
      j++; 
     } 
     k++; 

    } 

    while(i<n1){ 
     ar[k]=L[i]; 
     i++; 
     k++; 
    } 
    while(j<n2){ 
     ar[k]=R[j]; 
     j++; 
     k++; 
    } 


} 


void mergesort(vector <int> ar, int l, int r){ 
    int m; 
    m=r+(l-r)/2; 
    if (l<r) 
    { 


     mergesort(ar, l, m); 
     mergesort(ar, m+1, r); 
     merge(ar, l, m, r); 
    } 
} 

void print(vector <int> ar, int size){ 

    for (int i = 0; i < size; ++i) 
    { 
     cout<<ar[i]<< " "; 
    } 


} 

int main() 
{ 
    int n; 
    cin>>n; 
    vector <int> ar; 

    for (int i = 0; i < n; ++i) 
    { 
     cin>>ar[i]; 
    } 

    print(ar,n); 
    mergesort(ar, 0, n-1); 
    print(ar, n); 



    return 0; 
} 

Answer 1

Проблема частично связана с m=r+(l-r)/2. Когда l - 0 и r - 1, (l-r)/2 - 0. Это делает m равным 1, l, равным 0, и r, равным 1, и mergesort(ar, l, m);, который идентичен тому, с которым он только что работал. Стек становится неограниченным до тех пор, пока у вас не возникнет ошибка сегментации. Один из способов исправить это, который также сделает ваш код более эффективным, - это объединить списки, когда разница между l и r ниже определенного порога. Или, вы можете просто поменять местами два элемента, когда вы дойдете до точки, где l и r отличаются по одному, например, так:

if (l - r <= 1) { 
    int temp = ar[l]; 
    ar[l] = ar[r]; 
    ar[r] = temp; 
    return; 
}