1.3 정렬 - 병합: 재 귀 를 계산 하 는 방법

병합 정렬 (merge sort) 을 봅 시다.
사실 귀 합 된 주체 사상 은 매우 간단 하 다. 바로 두 배열 의 배열 을 어떤 방법 으로 함께 놓 아 그들 로 하여 금 계속 질서 있 게 하 는 것 이다.사실 병합 정렬 이 어 려 운 부분 은 재 귀 하 는 과정 이다. 물론 이 알고리즘 에서 재 귀 하 는 것 은 그리 어렵 지 않 고 이런 사상 이 가끔 나타 나 는 방식 은 매우 기묘 하 다.
CLRS 의 위조 코드 에 따라 우 리 는 그 대체적인 사고방식 을 얻 을 수 있다. 두 배열 의 끝 에 큰 수 를 놓 고 앞쪽 을 정상적으로 비교 하고 작은 배열 을 할 수 있다.어떤 배열 이 이미 그 큰 숫자 에 이 르 렀 을 때, 다른 배열 의 모든 수 는 그것 보다 작 을 것 이다.연산 횟수 의 통 제 는 배열 에 숫자 를 넣 는 변수 에 맡 깁 니 다. 가장 왼쪽 에서 가장 오른쪽 끝 까지 최대 에 이 르 면 멈 춥 니 다.
그럼 병합 을 위 한 Merge 함 수 를 써 보 겠 습 니 다.

template
void Merge( T A[ ], int Left, int Center, int Right )  //A     ，  3     ， ， 
{
    n1 = Center - Left + 1;  //      
    n2 = Right - Center;
    T *L = new T[ n1 + 1 ];
    T *R = new T[ n2 + 1 ];
    for ( int n = 0; n != n1; ++n )
        L[ n ] = A [ Left + n ];
    for ( int n = 0; n != n1; ++n)
        R[ n ] = A[ Center + n + 1 ];
    L[n1] = 500000;  //         
    R[n2] = 500000;
    int i = 0, j = 0, k = Left;
    while( k <= Right)  //k           ，    k    Right-Left+1，       
        if ( L[ i ] <= R [ j ])
            A[ k++ ] = L[ i++ ];  //    ，         ，     
        else
            A[ k++ ] = R[ j++ ];
    delete[ ]L;
    delete[ ]R;
}

한 가지 정교 한 점 은 바로 A[ k++ ] = L[ i++ ]; 입 니 다. 우 리 는 먼저 값 을 부여 한 다음 에 스스로 더 해 야 합 니 다. 이렇게 쓰 면 한 마디 로 간결 합 니 다.C + + primer 5e 에 서 는 필요 하지 않 을 때 사전 추가 / 자체 감 소 를 사용 하 라 고 말 한 것 을 기억 합 니 다. i + 와 같은 백 엔 드 형식 은 실제 적 으로 추가 한 후에 원래 값 으로 돌아 가 는 것 이기 때문에 불필요 한 변 수 를 저장 하 는 동시에 특별한 역할 을 하지 않 는 한 오 해 를 일 으 킬 수 있 습 니 다.여기 가 바로 물고 있 는 '특별한 역할' 입 니 다!담 호 강의 신 제 i+++++i 기억 나 세 요?이런 효과 가 있 지 않 으 려 면 오해 가 있 는 문법 을 쓰 지 않 는 것 이 좋다.
여기까지 말 한 김 에 c + + 의 증가 / 체감 연산 자 를 복습 하 겠 습 니 다.우 리 는 일 하 후 치 와 선행 증 가 를 구분 해 야 한다.간단 한 사전 증가 실현:

someClass& someClass::operator++()
{
    check(thisNum);  //      thisNum
    ++thisNum;
    return *this;
}

그러면 사전 설정 은 구분 하기 위해 서 우 리 는 그 에 게 인 자 를 주 었 습 니 다 (그러나 호출 되 지 않 습 니 다).

somClass someClass::opearator++(int)  //                     ，     
{
    somClass ret = *this;
    ++*this;
    return ret;
}

이 코드 의 구동 코드 는:

void MergeSort( T *A[ ], int L, int R )
{
    if ( p < r )
        int center = ( L + R ) / 2;
        MergeSort( A, L, Center );
        MergeSort( A, Center+1,R );
        Merge( A, L, Center, R );
}

그러나 이 코드 에 도 문제 가 있 습 니 다. 이른바 '보초병' 을 사용 하 는 것 입 니 다. paper 에서 무한 대 표시 일 수 있 습 니 다. 그러나 실현 과정 에서 어떻게 그것 을 가장 크게 유지 합 니까? 만약 에 고정된 유형 이 라면 int, 우 리 는 사용 할 수 있 습 니 다 INT_MAX. 그러나 범 형 은 요?어 떡 하지?그래서 우 리 는 다른 도량형 방식 을 사용 해 야 한다. 그것 이 바로 배열 의 길이 이다.이 코드 는 여러분 이 직접 쓰 는 것 을 권장 합 니 다. 왜냐하면 여러 가지 + 1, - 1 이 있 기 때문에 자신의 '논리 적 사고' 를 연습 하기에 적합 합 니 다.그럼 적어 볼 까요?우선, 우 리 는 먼저 메 인 프로그램 을 작성 합 니 다.

template
void MergeSort( T A[ ], int Left, int Right )
{
    int Length = Right - Left + 1;
    T *tmp = new T[ Length ];  //new           tmp
    if ( tmp != nullptr )
    {
        if (L < R)
        {
            int Center = ( L + R ) / 2;
            MergeSort( A, Left, Center );
            MergeSort( A, Center + 1, Right );
            Merge( A, tmp, Left, Center, Right );
        }
        delete[ ]tmp;
    }
}

그리고 우 리 는 그것 의 merge 루틴 을 썼 다.

template
void Merge( T A[], T tmp[], int Left, int Center, int Right ) 
{
    int i = Left, j = Center, k = Left;
    while ( i != Center + 1 && j != Right + 1 )  //      0，     
        if ( A[ i ] <= A[ j ])
            tmp[ k++ ] = A[ i++ ];
        else
            tmp[ k++ ] = A[ j++ ];
    //      ，       
    while ( i != Center + 1 )
        tmp[ k++ ] = A[ i++ ];
    while ( j != Right + 1 )
        tmp[ k++ ] = A[ j++ ];
    for ( int i = Left; i != Right + 1; ++i )
        A[ i ] = tmp[ i ];
}

이 프로그램 은 사실 이해 하기 쉽다. 그 과정 은 2 단 으로 나 뉜 다. 1) 두 배열 이 모두 비어 있 지 않 기 전에 비교 한 다음 에 tmp 에 들 어가 도록 한다.2) 한 개의 키 배열 이 모두 tmp 에 들 어간 후에 다른 나머지 부분 을 tmp 에 넣 으 면 됩 니 다. 그 두 개의 while 순환 은 사실 하나만 실행 하지만 판단 할 필요 가 없습니다. 다른 하 나 는 조건 을 만족 시 키 지 못 해서 바로 끝 납 니 다.
이제 병합 정렬 의 시간 복잡 도 를 살 펴 보 자.
병합 순 서 는 한 문 제 를 두 개의 키 문제 로 나 누 었 는데 그 중 하 나 는 N / 2 를 초과 하지 않 는 최대 정수 이 고 하 나 는 N / 2 를 초과 하 는 최소 정수 이다.이런 큰 영향 을 미 치지 않 는 문 제 는 무시 할 수 있다.그래서:

T(n)=T(n/2)+T(n/2)+Θ(n)=2T(n/2)+Θ(n)=2T(n/2)+cn

재 귀 나 무 를 그 리 려 면 (나 는 그 리 려 고 하지 않 는 다. CLRS 를 보 러 간다 ~): 나무 마다 2 개의 가지 가 있 고 각 노드 는 n / 2 의 규모 크기 를 부담 한다.이 는 하위 문제 의 층 마다 n / 2 의 규 모 를 줄 이 는 것 과 같 으 며, 나무의 높이 는 log2n 이다.각 층 의 대 가 는 cn 이기 때문에 총 대 가 는 cn * log2n + cn =Θ(nlgn)。
재 귀 나무 에 작은 문제 가 있 는데 두 개의 문제 가 다 르 면 어떻게 합 니까?쉽게 말 하면 b 작은 길 을 최 장 경로 로 합 니 다.b 가 작 다 는 것 은 이 문제 의 규모 가 크다 는 것 을 설명 한다. 그러면 그것 은 반드시 더 많은 것 을 나 누 어야 최소 상황 에 이 를 수 있 을 것 이다.
하지만 매번 재 귀 나 무 를 그 리 는 것 이 귀 찮 은 것 같 습 니 다. 재 미 있 는 방법, 주 된 방법 을 소개 하 겠 습 니 다.위의 식 을 보면 T(n)=2T(n/2)+cn 우 리 는 그것 을 다음 과 같이 요약 할 수 있다. T(n)=aT(n/b)+f(n) a 는 매번 몇 개의 키 문제 가 발생 하 는 것 을 대표 하고 1 / b 는 매번 문제 의 규모 이다.우 리 는 주 정 리 를 증명 하지 않 고 주관적 으로 만 사용 할 것 이다. 주관적 으로 그것 은 세 가지 조건 에서 사용 할 것 이다. 1. f (n) logba 라면 T (n) =Θ(nlogba)。이해 하기 쉽다. 바로 하나의 큰 것 이다. 그러면 당연히 그것 이 차지 하 는 시간 이 더 많다.2. f (n) = nlogba 라면 T (n) =Θ(nlogbalgn) 3. f (n) > nlogba 라면 T (n) =Θ(f(n));
그러나 이것 은 옳 은 표현 이 아니다. 왜냐하면 여러 가지 의미 에서 만 필요 한 것 이 아니 라 한 가지 양 이 필요 하기 때문이다.ε，ε상수 입 니 다.간단 한 판단 방법 은 나눗셈 을 하 는 것 이다. 만약 f / nlogba 업 체 가 n 보다 점점 작 을 것 이다.ε의 수 (예 를 들 어 lgn) 는 주 된 방법 조건 을 만족 시 키 지 못 하고 성실 하 게 재 귀 트 리 를 사용 하 는 것 이 좋 습 니 다 ~