ツリーソート

ツリーソート
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合のパフォーマンス	O ( n ²) (不平衡) O ( n log n ) (平衡)
最高のパフォーマンス	O ( n log n ) [引用が必要]
平均的なパフォーマンス	O ( n log n )
最悪の場合の空間複雑度	Θ( n ) の
最適	はい、バランスが取れていれば

ツリーソートは、ソートする要素からバイナリ検索ツリーを構築し、ツリーを（順番に）トラバースして要素がソートされた順序で出てくるソートアルゴリズムです。 ^{[1]その典型的な用途は、}オンラインでの要素のソートです。つまり、挿入するたびに、それまでに見た要素のセットがソートされた順序で利用できるようになります。

ツリーソートは 1 回限りのソートとして使用できますが、どちらもピボットに基づいて要素を再帰的に分割するためクイックソートと同等であり、クイックソートはインプレースでオーバーヘッドが低いため、クイックソートに比べてツリーソートの利点はほとんどありません。自己バランスツリーを使用すると、最悪の場合の複雑さは軽減されますが、オーバーヘッドはさらに大きくなります。

効率

バイナリ検索ツリーに 1 つの項目を追加するのは、平均して $O (log n)$ プロセスです ( big O 記法)。n 個の項目を追加するのは $O (n log n)$ プロセスなので、ツリーソートは「高速ソート」プロセスになります。不均衡なバイナリツリーに項目を追加すると、最悪の場合、つまりツリーがリンクリスト(縮退ツリー) に似ている場合は、 $O (n)$ 時間かかります。これにより、このソートアルゴリズムでは最悪のケースで $O$ $($ $n$ $²)$ 時間になります。この最悪のケースは、アルゴリズムが既にソートされたセット、またはほぼソートされている、逆になっている、またはほぼ逆になっているセットで動作する場合です。ただし、予想される $O$ $($ $n$ $log$ $n$ $)$ 時間は配列をシャッフルすることで達成できますが、これは等しい項目には役立ちません。

最悪の場合の動作は、自己バランス型二分探索木を使用することで改善できます。このような木を使用すると、アルゴリズムは最悪の場合のパフォーマンスが $O (n log n)になり、$ 比較ソートの次数最適になります。ただし、木ソートアルゴリズムでは、クイックソートやヒープソートなどのインプレースアルゴリズムとは異なり、木に別のメモリを割り当てる必要があります。ほとんどの一般的なプラットフォームでは、これはヒープメモリを使用する必要があることを意味し、クイックソートやヒープソートと比較するとパフォーマンスが大幅に低下します^{[引用が必要]}。二分探索木としてスプレー木を使用する場合、結果として得られるアルゴリズム (スプレーソートと呼ばれる ) には、適応型ソートであるという追加のプロパティがあります。つまり、ほぼソートされている入力の場合、実行時間は $O (n log n)$ よりも速くなります。

例

疑似コード内の次のツリーソートアルゴリズムは、比較可能な項目のコレクションを受け入れ、項目を昇順で出力します。

 構造BinaryTree BinaryTree : LeftSubTreeオブジェクト: Node BinaryTree : RightSubTree手順Insert ( BinaryTree : searchTree , Object : item ) IF searchTree.Node IS NULL THEN SET searchTree.Node TO item ELSE IF item IS LESS THAN searchTree.Node THEN Insert ( searchTree . LeftSubTree , item ) ELSE Insert ( searchTree . RightSubTree , item )手順InOrder ( BinaryTree : searchTree ) IF searchTree.Node IS NULL THEN EXIT手順ELSE InOrder ( searchTree . LeftSubTree ) EMIT searchTree .ノードInOrder ( searchTree . RightSubTree ) PROCEDURE TreeSort (コレクション: items ) BinaryTree : searchTree FOR EACH individualItem IN items Insert ( searchTree , individualItem ) InOrder ( searchTree )

単純な関数型プログラミング形式では、アルゴリズム ( Haskell ) は次のようになります。

 データツリーa =リーフ|ノード(ツリーa ) a (ツリーa )           

 insert :: Ord a => a -> Tree a -> Tree a insert x Leaf = Node Leaf x Leaf insert x ( Node t y s ) | x <= y = Node ( insert x t ) y s | x > y = Node t y ( insert x s )           
        
      
               
                

 flatten :: Tree a -> [ a ] flatten Leaf = [] flatten ( Node t x s ) = flatten t ++ [ x ] ++ flatten s     
    
             

 ツリーソート:: Ord a => [ a ] -> [ a ]ツリーソート= flatten 。フォルダー挿入リーフ

上記の実装では、挿入アルゴリズムと検索アルゴリズムの両方に $O (n ²) の$ 最悪のシナリオがあります。

外部リンク

バイナリツリー Java アプレットとWayback Machineの説明(2016 年 11 月 29 日アーカイブ)
ツリー型のリンクリスト
C++ でのツリーソート

参考文献

^ McLuckie, Keith; Barber, Angus (1986). 「Binary Tree Sort」.マイクロコンピュータのソートルーチン. Basingstoke: Macmillan. ISBN 0-333-39587-5. OCLC 12751343.

[McLuckie_Barber_p.-1] McLuckie, Keith; Barber, Angus (1986). 「Binary Tree Sort」.マイクロコンピュータのソートルーチン. Basingstoke: Macmillan. ISBN 0-333-39587-5. OCLC 12751343.

効率

例

外部リンク

参考文献

関連するトピック

ソートアルゴリズム

配列

最悪の場合の

パフォーマンス