병합 정렬 - 분할 오류

Question

나는 1 년 넘게 파이썬에서 프로그래밍을 해왔으며 몇 가지 기본 알고리즘을 배우기 위해 C++로 돌아갔습니다. 병합 정렬로 시작했지만 세분화 오류가 발생합니다. 도움말 크게 감사하겠습니다. 나는 그것이 일어난 곳을 디버깅 한 것 같지만, 왜 그 이유를 이해할 수는 없다.

#include <iostream> 
using namespace std; 
void* merge(int array1[], int array2[], int low, int mid, int high){ 
    int i, j, k; 
    for (i = low,j = mid, k = low; i < mid, j < high; k++){ 
     if (array1[i] < array1[j]){ 
      array2[k] = array1[i]; 
      i++; 
      } 
     else{ 
      array2[k] = array1[j]; 
      j++; 
     } 
    } 
    if (i == mid){ 
     for (; j < high; j++, k++){ 
      array2[k] = array1[j]; 
      } 
    } 
else{ 
    for (; i < mid; i++, k++){ 
     array2[k] = array1[i]; 
    } 
} 
void* merge_sort(int array1[], int copy[], int low, int high){ 
    int mid; 
    int range = high - low; 
    if (range == 1) 
     copy[low] = array1[low]; 
    else{ 
     mid = low + range/2; 
     merge_sort(array1, copy, low, mid); 
     // Segmentation error seems to be here. 
     merge_sort(array1, copy, mid, high); 
    } 
    merge(array1, copy, low, mid, high); 
} 

int main() 
{ 
    int n, temp; 
    cout << "How many numbers do you want to enter?" << endl; 
    cin >> n; 
    int numarray[n]; 
    for (int i = 0; i < n; i++){ 
     cin >> numarray[i]; 
    } 
    int dumarray[n]; // Used for filling elements from merge sort 
    merge_sort(numarray, dumarray, 0, n); 
    cout << "Merge Sort" << endl; 
    for (int i = 0; i < n; i++){ 
     cout << dumarray[i] << endl; 
    } 
    return 0; 
} 

는 편집 :

#include <iostream> 
using namespace std; 

void merge_sort(int [], int [], int, int); 

void merge(int array1[], int array2[], int low, int mid, int high){ 
    int i, j, k; 
    for (i = low,j = mid, k = low; i < mid, j < high; k++){ 
     if (array1[i] < array1[j]){ 
      array2[k] = array1[i]; 
      i++; 
      } 
     else{ 
      array2[k] = array1[j]; 
      j++; 
     } 
    } 
    if (i == mid){ 
     for (; j < high; j++, k++){ 
      array2[k] = array1[j]; 
      } 
    } 
    else{ 
     for (; i < mid; i++, k++){ 
      array2[k] = array1[i]; 
      } 
    } 
} 

void merge_sort(int array1[], int copy[], int low, int high){ 
    int mid; 
    int range = high - low; 
    mid = low + range/2; 
    if (range == 1) 
     copy[low] = array1[low]; 
    else{ 
     mid = low + range/2; 
     merge_sort(array1, copy, low, mid); 
     merge_sort(array1, copy, mid, high); 
    merge(array1, copy, low, mid, high); 
    } 
} 
int main(){ 
    int n, temp; 
cout << "How many numbers do you want to enter?" << endl; 
cin >> n; 
int numarray[n]; 
for (int i = 0; i < n; i++){ 
    cin >> numarray[i]; 
} 
    int dumarray[n]; 
    merge_sort(numarray, dumarray ,0, n); 
    for (int i = 0; i < n; i++){ 
     cout << dumarray[i] << endl; 
    } 

} 

Answer 1

중간 값의 계산은 잘못된 것 같다.

mid = low + (high-low)/2

편집으로 중간 계산 시도해보십시오 다른 브래킷 내부 merge(array1, copy, low, mid, high); 이동합니다.

else 
{ 
    mid = low + range/2; 
    merge_sort(array1, copy, low, mid); 
    merge_sort(array1, copy, mid, high); 
    merge(array1, copy, low, mid, high); 
} 

는 merge 기능은 많은 버그를 가지고있다. 초기 루프의 조건 검사는 i < mid, j < high이며 쉼표로 구분됩니다. 즉, j < high 만 확인하고 i에 대한 상태 확인 만 검사하는 것입니다.