2

タプルの配列をすべての要素で並べ替えたいと思います (それらがトライの場合のように)。入力が (1,2,5)、(1,2,3)、(1,1,4)、(2,8,9) の場合、対応する出力は (1,1,4)、( 1,2,3)、(1,2,5)、(2,8,9)。対応するトライは次のようになります。

    root
   /   \
  1     2
 / \    | 
1   2   8
|  /\   |
4 3  5  9

タプルの各位置に検索ツリーを使用することを考えていました。明らかな単純な方法もあります (最初の位置で並べ替え、次に 2 番目の位置で並べ替えるなど)。誰かがより良い方法を見ていますか？

4

3 に答える 3

3

上記で概説したトライベースのアプローチは、タプルで最上位桁の基数ソートを行うことに非常に似ています。基本的に、最初の数字に基づいてバケットに分散し、残りの数字に基づいてバケットを小さなグループに再帰的に細分化します。トライを構築するのではなく、MSD 基数ソートを明示的に実行することを検討することをお勧めします。データがまばらな場合、トライはメモリ効率が悪い可能性がありますが、MSD 基数ソートはメモリ使用量がかなり良いためです (特にすべてを暗黙的に実装する場合)。

上記の例では、タプル内のすべての数値が 1 桁でした。この場合、最大で 10 × 10 × 10 = 1000 個の異なるタプルを使用できますが、これはそれほど大きくありません。その場合、より最適化された並べ替えの利点は、おそらくその規模ではそれほど明らかではないため、カスタム コンパレータを使用して標準の並べ替えアルゴリズムを使用することを検討することをお勧めします。一方、タプルにさらに多くのエントリがある場合は、MSD 基数ソートなどのより賢いソートに投資する価値があるかもしれません。

お役に立てれば！

于 2013-03-18T17:24:24.217 に答える
1

基数ソートからトライ、マージソートから二分木に似ています

于 2013-03-18T17:57:35.297 に答える
0

物事を単純に保ち、タプルの値をタプルのすべての要素の合計として10と見なすと、(1,2,5)が125になり、ヒープなどの単純な比較ソートでソートするのはどうですか選別

于 2013-03-18T18:13:05.220 に答える