Ошибка сегментации: 11 MergeSort

Question

Я пытаюсь реализовать алгоритм сортировки слияния, и я получаю ошибку сегментации. Зачем? Ошибка, похоже, в функции MergeSort. Функция сортировки слияния (при втором вызове), когда должна проверять только массив из 4 чисел (длина должна быть 4), показывает длину = 27. Почему? (Проверено на массив из 8 элементов)

#include<iostream> 
using namespace std; 

int n, A[1000]; 

void citire(int lungime) { 
    for (int i = 0; i < lungime; i++) cin >> A[i]; 
} 

void afisare(int lungime) { 
    for (int i = 0; i < lungime; i++) 
     cout << A[i] << " "; 
    cout << '\n'; 
} 

int lungime(int A[]) { 
    int i = 0; 
    while (A[i]) i++; 
    return i; 
} 

void Merge(int L[], int R[], int A[]) { 
    int nL = lungime(L); 
    int nR = lungime(R); 
    int i = 0, j = 0, k = 0; 

    while (i < nL && j < nR) { 
     if (L[i] <= R[j]) { 
      A[k] = L[i]; 
      i++; 
     } 
     else { 
      A[k] = R[j]; 
      j++; 
     } 
     k++; 
    } 

    while (i < nL) { 
     A[k] = L[i]; 
     i++; 
     k++; 
    } 

    while (j < nR) { 
     A[k] = R[j]; 
     j++; 
     k++; 
    } 
} 


void MergeSort(int A[]) { 
    int n1 = lungime(A); 
    if (n1 < 2) return; 
    else 
    { 
     int mid = (int)n1/2; 
     int L[mid]; 
     int R[n - mid]; 

     for (int i = 0; i < mid; i++) 
      L[i] = A[i]; 
     for (int i = mid; i < n; i++) 
      R[i - mid] = A[i]; 
     MergeSort(L); 
     MergeSort(R); 
     Merge(L, R, A); 
    } 
} 


int main() { 
    cin >> n; 
    citire(n); 
    MergeSort(A); 
    afisare(n); 
    return 0; 
} 

Answer 1

Изменения, внесенные в этот пример. A [], L [], R [] выделяются с использованием нового. A [] передается как параметр. L [] и R [] выделяются в Merge(). Размер и/или индексы передаются как параметры, а leftime() больше не используется для получения размера. Другие изменения отмечены в комментариях.

#include<iostream> 
using namespace std; 

void citire(int A[], int lungime) {  // A is parameter 
    for (int i = 0; i < lungime; i++) cin >> A[i]; 
} 

void afisare(int A[], int lungime) { // A is parameter 
    for (int i = 0; i < lungime; i++) 
     cout << A[i] << " "; 
    cout << '\n'; 
} 

// A, low, mid, end are parameters 
// L and R allocated here 
void Merge(int A[], int low, int mid, int end) { 
    int sizeL = mid-low; 
    int sizeR = end-mid; 
    int *L = new int[sizeL]; 
    int *R = new int[sizeR]; 

    for(int i = 0; i < sizeL; i++) 
     L[i] = A[low+i];    // A[low+i] 
    for(int i = 0; i < sizeR; i++) 
     R[i] = A[mid+i];    // A[mid+i] 

    int i = 0, j = 0, k = low;   // k = low 
    while (i < sizeL && j < sizeR) { 
     if (L[i] <= R[j]) { 
      A[k] = L[i]; 
      i++; 
     } 
     else { 
      A[k] = R[j]; 
      j++; 
     } 
     k++; 
    } 

    while (i < sizeL) { 
     A[k] = L[i]; 
     i++; 
     k++; 
    } 

    while (j < sizeR) { 
     A[k] = R[j]; 
     j++; 
     k++; 
    } 
    delete[] R; 
    delete[] L; 
} 

// A, low, end are parameters 
void MergeSort(int A[], int low, int end) { 
    int sizeA = end - low; 
    if(sizeA < 2) 
     return; 
    int mid = low + (sizeA/2);  // mid = low + ... 
    MergeSort(A, low, mid); 
    MergeSort(A, mid, end); 
    Merge(A, low, mid, end); 
} 

int main() { 
    int n; 
    cin >> n; 
    int *A = new int[n];    // A is allocated 
    citire(A, n);      // A, n are parameters 
    MergeSort(A, 0, n);     // A, 0, n are parameters 
    afisare(A, n);      // A, n are parameters 
    delete[] A; 
    return 0; 
} 

Answer 2

«Функция lungime длина строки и эта функция работает хорошо. Я проверил его на разных массивах». Ну, это чисто случайное; неинициализированная память может содержать нули и случайным образом предоставлять терминатор массива. Если вы хотите сохранить текущий проект, вы должны:

• инициализировать нули
• убедитесь, что нет более 999 элементов во входном потоке,
• , что ни один элемент не имеет значения ноль, поскольку нуль зарезервирован и используется как терминатор, и
• определяют L и R (в MergeSort) один элемент дольше и инициализируют последний элемент до нуля.

Если у вас нет достаточных оснований для сортировки по ролям, вы можете взглянуть на поддержку сортировки подфайлов. Класс vector в C++ предлагает именно это.