재귀 병합 정렬 C++

Question

C++에서 재귀 병합 정렬 프로그램을 작성하고 싶습니다. 문제는 기본 케이스 아이디어를 재귀 적으로 작동시키는 방법을 모르겠습니다. 누구든지 Merg Function(), Split Function() 및 MergSort() 기능의 기본 사례를 알려주십시오. 나는 너에게 감사 할 것이다.

void Merg(int A[], int s1, int e1, int s2, int e2) 
{ 
    int B[8]; 
    int i=0; 

    while (A[s1] < A[s2]) 
     B[i] = B[s1]; 
     i++; 
     s1++; 

     if (s1 == e1) 
     { 
     B[i] = A[s2]; 
     i++; 
     s2++; 
     } 

    while (A[s2] < A[s1]) 
     B[i] = B[s2]; 
     i++; 
     s2++; 

     if (s2 == e2) 
     { 
     B[i] = A[s1]; 
     i++; 
     s1++; 
     } 
} 

void Split(int A[], int s, int e) 
{ 
    int mid = (s+e)/2; 

    if (s < e && mid != 0) 
    { 
     Split(A, s, mid); 
     Split(A, mid+1, e); 
    } 
    Merg(A, s, mid, mid+1, e); 
} 

int main() 
{ 
    int A[8] = {10,4,8,12,11,2,7,5}; 

    Split(A, 0, 7); 

    return 0; 
} 

Answer 1

기본 케이스는 정렬을 보장 배열, 그래서 하늘의 배열 또는 길이의 배열 1.

병합 기능 중 하나는 정확하지 않습니다 만, 적어도 대부분 포함 올바른 아이디어. 배열 끝에 지나가는 병합을 막기 위해 추가 랩핑 루프와 몇 가지 조건이 필요합니다. split 함수는 완전히 off이고, split은 재귀 적이 지 않으며, 재귀적인 mergeSort 호출 내에서 더 이상의 분할이 발생합니다.

1. 길이 (A)가 이미 하반부 L과 상반부 H에
2. 분할 정렬 된 < 2 리턴 //
3. 병합 - 정렬 L
4. 병합 - 정렬 H
5. 가 병합 경우 분류 L과 H
6. 이 완료