アルゴリズム入門講座: 計数ソートとはc++で学ぶ

2018年1月3日水曜日

計数とは単純に数を数えるという意味らしく、
その名の通り、計数ソートは数を数えるアルゴリズムです(全部そうな気がしますが)

まず、以下の数列があり、これらを昇順にソートしたいとします。

A 5 0 5 3 1 4 5 0

この数列を配列Aとします。
計数ソートでは配列Aの各々の要素がいくつあるかを別の配列(Bとする)に記録することから始めます。

A 5 0 5 3 1 4 5 0

   0 1 2 3 4 5 6
B 2 1 0 1 1 3 0
B 2 3 3 4 5 8 8

上図では、要素の数を配列のindexに見立てて代入した後
各要素の累積和を求めて更新しています。
つまり、B[x]には配列Aについてのx以下の要素数が記録されていることになります。
これを利用して、ソートされた数列を作り出していきます。

次に昇順にソートされた数列を作りだされる過程をみていきます

1.

A 5 0 5 3 1 4 5 0
B 2 3 3 4 5 8 8

   1 2 3 4 5 6 7 8
C    0

配列Aの末尾から0を取り出します。
続いて配列Bからindex0の要素数2を取り出します。
そして出力先となる配列Cのindex2に0を挿入します。
また、配列Cは便宜上index1からスタートしていることします。

配列Bから配列Cに挿入したindex0の要素数を一つ減らして1とします
挿入した要素を減らすことで、次に挿入する位置を調整しています。

2.

A 5 0 5 3 1 4 5 0
B 1 3 3 4 5 8 8

   1 2 3 4 5 6 7 8
C    0                  5

Aから末尾の位置を一つずらして、1と同じ動作を繰り返します。
Aの要素は5、Bのindex5の要素は8なので、cのindex8に5を代入し、
Bのindex5の要素数を一つ減らして7とします。

以下これを繰り返すことにより、昇順にソートすることができます。

計数ソートは各要素が0以上k以下である要素数nの数列に対しO(n + k)で動作します。動作で見る通りですね。

アルゴリズム入門講座