1

Robert Sedgewick による C++ のアルゴリズムのマージソートについて読んでいて、次の質問があります。

static void mergeAB(ITEM[] c, int cl, ITEM[] a, int al, int ar, ITEM[] b, int bl, int br )
{ 
    int i = al, j = bl;
    for (int k = cl; k < cl+ar-al+br-bl+1; k++)
    {
        if (i > ar) { c[k] = b[j++]; continue; }
        if (j > br) { c[k] = a[i++]; continue; }
        c[k] = less(a[i], b[j]) ? a[i++] : b[j++];
    }
}

注目に値する基本的なマージの特徴は、内側のループに 2 つの入力配列の最後に到達したかどうかを判断する 2 つのテストが含まれていることです。もちろん、これら 2 つのテストは通常​​失敗するため、テストを削除できるようにセンチネル キーを使用する必要があります。つまり、他のすべてのキーの値よりも大きなキー値を持つ要素が a および aux 配列の最後に追加された場合、テストを削除できます。 c 配列の次の要素は、マージが完了するまで b (a) 配列から取得されます。

ただし、最大のキー値を知るのが容易でない場合や、スペースが便利に利用できない場合があるため、センチネルを使用するのは必ずしも簡単ではありません。

マージには、簡単な解決策があります。この方法は、次の考え方に基づいています。インプレース抽象化を実装するために配列をコピーすることを諦めた場合、2 番目の配列をコピーするときに (追加コストなしで) 単純に逆の順序で配置することで、関連するインデックスは右から左に移動します。この配置により、どの配列であっても、最大の要素が他の配列のセンチネルとして機能します。

上記のテキストに関する私の質問

  1. 「a (b) 配列が使い果たされたとき」というステートメントは何ですか? ここで「a (b)」とは何ですか?

  2. 最大のキーを決定するのは簡単ではないと著者が言及している理由と、最大のキーを決定する際にスペースがどのように関連しているか?

  3. 「私たちが配列をコピーすることに辞任していることを考えると」という著者の意味は何ですか? この文脈で辞任とは何ですか？

  4. 簡単な解決策として挙げられているアイデアを理解する上での簡単な例を要求しますか?

4

2 に答える 2

3

  1. 「a (b) 配列が使い果たされたとき」は、「a配列またはb配列が使い果たされたとき」の省略形です。

  2. インターフェイスはより大きな配列のサブ配列を扱っているため、配列の端を超えて単純に書き込むことはできません。

  3. このコードは、2 つの配列から別の 1 つの配列にデータをコピーします。このコピーは避けられないため、「配列のコピーをあきらめる」ということは、配列をコピーする必要があることは避けられないことをしぶしぶ受け入れることを意味します。

  4. トリッキー...意味を理解するには時間がかかります。

接線的に：それはおそらく私がループを書く方法ではありません. 私は使用する傾向があります：

int i = al, j = bl;
for (int k = cl; i <= ar && j <= br; k++)
{
    if (a[i] < b[j])
        c[k] = a[i++];
    else
        c[k] = b[j++];
}
while (i <= ar)
    c[k++] = a[i++];
while (j <= br)
    c[k++] = b[j++];

後続の 2 つのループのうちの 1 つは何もしません。改訂されたメイン マージ ループには、反復ごとに 3 つのテストがありますが、1 つの元のアルゴリズムでは、反復ごとに 4 つのテストがあります。正式に測定したことはありませんが、単純なマージ ループは、元の単一ループ アルゴリズムよりも高速になる可能性があります。

最初の 3 つの質問は、英語学習者に最適です。

于 2013-08-20T05:56:51.237 に答える