[algorithm][uuuu] Counting Sort + Radix Sort
なのでRadix Sort書いてみた。昨日のはうじひささんが先に C で書いていたので pythonで書いたんだけど、今日はCで行ってみる。説明もせずに書き下してしまったので一応説明。というか鳥頭な自分への備忘録。書かないとどうせ忘れる。
Counting Sortとは
対象を降順昇順にソートしたいとして、、、
まず図のように、ソート対象(配列A)の各要素がとりえる値、全てに対応した箱を用意する(1)。次に、ソート対象の数値をおもむろにポンポンとこの箱に仕分けしていく(2)。仕分けというか、実際には対応する箱の値をインクリメントする（ヒストグラム作ってることになる）。
それが終わったら各値の順位を決定する。順位は前の箱の数値（ヒストグラム値）に自分の数値を順に足していくと決定できる(3)。途中、空っぽの箱にまで順位がついてしまうが、この際気にしない。この「順位」はソート後の配列における各値の、最大の出現位置を表している。
順位がでたら、今度はその順位を元にしてソート対象を出力配列Bに分配する(4)。各順位は最大の位置を表しているのでソート対象の大きいほうから処理。というわけで大きいほうから配列Aを見て、値に対応する順位を得る。これが最大の出現位置なので、出力配列Bのその位置に値を書き込む。次に同じ値が出た場合、今書いた場所より一つ小さい位置になるので、順位をデクリメントする。
こんだけ。簡単。まったく「比較」演算がありません。なんと強引なソートだ。32-bitの整数をソートしようとすると箱は 4G個必要になるわけでムチャというか無駄です。その代わり、配列Aに小さい値しかなければO(n)の非常に速いアルゴリズムになる、と（メモリは食うけども）。しかも安定（同値の元に関しては元々の順序を乱さない）。
Radix Sortとは
Radix Sortはソート対象を各「桁」に分けて桁ごとにソートする。このときに下の桁からやると効率が良い。上の桁からやってしまうと、次の桁のソートを行うとき、上の桁が同じ組の中でソートを行う必要が出てしまうので常に境界を意識してソートする必要がある（上の桁の方がドミナント）---ということをcuzicさんに教わりました（ありがトー！）*1。で、このRadix Sortをさっきの Counting Sortと組み合わせると、Counting Sortで必要になる箱の数が分割した桁の分だけで済むので非常においしい、と。Counting Sortは安定なので、別の桁のソートで前の桁の順序関係が狂わない。すばらしい。
長々書いたけど、やっぱり説明下手だ。僕。
で、コード
とりあえずちゃんと動くかどうかだけテスト。オーダーやヒープ or クイックとの対決は帰ってからやろう。
#include <stdio.h> #include <stdlib.h> typedef unsigned int uint; void disp(uint* a,int n) { while(n--) { int val = *a++; printf("%14d (%08x)\n", val, val); } } #define PEEP(x) ((x &mask)>>shift) void csort(uint* a, uint* b, uint* c, int n, int r, int lv) { int shift = lv, k = 1<<r; int mask = (k-1) << shift; int i; for (i = 0; i< k; i++) c[i] = 0; // clear (1) for (i = 0; i< n; i++) c[PEEP(a[i])]++; // count (2) for (i = 1; i< k; i++) c[i] += c[i-1]; // rank (3) for (i = n-1; i>=0; i--) b[--c[PEEP(a[i])]] = a[i]; // distribute (4) } // *a : input & buffer , *b : buffer, *c : bin for count // n : num of elements, r : divided bit-width uint* radixsort(uint* a, uint* b, uint* c, int n, int r) { int i; uint* t; for (i = 0; i< sizeof(uint)*8; i+= r) { csort(a, b, c, n, r, i); t = a; a = b; b = t; //swap } return a; } main(int argc, char**argv) { int n = 20; int r = 4; int k, i; int *a, *b, *c, *result; if (argc==2) r = atoi(argv[1]); k = (1 << r); a = malloc(n * sizeof(uint)); b = malloc(n * sizeof(uint)); c = malloc(k * sizeof(uint)); for (i = 0; i< n; i++) a[i] = rand(); disp(a, n); printf(" ---- \n"); result = radixsort(a, b, c, n, r); disp(result, n); }
こういうとき、きれいにスパッと書ける人がうらやましいんだけど・・・
1804289383 (6b8b4567)
846930886 (327b23c6)
1681692777 (643c9869)
1714636915 (66334873)
1957747793 (74b0dc51)
424238335 (19495cff)
719885386 (2ae8944a)
1649760492 (625558ec)
596516649 (238e1f29)
1189641421 (46e87ccd)
1025202362 (3d1b58ba)
1350490027 (507ed7ab)
783368690 (2eb141f2)
1102520059 (41b71efb)
2044897763 (79e2a9e3)
1967513926 (7545e146)
1365180540 (515f007c)
1540383426 (5bd062c2)
304089172 (12200854)
1303455736 (4db127f8)
----
304089172 (12200854)
424238335 (19495cff)
596516649 (238e1f29)
719885386 (2ae8944a)
783368690 (2eb141f2)
846930886 (327b23c6)
1025202362 (3d1b58ba)
1102520059 (41b71efb)
1189641421 (46e87ccd)
1303455736 (4db127f8)
1350490027 (507ed7ab)
1365180540 (515f007c)
1540383426 (5bd062c2)
1649760492 (625558ec)
1681692777 (643c9869)
1714636915 (66334873)
1804289383 (6b8b4567)
1957747793 (74b0dc51)
1967513926 (7545e146)
2044897763 (79e2a9e3)
正しいみたい。
*1:ちなみにcuzicさんは手で配布物とかのソートをするといつもうまくいかないそうです。わかる気がする
