1

質問は、16:43 から 23:34 http://youtu.be/M814OagXWTI?t=16m43sまでのビデオからのマージ ソートに関するものです。

左/右の並べ替えマージ再帰を終了した後、これらのサブ配列をマージして戻す方法がわかりません。要素が 2 つのサブ配列に分割されている一番下から始めましょう。左側のサブ配列は B として、右側のサブ配列は C として知られています。16:43 頃にマージ関数にジャンプし、配列 B と C を並べ替えます。および 3. マージ ソート関数 (以下のコード) は、基本的に B の要素と C の要素をインデックスを介して比較します。要素 0 から始めて、両方の配列の各要素を比較し、最小のものを配列 A に追加します。基本的に並べ替えられた配列になるまで、要素が由来する配列のインデックスを増やします。

基本的に上記と同じことを行い、元の再帰呼び出しを終了し、3 8 2 9 のマージに進みます。これが私の質問です。コードに矛盾があります。マージされた要素を配列 A に戻しましたが、マージ関数を呼び出して 2 8 と 2 9 をマージすると、配列 B、C、および A が渡されます。次に、配列 B と C を使用して比較を行いますが、要素は並べ替えたいのは A ですよね？それでは、間違ったものを並べ替えているだけではないでしょうか? この部分については、本当に説明が必要です。

擬似コード:

 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]
}
4

1 に答える 1

1

これは、引用されたアルゴリズムを使用した単純なソートのブローバイブローナレーションです。インデントはスタックの深さを表します。各 MergeSort または Merge 呼び出しには、時間順に番号が付けられます。A3 は、呼び出し 3 の A 配列を意味します。「==」は、「と同等」を意味します。「=」は「コンテンツがある」ことを意味します。

Top に配列 Original、内容 {3,4,2,1} があるとします。トップコール MergeSort(オリジナル)

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-04T10:46:50.600 に答える