6

すべての整数はある程度の長さの一連のビットとして表すことができるため、次の方法で整数の束を並べ替えることができるようです。

  1. 各整数をバイナリトライ（各ノードに2つの子があり、1つは0、もう1つは1）に挿入します。
  2. トライ内のすべての単語をソートされた順序でリストするための標準アルゴリズムを使用して、すべての整数をソートされた順序でリストします。

この並べ替えアルゴリズムは実際に使用されたことがありますか？

4

1 に答える 1

6

私は実際にこのアルゴリズムがこれまでに使用されたのを見たことがありません。これはおそらく、メモリのオーバーヘッドが非常に大きいためです。数値のすべてのビットが、2つのポインタと独自のビットを含むノードに吹き飛ばされます。32ビットシステムでは、これはメモリ内の64倍のブローアップであり、64ビットシステムでは、これはメモリ内の128倍のブローアップです。

ただし、このアルゴリズムは、実際に頻繁に使用される有効数字の基数ソート（バイナリクイックソートとも呼ばれます）と非常に密接に関連しています。実際、バイナリクイックソートは、このアルゴリズムのスペース効率の高い実装と考えることができます。

接続は、トライの再帰的な構造に基づいています。トライの最上位ノードについて考えると、次のようになります。

           *
          / \
         /   \
    All #s  All #s
     with    with
    MSB 0   MSB 1

トライの標準のプレオーダートラバーサルを使用してすべての数値をソートされた順序で出力する場合、アルゴリズムは最初に0で始まるすべての数値をソートされた順序で出力し、次に1で始まるすべての数値をソートされた順序で出力します。注文。（すべての数値には同じビット数が含まれているため、ルートノードが出力されることはありません。したがって、すべての数値は実際にはリーフに格納されます）。

したがって、トライを構築し、その上でプレオーダートラバーサルを実行する効果をシミュレートしたいとします。これは、MSB 0ですべての数値を印刷することから始まり、次にMSB 1ですべての数値を印刷することから始まります。したがって、数値を2つのグループに分割することから始めることができます。次に、すべての番号がMSB 1であるものを、すべての番号をMSB 0で再帰的にソートして印刷し、次にMSB1で始まるすべての番号を再帰的にソートして印刷します。この再帰的なプロセスは、最終的に数字のすべてのビットを通過するまで続きます。その時点で、各数字を個別に印刷するだけです。

上記のプロセスは、バイナリクイックソートアルゴリズムとほぼ同じで、次のように機能します。

  • 数字が残っていない場合は、何もしません。
  • 番号が1つ残っている場合は、それを印刷します。
  • さもないと：
    • 最初のビットに基づいて、数値を2つのグループに分割します。
    • 0から始まる数値を再帰的にソートして出力します。
    • 1から始まる番号を繰り返し並べ替えて印刷します。

これらのアルゴリズムにはいくつかの違いがあります。バイナリクイックソートは、すべてがソートされるまでリストを再帰的に分割することで機能します。一方、トライベースのアルゴリズムは、トライを構築してから数値を再構築します。ただし、バイナリクイックソートは、トライの構築とウォークを同時に行うアルゴリズムの最適化と考えることができます。

つまり、メモリオーバーヘッドのために、トライベースのアルゴリズムを使用したいと思う人はいないと思いますが、MSD基数ソートアルゴリズムを導出するための優れた出発点になります。

お役に立てれば！

于 2013-01-15T05:49:11.570 に答える