c++ - 要素が 3 つしかない 100 要素の整数配列の並べ替え

Question

100 個の数値の配列があるとします。配列内の唯一の異なる値は 1、2、および 3 です。値は配列全体でランダムに並べられます。たとえば、配列は次のように取り込まれます。

int values[100];

for (int i = 0; i < 100; i++)
    values[i] = 1 + rand() % 3;

このような配列を効率的にソートするにはどうすればよいですか?

Answer 1

最速の解決策は、まったく「ソート」しないことです。

• 配列を調べて、1、2、3 の出現回数をカウントします。これらのカウントは、うまくいけばレジスターに収まるはずです...
• 配列に正しい数の 1、2、3 を入力し、既存のものを上書きします。

最後に、完全にソートされた配列が得られます。

一般に、配列のサイズに比べて可能な値の範囲が非常に狭い場合、これは便利な O(n) ソート アルゴリズムになります。

Answer 2

オランダの国旗アルゴリズムは、これについて一般的に引用されているアルゴリズムであり、実際にはクイックソートのバリアントの 1 つである分割ステップです (1 はより小さい、2 は等しい、3 はより大きい)。そのバリアントでは、中間部分をソートする必要はありません。