__merge_without_buffer()C++ STL で使用されるアルゴリズムの適切な高レベルの説明はどこで入手できますか? このコードを D プログラミング言語で再実装して、いくつかの拡張機能を追加しようとしています。低レベルの詳細が多すぎてわかりにくいため、STLソースコードを読んだだけでは、アルゴリズムレベルで何をしているのか理解できないようです。また、やみくもにコードを翻訳したくはありません。なぜなら、それが機能しない場合、理由がわからず、拡張機能を追加できなくなるからです。
1 に答える
12
__merge_without_buffer()は、インプレース マージ ソートのマージ ステップとしてインプレース マージを実行しています。入力として 2 つの範囲のデータを取り[first, middle)、[middle, last)これらは既に並べ替えられていると想定されます。およびパラメーターは、2 つの入力範囲の長さに等しく、len1それぞれおよびです。len2(middle - first)(last - middle)
まず、ピボット要素を選択します。次に、データを の順序に並べ替えますA1 B1 A2 B2。ここA1で、[first, middle)はピボットより小さい要素のセット、 はピボット以上A2の要素のセット、 はピボットより小さい要素のセット、およびピボット以上の要素のセットです。データは元々 の順序になっていることに注意してください。これは、まさにそれを行うへの呼び出しです。[first, middle)B1[middle, last)B2[middle, last)A1 A2 B1 B2A2 B1B1 A2std::rotate()
これで、ピボットより小さい要素 (および) をピボット以上の要素 (A1およびB1) から分離したので、2 つの部分範囲およびを再帰的にマージできます。A2B2A1 A2B1 B2
ピボットをどのように選択しますか? 私が見ている実装では、より大きな部分範囲から要素の中央値を選択します (つまり、[first, middle)要素が よりも多い場合[middle, last)は の中央値を[first, middle)選択し、それ以外の場合は の中央値を選択します[middle, last))。部分範囲は既にソートされているため、中央値を選択するのは簡単です。このピボットの選択により、2 つのサブ範囲を再帰的にマージするときに、各サブ問題が現在の問題のサイズの 3/4 を超えないことが保証されます。これは、最悪の場合、要素の少なくとも 1/4 がピボットよりも大きいか小さいためです。 .
これの実行時間は？呼び出しには O(N) 時間がかかり、std::rotate()自分自身に対して 2 つの再帰呼び出しを行います。これは、O(N log N) の実行時間に相当します。ただし、これはマージソートの 1 ステップに過ぎないことに注意してください。マージソートでは、最初に両方の半分を再帰的にソートしてからマージすることに注意してください。したがって、mergesort の実行時間の再帰関係は次のようになります。
T(N) = 2T(N/2) + O(N log N)
これをマスター定理に当てはめると、マージソートが O(N log 2 N) 時間で実行されることがわかります!
最後に興味深い点として、比較ベースの並べ替えアルゴリズムの次の 3 つの性質について考えてみましょう。
- 所定の位置に
- 安定
- O(N log N) 時間で実行
通常、一度に取得できるのはこれらのうち 2 つだけです。クイックソートでは (1) と (3) が取得され、マージソートでは (2) と (3) が取得され、インプレース マージソートでは (1) と (2) が取得されます。カウントソートなどの非比較ベースのソートは、3 つすべてを達成できますが、これらのソートは特定のデータ型のみをソートできます。3つすべてを達成する比較ベースのソートが存在する可能性がありますが、存在する場合、私はその存在を認識しておらず、ほぼ確実にはるかに複雑です。
于 2009-01-13T05:36:49.873 に答える