0

このトピックをグーグルで検索したので、いくつかのものを見つけました：

Consider a pipeline of sorters S0 to Sm.

S0 has one input stream (the input sequence), and two output streams.
Si (i = 1 to m-1) has two input streams and two output streams. The
output streams of Si are the input streams of Si+1, for i = 0 to m-1.
Sm has two input streams and one output stream.

S0 reads the input stream, creates "sorted" sub-sequences of size one
and sends these intermittently to one of its two output streams.

Si repeatedly reads two sorted sub-sequences, one from each input
stream, merges them, and writes the double sized sorted sub-sequences
intermittently two one of its output streams.

Sm reads two sorted sub-sequences, one from each input stream, merges
these and produces the resulting output sequence.

Here is an example for a sequence of 8 numbers, where a bar | delimits
sorted sub sequences  

                  2 | 1 | 6 | 8  3 1 | 8 4  8 6 5 4 
7 2 3 1 5 6 4 8   ------------>  -------->  ------>   8 7 6 5 4 3 2 1
--------------> S0             S1         S2       S3 -------------->
                  ------------>  -------->  ------>
                  7 | 3 | 5 | 4  7 2 | 6 5  7 3 2 1

パイプライン パターンでマージ ソートの疑似コードが必要です。

4

1 に答える 1

1

これは、「ストリーム」を使用するボトムアップ マージソート(およびここと講義ノートはこちら) の変形のようです。

ボトムアップ マージ ソートはマージ ソートの非再帰的な変形であり、配列は一連のパスによってソートされます。各パス中に、配列はサイズ m (最初は m=1) のブロックに分割されます。隣接する 2 つのブロックごとに (通常のマージソートと同様に) マージされ、次のパスは m の 2 倍の値で行われます。

Pipeline Mergesort では、各ソーターは隣接するブロックを結合するときにパスを表します。ただし、従来のボトムアップ マージソートとは異なり、隣接するブロックは、両方の入力ストリームから読み取られた一致するペアです (同じストリーム/配列内で隣接するのではなく)。

いずれにせよ、最初に何かを試してみてください- SO は実際的な質問をする場所であり、タスクを投稿する場所ではありません:)

于 2012-10-03T01:28:27.303 に答える