분리법과 귀속 프로그래밍 절차

분리법은 매우 강력한 알고리즘 설계 방법의 하나다.기본 사상은 원문제를 몇 개의 규모가 작지만 원문제와 유사한 자문제로 분해하고 이 자문제들을 귀속적으로 구해한 다음에 이 자문제들의 해를 합쳐서 원문제의 해를 세우는 것이다.
분산 정책에서 문제를 하나씩 반복적으로 풀고 각 계층 반복에 다음 세 단계를 적용합니다.
(1)분해(Divide): 원문제를 일부 자문제로 분해하고 자문제의 형식은 원문제와 마찬가지로 규모만 작다.
(2) 해결(Conquer): 하위 문제를 차례로 해결한다.만약 하위 문제의 규모가 충분하게 작다면, 귀속을 멈추고 직접 해답을 구한다.
(3) 합병(Combine): 하위 문제의 해를 원 문제의 해로 조합한다.
 
분치 사상은 코드에 나타나는데 왕왕 귀속되는 형식이다.실제로 인코딩할 때는 다음 절차를 따를 수 있습니다.
(1) 함수 원형을 정성껏 설계하는데 입참, 출참과 반환값 등을 포함한다.
(2) (1)의 함수를 호출하여 각 하위 문제를 처리하고 하위 문제가 이미 해결되었다고 가정한다.
(3) 하위 문제 합병의 구체적인 세부 사항을 처리한다.
(4) 기본적인 상황을 처리한다.
(5) (4)의 코드를 함수체 앞으로 옮겨 코드 구조를 정리한다.
 
예1: 역귀판 삽입 정렬
A[1..n]를 정렬하기 위해서 우리는 차례로 A[1..n-1]를 정렬한 다음에 A[n]를 정렬된 그룹 A[1..n-1]에 삽입한다.
1단계: 설계 함수 원형

void my_insertion_sort(int a[], int left, int right) // a[left...right] ,left right ， 0 .
{
}

2단계: 함수를 호출하여 하위 문제를 해결한다

void my_insertion_sort(int a[], int left, int right) // a[left, ...right] ，left,  right ， 0 。
{
    my_insertion_sort(a, left, right - 1); // a[left .. right-1] 
    
    // a[left .. right-1] ， a[right] a[left .. right-1] 。
}

3단계: 하위 문제 병합
다음에 작성할 코드는 a[right]를 a[left..right-1]의 적당한 위치에 삽입하는 것입니다. 다음과 같습니다.

void my_insertion_sort(int a[], int left, int right) // a[left, ...right] ，left,  right ， 0 。
{
    my_insertion_sort(a, left, right - 1); // a[left .. right-1] 
    
    // a[right] a[left .. right-1] 
    int j = right - 1;
    int temp = a[right];
    while (j >= left && temp < a[j])
    {
        a[j + 1] = a[j];
        --j;
    }
    a[j + 1] = temp;
    // ，a[right] a[left .. right-1] 
}

4단계: 기본 상황 처리
함수 원형 보기 void myinsertion_sort(int a[],int left,in right); left가right와 같을 때 정렬 대기 구간은 원소로 되돌아오는 것을 발견합니다.

void my_insertion_sort(int a[], int left, int right) // a[left, ...right] ，left,  right ， 0 。
{
    my_insertion_sort(a, left, right - 1); // a[left .. right-1] // a[right] a[left .. right-1] 
    int j = right - 1;
    int temp = a[right];
    while (j >= left && temp < a[j])
    {
        a[j + 1] = a[j];
        --j;
    }
    a[j + 1] = temp;
    // ，a[right] a[left .. right-1] 

    // left == right ， 。
    if(left == right)
       return;
}

5단계: 코드 구조를 최적화하고 4단계의 코드를 앞으로 옮긴다.

void my_insertion_sort(int a[], int left, int right) // a[left, ...right] ，left,  right ， 0 。
{
    // left == right ， 。
    if(left == right)
        return;

    my_insertion_sort(a, left, right - 1); // a[left .. right-1] // a[right] a[left .. right-1] 
    int j = right - 1;
    int temp = a[right];
    while (j >= left && temp < a[j])
    {
        a[j + 1] = a[j];
        --j;
    }
    a[j + 1] = temp;
    // ，a[right] a[left .. right-1] 
}

혹은 가장 좋은 것은

void my_insertion_sort(int a[], int left, int right) // a[left, ...right] ，left,  right ， 0 。
{
    if(left < right)    // 
    {
        my_insertion_sort(a, left, right - 1); // a[left .. right-1] // a[right] a[left .. right-1] 
        int j = right - 1;
        int temp = a[right];
        while (j >= left && temp < a[j])
        {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = temp;
        // ，a[right] a[left .. right-1] 
    }
    
}

 
예2: 병합 정렬
병합 서열은 바로 분치 사상의 전형적인 예이다.
1단계: 설계 함수 프로토타입:
예를 들어 배열 a[left...right] 사이의 요소를 정렬하려면 다음과 같은 원형을 설계할 수 있습니다.

void my_merge_sort(int a[],int left,in right); // left right ， 0 。
{

}

2단계: 함수를 호출하여 하위 문제를 해결합니다.
우리는 정렬을 기다리는 구간을 두 부분으로 나누고, 이 두 부분에서 우리의 함수를 호출해서 그것을 해결할 것이다.

void my_merge_sort(int a[],int left,in right); // left right ， 0 。
{
    int mid = ( left + right ) / 2;    // ， 
    my_merge_sort(a,left,mid);      　　// 
    my_merge_sort(a,mid+1,right);　　　　// 

    // 、 ， 。
}

3단계: 하위 문제 병합
두 정렬된 그룹의 합병 문제를 처리하기 위해 함수merge(int a[], int l, int m, intr)를 설계합니다.

void my_merge_sort(int a[],int left,in right); // left right ， 0 。
{
    int mid = ( left + right ) / 2;    // ， 
    my_merge_sort(a,left,mid);      // 
    my_merge_sort(a,mid+1,right); // 

    merge(a,left,mid,right); // 
}

4단계: 기본 상황 처리
이전에 설계된 정렬 함수의 원형:void mymerge_sort(int a[],int left,in right); left가right와 같을 때, 정렬 대기 구간은 원소로 되돌아옵니다.

void my_merge_sort(int a[],int left,in right); // left right ， 0 。
{
     int mid = ( left + right ) / 2;    // ， 
    my_merge_sort(a,left,mid);      // 
    my_merge_sort(a,mid+1,right); // 

    merge(a,left,mid,right); // 

    // left == right ， 。
    if(left == right)
        return;
}

5단계: 코드 구조를 최적화하고 4단계의 코드를 앞으로 옮긴다.코드 구조는 다음과 같습니다.

void my_merge_sort(int a[],int left,in right); // left right ， 0 。
{
    // left == right ， 。
    if(left == right)
        return;

    int mid = ( left + right ) / 2;    // ， 
    my_merge_sort(a,left,mid);      // 
    my_merge_sort(a,mid+1,right); // 

    merge(a,left,mid,right); // 
  
}

혹은 가장 좋은 것은

void my_merge_sort(int a[],int left,in right); // left right ， 0 。
{
    if(left < right)
    {
        int mid = ( left + right ) / 2;    // ， 
        my_merge_sort(a,left,mid);      // 
        my_merge_sort(a,mid+1,right); // 

        merge(a,left,mid,right); // 
    }  
}