sorting - 順序付き連結リスト

Question

順序付きリンクリストを作成したい。

リンクされたリストに項目を挿入するときに並べ替えると (つまり、以下をmethod #1参照)、それともすべての項目を挿入して後で並べ替える方が速いでしょうか?

方法 1

Rough pseudo - code:
for each node in the list
    if newNode is greater than current node
       continue;
    else
       insert the node here;

方法 2

Insert all items.
Sort the list at the end (using QuickSort)

score 0 · Accepted Answer

挿入するデータに大きく依存します。大まかに降順でノードを追加している場合は、ノードを挿入するときに並べ替える方が明らかに高速ですが、逆の場合は遅くなります。

また、完了時にソートする場合、使用するソートアルゴリズムにも依存します。

一般に、並べ替えアルゴリズムの選択に関しては、二重リンクリストを使用するとより多くのオプションがあります。

また、一部のアプリケーションでは、いつでもクエリできるようにリストを常にソートしておくことが実用的です。リストの先頭 (または末尾) に常に追加すると、何かを追加するたびに再ソートする必要があります。

ソートされた状態を維持するバイナリツリーや、ノードを追加/検索する時間がツリーのサイズに線形ではなく対数的に関連する (リンクされたリストのように) など、考慮したい他の構造もあります。

2 に答える 2