問題タブ [stable-sort]

manページには何も書かれていないので、stdlibの古き良きqsort関数は安定していないと思います。これは私が話している機能です：

比較関数を変更して、比較しているアドレスも含めると、安定すると思います。あれは正しいですか？

例えば：

質問のタイトルは十分に明確だと思います。C++でstd::listをstable_sort（）することは可能ですか？または、それをstd :: vectorに変換する必要がありますか？

簡単な例を試しましたが、リンクリストにはないRandomAccessIteratorsが必要なようです。では、どうすればstd :: list（）を安定ソートできますか？

編集：私にエラーを与えるサンプルコード：

g ++では約30行のエラー（貼り付けるには長すぎます）が表示され、そのうちのいくつかはRandomAccessIterators（および_merge_sort_loopと呼ばれるもの）を参照しています。リンクリストのマージソートの実装を見たことがあり、それらはほとんど「シーケンシャル」であるため、少し奇妙です。

ドキュメントはそれを保証しません。それが文書化されている他の場所はありますか？

リストの sort メソッドは安定していることが保証されているため(Notes 9 番目のポイント:「Python 2.3 以降、sort() メソッドは安定していることが保証されています」)、sorted は機能的に類似しているため、安定している可能性があると思います。しかし、私はそう言っている決定的な情報源を見つけることができません。

目的: 主キーが両方のレコードで等しい場合、主キーと副キーに基づいて並べ替える必要があります。sorted() が安定していることが保証されている場合、2 次キーでソートしてから、1 次キーでソートして、必要な結果を得ることができます。

PS: 混乱を避けるために、「等しい要素の相対的な順序を変更しないことが保証されている場合、並べ替えは安定している」という意味で安定を使用しています。

int ID、文字列 NAME、文字列 LAST_NAME を含む構造体 ABC を定義しました。
私の手順は次のとおりです。入力ファイルから行を読み取ります。各行を名と姓に解析し、ABC 構造体に挿入します。また、構造体の ID は入力行の番号で与えられます。

次に、構造体をベクター マスターリストに push_back します。また、名と姓をキーワードとして使用して、これらを vector< vector > として定義されたハッシュテーブルにハッシュしています。あれは、

私のデータが次の場合:
Garfield Cat
Snoopy Dog
Cat Man

次に、キーワード Cash について、Garfield Cat と Cat Man を含むベクターへのハッシュを行います。もう一度 push_back を使用して構造体をハッシュテーブルに挿入します。

問題は、マスターリストで stable_sort を呼び出すと、何らかの理由でハッシュテーブルが影響を受けることです。曲の順序が異なっているために発生している可能性があると思ったので、マスターリストのコピーを作成して並べ替えてみましたが、元のマスターリストには影響しませんが、ハッシュテーブルにはまだ影響があります.

なぜこれが起こっているのでしょうか？

EDIT--投稿されたソースコード:

メインはこちら

ハッシュテーブル挿入実装のスニペットは次のとおりです。

私の入力が (aでbありc、等しいキーを区別するため) であるとします。

私の数え方の並べ替えは次のように保存されます（、、および情報を破棄しaますb!! c）

それは私に結果を与えるでしょう

では、この安定ソートはどのようになっているのでしょうか。「等しいキーを持つレコードの相対的な順序を維持する」方法がわかりません。

説明してください。

次の問題を考えてみましょう。

赤または青の2つのクラスに属する要素の配列が与えられます。すべての青い要素が最初に来るように（そしてすべての赤い要素が後に続くように）、配列の要素を再配置する必要があります。再配置は安定した方法で行う必要があります。つまり、青い要素の相対的な順序を維持する必要があります（赤い要素でも同じです）。

上記の再配置をインプレースで実行する巧妙なアルゴリズムはありますか？

もちろん、インプレースではないソリューションは簡単です。

明らかなインプレースソリューションは、安定したソートアルゴリズムをアレイに適用することです。ただし、配列で本格的な並べ替えアルゴリズムを使用することは、特に2つのクラスの要素しか扱っていないという事実を考慮すると、直感的にやり過ぎのように感じます。

どんなアイデアでも大歓迎です。

ECMAスクリプトの仕様では、配列の並べ替えに使用するアルゴリズムが指定されておらず、並べ替えが安定しているかどうかも指定されていないことを知っています。

Firefoxでこの情報が見つかりました。これは、firefoxが安定ソートを使用することを指定しています。

IE 6/7/8、Chrome、Safariについて知っている人はいますか？

Table.sortに関する Luaの公式ドキュメントを読んでいたところ、次のように書かれていることに気付きました。

「[Table.sort] アルゴリズムは安定していません。つまり、指定された順序で等しいと見なされた要素の相対位置が、並べ替えによって変更される可能性があります。」

Table.sortLua でいつ安定化するかについてのアイデアはありますか?

私はこの論文を理解しようとしています:線形時間での安定した最小スペースの分割。

主張の重要な部分は、

アルゴリズム Bは、サイズnのビット配列を O(nlog 2 n) 時間と一定の余分なスペースで安定してソートしますが、 O( _n )回しか移動しません。

ただし、この論文ではアルゴリズムについては説明されておらず、私がアクセスできない別の論文を参照しているだけです。時間の範囲内で並べ替えを行う方法をいくつか見つけることができますが、一定以上のスペースを必要とせずに O(N) 移動を保証する方法を見つけるのに苦労しています。

このアルゴリズム B は何ですか? 言い換えれば、与えられた

_{Predicate を nlog 2} n回未満の呼び出しで Predicate をソートキーとして安定B(Item* a, size_t N);してソートし、 O(N) への書き込みのみを実行する関数はありますか?

特定の順序でIDを持っています

のIDと同じ順序でクエリセットのアルバムが必要album_idsです。注文を維持するにはどうすればよいですか？またはalbum_idsのようにアルバムを取得しますか？