it-swarm-ja.tech

STLのlist :: sort()で使用されている並べ替えアルゴリズムはどれですか?

ランダムな整数のリストがあります。どのアルゴリズムがlist::sort()メソッドで使用されているのかと思います。例えば。次のコードで:

list<int> mylist;

// ..insert a million values

mylist.sort();

編集:参照 このより具体的な質問

36
sharkin

標準は特定のアルゴリズムを必要とせず、安定している必要があり、約N lg Nの比較を使用して並べ替えを完了する必要があるだけです。これにより、たとえば、クイックソートのマージソートまたはリンクリストバージョンが可能になります(一般的な考えに反して、クイックソートは必要ありません必要ありません配列の最も一般的な実装は)ですが、不安定です。

その条件付きで、短い答えは、最新の標準ライブラリではstd::sortは、基本的には再帰の深さを追跡するQuicksortであるイントロソート(イントロスペクティブソート)として実装され、Quicksortが通常であればHeapsort(通常は低速ですがO(n log n)の複雑さ)に切り替わります。再帰が深すぎます。ただし、イントロソートは比較的最近(1990年代後半)発明されました。古い標準ライブラリは通常、代わりにクイックソートを使用していました。

stable_sortが存在するのは、配列のようなコンテナーをソートする場合、最速のソートアルゴリズムのほとんどが不安定であるため、標準には両方のstd::sort(高速ですが、必ずしも安定しているとは限りません)およびstd::stable_sort(安定していますが、多くの場合多少遅くなります)。

ただし、どちらも通常はランダムアクセス反復子を想定しており、リンクリストのようなものでは(もしあれば)うまく機能しません。リンクリストの適切なパフォーマンスを得るために、標準にはlist::sort。ただし、リンクされたリストの場合、そのようなトレードオフは実際にはありません-安定の両方であるマージソートを実装するのは非常に簡単です(約)何よりも速い。そのため、安定するために必要なsortメンバー関数が1つだけ必要でした。

46
Jerry Coffin

それは完全に定義された実装です。規格がそれについて言っている唯一のことは、その複雑さはO(n lg n)であり、ソートはstableであることです。つまり、等しい要素の相対的な順序は、ソート後に変更されないことが保証されています。

std::listのソートメンバー関数は、通常、何らかの形式のマージソートを使用して実装されます。これは、マージソートが安定しており、リンクリストを使用している場合のマージは非常に安価です。

それが役に立てば幸い:)

14
Billy ONeal