My Merge Sort 알고리즘에 올바른 대답이 없습니다.

Question

C++ 및 알고리즘에 익숙하지 않습니다. 필자가 작성한 병합 정렬 알고리즘에서 혼란 스럽습니다. 나는 오류가 없을 때 코드가 정답을 얻지 못하는 이유를 모른다. 코드에서 입력 한 5 개의 숫자를 정렬하고 싶습니다. 정렬 된 배열은 화면에 인쇄되지 않습니다. 내 코드에서 문제를 알고 싶다. 고마워.

#include<iostream> 
using namespace std; 
int merge(int a[], int low, int mid, int high) { 
    int h = low; int j = mid + 1; int k = low; 
    int *b = new int[high - low + 1]; 
    while ((h <= mid) && (j <= high)) { 
     if (a[h] < a[j]) 
      b[k++] = a[h++]; 
     else 
      b[k++] = a[j++]; 

    } 
    if (h > mid) { 
     for (j; j <= high;++j) 
      b[k++]=a[j]; 
    } 
    if (j > high) { 
     for (h; h <= mid; ++h) 
      b[k++] = a[h]; 
    } 
    for (int i = low; i <= high; ++i) 
     a[i] = b[i]; 
    delete []b; 
    return 0; 
} 
int MergeSort(int a[], int low, int high) { 
    if (low < high) { 
     int mid = (low + high)/2; 
     MergeSort(a, low, mid); 
     MergeSort(a, mid + 1, high); 
     merge(a, low, mid, high); 
    } 
    return 0; 
} 

int main() { 
    int const n(5); 
    int a[n]; 
    cout << "Input " << n << " numbers please:"; 
    for (int i = 0; i < n; ++i) { 
     cin >> a[i]; 
    } 
    MergeSort(a, 0, n - 1); 
    for (int i = 0; i <= n - 1; ++i) 
     cout << a[i] << " "; 
    cout << endl; 
} 

Answer 1

MergeSort 기능 - low + 1 == high 따라서 mid==low을 가정합니다.

MergeSort(a, mid, high) 다시 같은 low 및 high 전달됩니다 동안 MergeSort(a, low, mid)와

재귀 호출은 즉시 반환 - 응용 프로그램이 스택 오버플로 될 때까지

---

을 (당신이 SO에 다시 질문을 게시거야?)

merge 기능을 가정하면 low==3, mid==4, high==5이라고 가정합니다.

b[]을 3으로 할당합니다. 여태까지는 그런대로 잘됐다.

그런데 당신은 (3 인) k=low 시작하고 b[k++]의 할당을 수행 - 이미 경계에서 훨씬 더 다음 단계에서 b[0] 및 b[1]이 그대로 남아있을 것입니다 동안 b[4] 및 b[5] (서면됩니다 때).

등등

당신이 아마하고 싶은 것은합니다 (while주기의 끝에서 k++ 다음 b[k-low]) 오프셋 - low에 임시 저장에 대한 모든 할당을 수행하는 것입니다 (for (int i = low; i <= high; ++i) a[i]=b[i]; 포함).

Answer 2

작은 문제 만 발견했습니다. 이 간단한 수정을 시도하십시오.

for (int i = 0; i <= n - 1; ++i) { 
     cout << a[i] << " "; 
     cout << endl; 
    } 

코드에 for 문에 괄호가 없습니다. 이 코드는 내 컴퓨터에서이 수정 프로그램을 사용하여 작동합니다.