병합 정렬 코드가 잘못되었습니다. 알아낼 수 없습니까?

Question

프로그래밍을 처음 사용합니다. 나는 최근에 알고리즘을 연구하기 시작했다. 내 코드는 병합 정렬 절차를 수행해야하지만 올바르게 빌드되었지만 오류가 있습니다. 코드가 입력을 받아 작업을 멈 춥니 다. 인해 무한 재귀 "루프"에

#include<iostream> 
    using namespace std; 
    #define size 10 
    class mergesort { 
    public: 
     mergesort(){} 
     void merge(int a[]) { 
      int mid = 5; 
      if (size < 2) return; 
      int left[size]; int right[size]; 
      for (int i = 0; i < mid; i++) { 
       left[i] = a[i]; 
     } 
      for (int j = mid; j < size-1; j++) { 
       right[j-mid] = a[j]; 
      } 
      merge(left); 
      merge(right); 
      sort(left, right, a, mid, size-mid); 
     } 

     void sort(int left[], int right[], int a[], int L, int R) { 
      int i = 0; int j = 0; int k = 0; 
      while (i < L && j < R) { 
       if (left[i] <= right[j]) 
       { 
        a[k] = left[i]; 
        k++; i++; 
       } 
       else if (right[j] < left[i]) { 
        a[k] = right[j]; 
        k++; j++; 
       } 
      } 
      while (i < L) { 
       a[k] = left[i]; 
       k++; i++; 
      } 
      while (i < R) { 
       a[k] = right[j]; 
       k++; j++; 
      } 
     } 
    }; 
    void main() { 
     mergesort m; 
     int a[size]; 
     cout << "Enter the elements:" << endl; 
     for (int i = 0; i < size; i++) { 
      cin >> a[size]; 
     } 
     m.merge(a); 
    } 

Answer 1

스택 오버플로 오류이다 그것은 이러한 오류를 나타낸다.

merge()에는 두 개의 매개 변수가 더 필요합니다. 이 예제에서는 _alloca()를 사용하여 스택에서 할당 했으므로 여유 공간이 필요하지 않습니다. 이것은 스택을 오버플로하지 않을만큼 작은 배열에서만 작동합니다. 다른 방법은 malloc()과 free()를 사용하는 것입니다. 제 배열 동일한에게의 한번 할당을 수행하기 위해 한 번에 헬퍼 기능을 사용 -

가

 while (j < R) {    // use j here 
      a[k] = right[j]; 
      k++; j++; 
     } 

대체 방법 :

void merge(int a[], int lo, int hi) // hi is end == last + 1 
    { 
     if((hi - lo) < 2) 
      return; 
     int mid = (lo+hi)/2; 
     int *left = _alloca((mid - lo)*sizeof(int)); // alloc from stack 
     int *right = _alloca((hi - mid)*sizeof(int)); // alloc from stack 
     for (int i = lo; i < mid; i++) 
      left[i-lo] = a[i]; 
     for (int i = mid; i < hi; i++) 
      right[i-mid] = a[i]; 
     merge(left, lo, mid); 
     merge(right, mid, hi); 
     sort(left, right, a, mid-lo, hi-mid); 
     } 
    } 

분류 마지막 동안()는 I 대신 J를 사용해야 크기를 []로, 아마도 b []를 호출하고, 분할 및 병합을 수행 할 때 []와 같은 b []에 대해 동일한 색인을 사용합니다. b []는 merge() 및 sort()에 매개 변수로 전달되며 left [] 및 right [] 대신 사용됩니다.

이름이 혼란스럽고 merge()는 실제로 "정렬"이며 sort()는 실제로 "병합"입니다.