병합 정렬 알고리즘 (병합 배열 부분)

질문 23시 34분 http://youtu.be/M814OagXWTI?t=16m43s 병합 정렬 알고리즘 (병합 배열 부분)

우리는 우리가 왼쪽 종료 한 후이 하위 어레이를 다시 병합하는 방법을 내가 혼란 스러워요에 16시 43분부터 비디오에서 병합 정렬에 관한 것입니다/오른쪽 정렬 병합 재귀. 우리의 원소가 두 개의 서브 배열로 나뉘어 질 때 맨 아래부터 시작할 수 있습니다. 왼쪽 서브 배열은 B로 알고 오른쪽 서브 배열은 C로 알려져 있습니다. 약 16:43에서 우리는 병합 함수로 뛰어 들어가서 배열 B와 C를 정렬합니다. 3. 병합 정렬 함수 (코드 숨김)는 기본적으로 인덱스를 통해 B의 요소와 C를 비교합니다. 요소 0부터 우리는 두 배열의 각 요소를 비교하고 어느 것이 든 가장 작은 배열을 배열 A에 추가합니다. 우리는 기본적으로 정렬 된 배열을 가질 때까지 요소가 제공 한 배열의 인덱스를 늘립니다. 정렬 된 배열이 끝나면 이전에 일시 중지 된 재귀 스택을 다시 크롤링하고 하위 배열의 오른쪽 분할을 계속 진행하기 위해 재귀 호출을 종료합니다. 8 3 2 9

기본적으로 우리는 위와 같은 재귀 호출을 끝내고 합병 3 8 2 9로 진행합니다. 좋아요, 제 질문입니다 : 코드에서 모순이 있습니다. 병합 된 요소를 배열 A에 다시 넣었습니다. 그러나 병합 함수를 호출하여 2 8과 2 9를 병합하면 배열 B, C 및 A가 전달됩니다. 그런 다음 배열 B와 C를 사용하여 비교를 수행하지만 요소 우리는 정렬하고 싶습니다. 그렇지 않습니까? 그렇다면 잘못된 것들을 정렬하는 것만은 아닐까요? 이 부분에 대한 설명이 필요합니다.

의사 코드 :

MergeSort(A[0...n-1]){ 
if n<=1 
    return A; 

copy A[0...n/2-1] to B[0...n/2-1] 
copy A[n/2...n-1] to C[0...n/2-1] 
MergeSort(B[0...(n/2)-1) 
MergeSort(C[0...(n/2)-1) 
Merge(B,C,A) 

Merge(B[0...p-1], C[0...q-1], A[0...p+q-1]){ 
i=0; j=0; k=0 
while(i <p and j<q) do{ 
    if B[i] <= C[j] { 
     A[k]=B[i]; 
     i=i+1; 
    } 
    else { 
    A[k]=C[j]; 
    j=j+1; 
    } 
    k=k+1 
} 

//Copy leftover element 
if i==p 
    A[k...p+q-1]=C[j...q-1] 
else 
    A[k...p+q-1]=B[i...p-1] 
}

출처

2013-08-04 user2644819

A는 형식 인수 식별자이므로 MergeSort의 다른 호출에서 다른 것을 의미합니다. –

이것은 내 질문에 답하지 않습니다. – user2644819

2와 9로 나뉘는 재귀 이후에 우리는 부분 배열 9에서 MergeSort (C [0 ... (n/2) -1)를 재귀 적으로 호출하려고하지만 재귀 호출을 종료하고 emerge MergeSort (C [0 ... (n/2) -1)를 제거하고 병합 (B, C, A) 인 다음 명령문으로 진행하십시오. 2와 9의 배열 B와 C를 배열 A에 병합 한 다음 그 재귀 호출을 끝내고 이전의 일시 중지 된 재귀 호출로 되돌아갑니다. – user2644819

이 인용 된 알고리즘을 사용하여 간단한 종류의 드릴께요 나레이션이다. 들여 쓰기는 스택 깊이를 나타냅니다. 각 MergeSort 또는 Merge 호출에는 시간 순서대로 번호가 매겨집니다. A3은 호출 3의 A 배열을 의미합니다. "=="은 "와 동등한"것을 의미합니다. "="은 "내용 있음"을 의미합니다.

Top에는 원본 Original, content {3,4,2,1}가 있다고 가정합니다. 맨 위로

MergeSort1(A1==Original={3,4,2,1}) Create B1={3,4} and C1={2,1} 
    MergeSort2(A2==B1={3,4}) Create B2={3} and C2={4} 
    MergeSort3(A3==B2={3}) Base case, no changes. 
    MergeSort4(A4==C2={4}) Base case, no changes. 
    Merge5(B5==B2={3},C5==B2={4},A5==A2==B1) Write {3,4} into A5, which is A2, which is B1. 
    MergeSort6(A6==C1={2,1}) Create B6={2} and C6={1} 
    MergeSort7(A7==B6={2}) Base case, no changes. 
    MergeSort8(A8==C6={1}) Base case, no changes. 
    Merge9(B9==B6={2},C9==C6={1},A9==A6==C1) Write {1,2} into A9, which is A6, which is C1. 
    Merge10(B10==B1={3,4},C10==C1=={1,2},A10==A1==Original) Write {1,2,3,4} into A10, which is A1, which is Original.

이 모든 높은 수준의 결과와 기존에 {3,4,2,1} 대체하는 것입니다 (원본) 머지 소트를 호출 {1,2,3,4}.

기억해야 할 핵심 사항은 각 함수 호출에는 자체 변수가있는 자체 스택 프레임이 있지만 형식 인수는 호출자 프레임의 변수 또는 매개 변수 인 실제 인수에 매핑된다는 것입니다.

출처

2013-08-04 10:46:50

병합 정렬 알고리즘 (병합 배열 부분)

답변

관련 문제