次の問題を考えてみましょう。
赤または青の2つのクラスに属する要素の配列が与えられます。すべての青い要素が最初に来るように（そしてすべての赤い要素が後に続くように）、配列の要素を再配置する必要があります。再配置は安定した方法で行う必要があります。つまり、青い要素の相対的な順序を維持する必要があります（赤い要素でも同じです）。
上記の再配置をインプレースで実行する巧妙なアルゴリズムはありますか？
もちろん、インプレースではないソリューションは簡単です。
明らかなインプレースソリューションは、安定したソートアルゴリズムをアレイに適用することです。ただし、配列で本格的な並べ替えアルゴリズムを使用することは、特に2つのクラスの要素しか扱っていないという事実を考慮すると、直感的にやり過ぎのように感じます。
どんなアイデアでも大歓迎です。
どうやらO（n）時間とO（1）空間でそれを行うことが可能です。Jyrki Katajinen による論文Stable minimum space partitioning in linear timeと Tomi Pasanen は、それが可能であると主張しています。
安定した 0-1 ソートの Google。
これは C++ では Stable Partitioning と呼ばれ、標準アルゴリズムstd::stable_partitionがあります。
SGI 実装には、使用可能なメモリの量に応じて適応的な動作があります。
後者のインプレース ソリューションでは、舞台裏で安定した並べ替えアルゴリズムが使用されているのではないかと思います。
O(n) アルゴリズムはわかりませんが、最悪の場合に O(n*log(n)) の複雑さを持つ単純なアルゴリズムを次に示します。多分それは役に立つでしょう。
最初からゼロを切り捨て、最後から 1 を切り捨てます。それらはすでにその場所にあります。これで、配列は次のように、1 のシーケンスの後にゼロのシーケンスが続き、その後に 1 のシーケンスが続きます。
最初の 1 のシーケンスを最初の 0 のシーケンスと交換し、3 番目の 1 のシーケンスを 3 番目の 0 のシーケンスと交換します。0110011001 になります。
シーケンスの量は約 2 倍になりました。配列がソートされるまで、上記の手順を繰り返します。
2 つの隣接シーケンスを交換するには、最初のシーケンスを逆にし、次に 2 番目のシーケンスを逆にして、両方を逆にします。