アルゴリズム・テータ構造入門 行います。これが分布数え上げソートの原 理て、す。 実例をあげて説明しましよう。キーの範 囲は 0 以上 10 以下だとします。また , データ の並び 7 , 1 , 4 , 2 , 7 , 8 , 2 を整列するもの としましよう。各キーの出現する回数とそ の累計を Table 1 に示します。出現回数の累 計から , そのキーを持つデータが整列後に 配列のどの位置に置かれるかがわかります。 キー k を持っ要素の個数を a , 0 以上 k 以下 のキーを持っ要素の個数 ( TabIe 1 の累計 ) を b とすると , キー k を持っ要素は , 配列の ( b ー a) 番目から ()— 1 ) 番目に位置することにな ります。 たとえば , キー 1 の場合 ,Table 1 から a = 1 , b = 1 なのて、 , 配列の 0 番目 ( つまり先頭 ) に置かれることになります。また , キー 2 は a = 2 , b = 3 なのて、 , 配列の 1 番目と 2 番目に 置かれることになります。同様にしてキー 4 は 3 番目 , キー 7 は 4 番目と 5 番目 , キー 8 は 6 番目に置かれます。この情報を元に , 配列 の要素を移動すれば , 分布数え上げソート は完了て、す。 分布数え上げソートという名称は , キー の分布を数え上げてその情報をもとに整列 TabIe 1 キーの分布 分布数え上けソート (distribute counting so 1 : / * 整列の対象となるデータの型。 * / 2 : typedef struct { 3 : int key; / * 整列のキー。 0 から M の範囲内でなければならない。 4 : int other; / * その他の情報。 5 : } DATA; 6 : 7 : / * キーは 0 から M までの範囲の整数。 8 : #define 100 9 : 10 : / * キーの分布を数え上げるための配列。 int countCM + 1]; 12 : 13 : / * 大きさ n の配列 a を分布数え上げソートによって整列する。 14 : 結果は配列 b に得られる。 15 : void dist count_sort(DATA a[], DATA bC], int n) 16 : { 17 : int i; 18 : / * カウンタをすべて 0 にする。 19 : 20 : for (i 0 ; i く = M; i + + ) count[i] 22 : / * キーを数え上げる。 23 : for (i 24 : 0 ; i く n; i + + ) count[a[i]. key] + + ; 25 : 26 : / * 数え上げたキーの累積度数分布を求める。 27 : for (i = 0 ; i く M; i + + ) 28 : countCi + 1] + = count[i]; 29 : 30 : / * 度数分布にしたがってデータを配列 a から配列 b にコピーする。 31 : for ( i = n ー 1 ; i 〉 = 0 ・ i--) 32 : bC--countCaCi]. keyj] = a[i]; 33 : 34 : } List 2 を行う ことからきています。 ときとまったく同じて、す。また , 8 行目て、 次に , プログラム (List 2 ) を見てみましょ は , キーの最大値を表す定数 M をマクロ定 う。関数 dist count sort が分布数え上げソ 義しています。 11 行目て、定義されている配 ートを行うルーチンて、す。この関数は , 配 列 count は , キーの個数を数え上げるための 列 a の内容を昇順に整列して , その結果を配 ものて、す。 列 b に返します。パラメータ n は , 配列 a に含 15 ~ 34 行目が関数 dist count sort の本体 まれる要素の個数て、す。 て、す。まず始めに , 20 ~ 21 行目の for 文て、配 これまて、に紹介した整列ルーチンとは違 列 count のすべての要素を 0 にします。 24 ~ 2 って , 与えられた配列そのものを整列する 5 行目て、キーの個数を数え上げて , 28 ~ 29 行 のて、はなく , 整列された配列のコピーを作 目の for 文て、累計を求めています。この段階 成することに注意しましよう。今まて、に紹 て、 , 配列 count には TabIe 1 の累計の部分の 介したアルゴリズムて、は , 要素を比較交換 値が入っていることになります。 することによって , 最終的な状態に向かっ 最後に , 32 ~ 33 行目のループて , 配列 co て遷移していきました。これに対して , 分 unt の内容をもとに , 配列 a の各要素を配列 布数え上げソートて、は , キーの分布を基に b のあるべき位置にコピーします。このルー して , 要素をいっきょに最終的な位置に移 プから抜けた時点て、 , 配列 a の要素を昇順に 動するのて、 , 配列のコピーを作らずに済ま 整列したものが配列 b に得られます。 すことはて、きません。 ところて、 , この for 文て、は配列 a の末尾の要 2 ~ 5 行目て、整列の対象となるデータの型 素から先頭に向かって処理しています。な を定義していますが , これはビンソートの ぜ後ろから前へと処理するのかというと , 累計 個数 0 0 0 1 つっ ) 4 5 6 7 8 9 0 1 3 3 4 4 4 6 7 7 7 一 1 っム 0 1 0 0 2 1 0 0 対象となるデータの並びは 7 , 1 , 4 , 2 , 7 , 8 , 2 アルゴリズムとデータ構造入門 73

されています。つまり , 安定な整列が実現 種類 m がデータの個数 n に比べて極端に大き 安定な整列を実現するためて、す。その理由 されているわけて、す。もし , 32 行目の for 文 くなければ分布数え上げソートの計算量は を Fig. 2 をもとに説明しましよう。 て、 , 配列 a の先頭から末尾に向かって処理を Fig. 2 ー①は , 先ほどの例のデータの並び O ( n ) となり , m が n より極端に大きければ計 進めると , まず 2a が b [ 2 ] にコヒ。ーされて を処理していて , 累計の計算まて、が終わっ 算量は O (m) になります。 から , 2b が b [ 1 ] にコヒ。ーされることにな た状態を表したものて、す。ところて、 , デー また , 作業領域としてキーの個数を数え ります。これて、は 2a , 2b のふたつの要素の るための配列 ( 大きさ m ) と , 結果を格納する タの並びには 2 という要素がふたっ含まれて 位置関係は保存されないのて、 , 安定な整列 ための配列 ( 大きさ n) が必要になります。し いるのて、 , 前のものを 2a, 後ろのものを 2b にならないわけて、す。 と呼んて、区別することにします。つまり , たがって , 領域計算量は O ( n ) ( または O ( m ) ) 次に紹介する基数ソートて、は , 分布数え て、す。分布数え上げソートも ( ビンソートと 配列 a は次のようになっています。 同様 ) , 比較を用いた整列アルゴリズムに比 上げソートを利用していますが , 分布数え 7 , 1 , 4 , 2a, 7 , 8 , 2b また , count [ 2 ] は 3 になっています (Ta 上げソートが安定て、あるということを前提 べて高速て、すが , その代わりに大きな作業 ble 1 のキー 2 に対応する累計 ) 。 としています。 領域を必要とします。 こて、 , 2 という要素のみに着目して話を 分布数え上げソートの性質 進めていきます。 32 ~ 33 行目のループて、は , 分布数え上げソートの計算量について考 配列 a の後ろから前に向かって処理を進めて ところて、 , ビンソートも分布数え上げソ 察しましよう。データの個数を n, キーの種 いくのて、 , ます最初に 2b が処理されます。 こて、は count [ 2 ] = 3 なのて、 , Fig. 2 ー①の 類を m とします。 List 2 からわかるように ートも , キーの種類 m が多すぎてはいけない ように要素 2b は b [ 2 ] にコビーされます ( 3 このアルゴリズムは四つのループから構成 という制限があります。なぜなら , いすれ 3 行目て、 count Ca Ci]. key] がプレデクリメ のアルゴリズムて、も大きさ m の作業用配列が されています。 ントされているのて、 , b [ 3 ] て、はなく b [ 2 ] ①カウンタをクリアする ( 20 ~ 21 行目 ) 必要になるからて、す。たとえば , キーが un になることに注意 ) 。 count [ 2 ] の値は 1 た ②キーの個数を数える ( 24 ~ 25 行目 ) signed long ( 32 ビット ) だったとすると , お け減らされて count [ 2 ] = 2 となります。 ③キーの個数の累計を求める ( 28 ~ 29 行目 ) 手上げて、す。実用的な見地からすると , ④データを配列 a から配列 b へコヒ。ーする の制限はかなりきついものて、 , 利用価値が 次に , 8 , 7 は省略して , 2a に着目しま す。このとき count [ 2 ] = 2 なのて、 , 要素 2a ( 32 ~ 33 行目 ) 半減してしまいます。 は b [ 1 ] にコヒ。ーされます ( Fig. 2 ー② ) 。 このうち , 1 と 3 は m 回実行され , 2 と 4 は n キーの種類が多いときには 0 ( n ) て、整列を 結果として , 2a, 2b のふたつの要素が , 回実行されます。したがって , 全体の計算 行うことは不可能かといえば , そうて、はあ りまん。次に紹介する基数ソート ( rad ⅸ so 量は O (n 十 m) になります。ここて、 , キーの もとの位置関係を保ったまま配列 b にコヒ。ー (t) を使えば , この制約をかわすことが可能 て、す。 Fig. 3 基数ソート 基数ソートというアルゴリズムは , かな り古くから知られていて , パンチカードを 整列するのに利用されていました。 ノヾンチ カード 1 枚には文字を 80 個パンチすることが て、きます。また , カードの特定の位置の文 字を基に , 自動的にカードを振り分ける機 械があります。 この機械を使って , 数字がパンチされて いるカードを整列することがて、きます。た とえば , カードの先頭から 4 ケタの十進数が パンチされているとしましよう。つまり次 のようになっています。 基数ソート っ 4 3 っ 4 6 つ」一 4 》 8 1 一 9 1 1 1 1 3 4 6 6 7 9 62 92 1 2 十の位で整列 73 1 4 6 49 62 92 14 ーの位で整列 73 49 12 6 1 ケタ目千の位 74 C M AGAZIN E 1992 2

アルゴリズム・テータ構造入門 Fig ・ 1 ビンソート ピンソート す。 , こて、は , 整列の対象となるレコード ビンソートのプログラムを List 1 に示しま のプログラムを簡単に書くことがて、きます。 配列を使って , 実現すれば , ビンソート ます (Fig. 1 ー③ ) 。 順に並んだデータ列 1 , 2 , 4 , 7 , 8 が得られ ビンから順に中身を取り出していけば , 昇 1- ② ) 。そして , 小さい値のラベルがついた の値のラベルのついたビンに入れます ( Fig. 次に , 整列するデータ 7 , 4 , 2 , 8 , 1 をそ ます。 に対応する値を書いたラベルを貼っておき 意します。それぞれのビンには , そのビン こ , 1 ~ 10 の値に対応する 10 個のビンを用 ートを用いて整列するには , Fig. 1 ー①のよ 8 , 1 だとしましよう。このデータをビンソ 0 まて、 , そして , 整列するデータが 7 , 4 , 2 , こて、 , 整列するデータの範囲が 1 から 1 といいます。 わけて、す。このアルゴリズムをビンソート つまり , データの値によって仕分けを行う に並べられたデータを得ることがて、きます。 るビンから順番に中身を取り出せば , 昇順 をビンに入れ終えたら , 小さい値に対応す るビンに入れていきます。すべてのデータ て , データをひとつひとっその値に対応す ことを英語て、ビン (bin) といいます。そし する箱をひとつずっ用意します。この箱の まずデータが取り得るすべての値に対応 べて異なる値になっているものとします。 とを考えます。整列の対象となる整数はす の範囲内に収まっている整数を整列するこ アルゴリズムを紹介しましよう。ある一定 最初に , ビンソート ()i n sort) という整列 } DATA int other ・ int key typedef struct { は次の構造体て、定義されています。 ① 1 ~ 10 に対応する 10 個のピンを用意する 2 ②テータを対応するピンに入れる ↓ 2 47 8 ③左から順番に中身を取り出せば , 整列されたテータか得られる 1 メンバ key が整列のキーになります。ま た , key が一 1 のときはビンが空て、あること を表していると約束します。メンバ oth 師 は , キー以外の情報を保持するためのもの て、 , ここて、は取り敢え $int 型にしてありま すが , 必要に応じて適当な型に定義してく List 1 の 9 行目て、 , キーの範囲の上限を表 す定数 M をマクロ定義しています。 こて、 は , 0 から 100 まて、を使えるように M は 100 に 定義されています。 12 行目て、は , ビンを表 す配列 b ⅲを定義しています。キー k を持つ データを binCk] に入れます。 C 言語て、は配 列の添え字は 0 から始まるのて、 , bin の大きさ は M て、はなくて , M 十 1 になっていることに 注意しましよう。 15 行目の関数 bin sort がビンソートを実行 する関数て、す。この関数は , 配列 a と要素の 個数 n をパラメータとして受け取り , 結果を 配列 a に返す仕様になっています。関数 bin sort が行っている処理はごく簡単なもの て、 , 先ほど説明したアルゴリズムをそのま まコーディングしただけのものて、す。 ます始めに 20 ~ 21 行目て、 , すべてのビン を空の状態にしておきます。メンバ key が一 1 のとき , そのビンは空て、あるという約束て、 した。 次に , 配列 a に含まれるデータを , 順番に対 応するビンに入れていきます ( 24 ~ 25 行目 ) 。 実際には , 同じキーを持つデータが重複し ていないことをチェックすべきて、しよう。 また , キーが 0 以上 M 以下に収まっているこ ともチェックすべきてす。 最後に , データをビンから順番に取り出 し , 配列 a に戻して処理は終了て、す ( 28 ~ 31 行目 ) 。 ビンソートの性質 ビンソートの計算量について考察しまし よう。データの個数を n, 用意したビンの個 数を m とすると , n 個のデータをビンに振り 分けるには O (n) の手間がかかります。ま た , データをビンから ( 昇順に ) 取り出すに は , すべてのビンを順番にチェックしなけ ればならないのて、 , O (m) の手間になりま す。したがって , ビンソートの計算量はこ アルゴリズムとデータ構造入門 71

アルゴリズム・テータ構造入門 2 ケタ目 3 ケタ目 4 ケタ目 百の位 十の位 ーの位 ます , ーの位 ( 4 ケタ目 ) の文字によってカ ードを振り分けます。 4 ケタ目には 0 ~ 9 のい ずれの文字がパンチされているはすて、すか ら , 全部て、カードの山が 10 個て、きます。 れを , 0 の山 , 1 の山 , 2 の山 , ・・・ 9 の山の 順番に重ね合わせれば , ーの位の昇順にす べてのカードを整列したことになります。 この整列手順は , ビンソートを拡張して , キーの重複を許したものと等価て、す。 次に同様の手順て、 , 十の位 ( 3 ケタ目 ) につ いて整列します。さらに百の位 , 千の位の 順番て、カードを整列すれば , 最終的にすべ てのカードが , 先頭にパンチされた 4 ケタの 数の昇順に整列されます。 ちょっと考えればこの手順がうまく働く ことがわかります。すて、に一の位について 整列済みて、あるとします。このとき , 十の 位について安定な整列を行えば , 十の位が 等しい数のあいだて、は , ーの位によって決 まる位置関係が保たれるはずて、す。したが って , 十の位について整列し終えた状態て、 は , すべての数は一の位と十の位について 整列済みになります。 たとえば , 十の位が等しいふたつの数 71 と 73 が含まれているとしましよう。まず一 の位について整列すると , 71 のほうが 73 よ りも前にきます。次に , 十の位について安 定な整列を行えば , 71 のほうが 73 よりも前 にあるという位置関係が保たれます。 このように , 下のケタから順番に 1 ケタず つ安定な整列を行っていけば , 最終的にす べてのケタについて整列されることになり ます。実際に , 2 ケタの十進数を基数ソート する例を Fig. 3 に示しましよう。 このアルゴリズムは , 下位から上位に向 かって 1 ケタずっ順番に整列していくのて、 , 基数ソートと呼ばれます。パンチカードの 例て、は , キーを十進数とみなし , 十進数の 1 ケタごとに整列を行いましたが , これはパ ンチカードを処理するのに都合がよいため このようにしているだけて、 , 別の方法 て、キーを分割することも可能て、す。 基数ソートの本質は , キーをいくつかの サプキーに分割して , 下位から上位の順て、 サプキーをもとに安定な整列を行うという 点にあります。キーをどのように分割する か , 安定な整列として何を利用するかは自 由に選択することがて、きます。 たとえば , パンチカードの例て、は , 4 ケタ の十進数を 1 ケタずつに分割して合計て、 4 回 整列を行いました。これを 2 ケタずっ , 2 回 整列を行うようにすることも可能て、す。ま た , コンピュータて、処理を行うのなら , キ ーを十進数として扱うよりも , 2 進数とみな したほうが , キーの分割は簡単にて、きます。 また , 安定て、ありさえすれば , どんな整 列アルゴリズムを使ってもかまいませんが , 実際には計算量 O ( n ) のアルゴリズムを使わ なければ意味がありません。つまり , O (n) のアルゴリズムを使えば , 基数ソートの計 算量も O (n) になり , 比較によるアルゴリズ ムよりも高速になります。しかし , O(n 10 g n) のアルゴリズムを使ったとすると , 基 数ソートの計算量は O ( nlogn ) になってし まい , 比較によるアルゴリズムに比べてメ リットはありません。何回も整列処理を行 うことを考えれば , むしろ不利になってし まいます。 パンチカードて、は , その機構上ビンソー トを使うことになります。しかし , プログ ラムとして実現する場合には , 分布数え上 げソートを用いるのが普通て、す。これ以降 , 分布数え上げソートを使うこととして話を 進めていきましよう。 キーをどのように分割するかは , 分布数 え上げソートの回数とその作業領域とを考 慮して決めなければなりません。これも典 型的な時間と空間のトレードオフて、す。基 本的には , キーを細かく分割すれば , 分布 数え上げソートに必要な作業領域は減りま すが , その代わり整列を行う回数が多くな ります。 アルゴリズムとデータ構造入門 75 16 ~ 30 行目は , List 2 の関数 dist count ットずつが整列のキーになります。 トという順番に下位から上位に向かって 4 ビ key の最下位 4 ビット , 2 回目には次の 4 ビッ 4 , 8 , 12 と変化させているのて、 , 1 回目には としています。このループて、は変数 bit を 0 , (key > > bit) & MASK キーのうち 4 ビットを取り出すのに ります。 22 行目と 30 行目からわかるように を繰り返すごとに , キーの分割位置が変わ いちばん外側のループ ( 14 行目の for ループ ) なっていることに注意してください List 2 の dist count sort とは少し仕様が異 b にも整列済みのデータが入っています ) 。 には , radix sort から返った時点て、は , 配列 入ります。配列 b は作業用の配列て、す ( 実際 の対象となる配列て、 , 整列の結果は配列 a に のパラメータを受け取ります。配列 a は整列 基数ソートを行う関数 radix sort は , 三つ 使用します。 は , 4 ビットを取り出すためのマスクとして た , 3 行目て、定義されているマクロ MASK ロ定数 M は 15 に #define してあります。ま 範囲は 0 ~ 15 になります。したがって , マク ーを , 4 ビットずつに分割するのて、 , キーの 使用する作業用配列を確保しています。キ まず 2 ~ 4 行目て、 , 分布数え上げソートて、 ートを適用しています。 つに分割して , 4 回に分けて分布数え上げソ 符号なし整数 (unsigned short) を 4 ビットず ます。このプログラムて、は , 16 ビット長の 基数ソートのプログラム例を List 3 に示し 基数ソートのプログラム とになります。 含まれるビットの数だけ整列を繰り返すこ ということも可能て、す。この場合 , キーに 反対に , キーを 1 ビットずっ分割してしまう 分布数え上げソートと同じことになります。 まったく分割しなければ , 基数ソートは , 両極端な例を考えてみましよう。キーを

アルゴリズム・アータ構造入門 sort とほとんど変わりません。ただ , key の 値の参照のしかたが違うだけて、す。 最後に 33 ~ 34 行目のループて、配列 b の内容 を配列 a にコヒ。ーしなおしています。これ は , 繰り返し整列を行うために , 常に結果 が配列 a に得られるほうが話が簡単になるか らて、す。効率を上げるためには , 配列 b から 配列 a に向かって分布数え上げソートするコ ードを追加して , このループをなくすべき て、しよう。 基数ソートの性質 基数ソートの計算量について考察してみ ましよう。データの個数を n, キーを a 個に 分割するとします。キーを分割することに よって , キーの種類 m を多くても n 程度に抑 えることがて、きるのて、 , 分布数え上げソー トの 1 回当たりの計算量は O ( n ) て、済みます。 たとえば , List 3 て、は , キーの種類 m は 16 に 基数ソート (radix so List 3 10 : { 36 : } int countCM + 1] : 3 : #define MASK 0x0f #define M 1 : / * キーの分布を数え上げるための配列。 なり , これは n に比べて十分に小さいとみな すことがて、きます。 また , キーを a 個に分割すると , 分布数え 上げソートを a 回実行する必要があります。 したがって基数ソート全体の計算量は O ( an ) となります。しかし , a は n に比べると十分 に小さいのて、 , 基数ソートの計算量は O ( n ) て、済むことになります。また領域計算量も O (n) になります。 このように , 基数ソートは計算量が O (n) と非常に高速なアルゴリズムて、す。しかし , 基数ソートを適用するためには , キーのビ ットパターンを分割しても , キーの大小関 係が保存されている必要があります。たと えば , 浮動小数点数は基数ソートて、扱うこ とはて、きません。また , 文字列も , ごく短 かい場合を除いて , 基数ソートには向いて いません。 List 3 て、は , 16 ビット長のキーを 4 ビット 2 : 4 : 5 : 8 : 11 : 12 : 13 : 14 : 15 : 17 : 18 : 19 : 20 : 22 : 23 : 24 : 25 : 26 : 27 : 28 : 29 : 30 : 32 : 33 : 34 : 35 : 6 : / * 大きさ n の配列 a を基数ソートする。作業用に配列 b を使用する。 16 ビット長の値 (uns i gned short) を , 4 ビットずつ 4 回にわたって分布数え 9 : void radix sort(unsigned short aC], unsigned short bC], int n) 上げソートを適用する。 int i, bit; / * 下位から上位に向かって , 4 ビットすっ 4 回ループを実行する。 count[i + lj + = count[i]; 0 ; i く M ・ i + + ) for (i / * 数え上げたキーの累積度数分布を求める。 countC(a[i]>>bit) & MASK] + + ; 0 ; i く n ; i + + ) for (i / * キーを数え上げる。 count[i] 0 ; i ← M ; i + + ) for (i / * カウンタをすべて 0 にする。 for (bit = 0 ; bit く 16 ; bit + = 4 ) { 0 ; i く n; i + + ) for (i / * データを作業用配列 b から配列 a へコピーする。 b[--count[(a[i]> 〉 bit) & MASK]] = aCi]; for (i = n ー 1 ; i 〉 = 0 ; i- / * 度数分布にしたがってデータを配列 a から配列 b にコピーする。 aCi] = bCi]; 76 C MAGAZINE 1 2 2 すつに分割して , 分布数え上げソートを 4 回 たとえば , List 3 の例て、 , キーの上位 8 ビ 挿入ソートとの併用というアイデアもあ フ。 トずっ 4 回に分けて整列を行うようにすれば また , キーが 32 ビット長てあれば , 8 ビッ フ。 に分割して , ソートを 2 回て、済ませるほうが 実行していますが , 実際には , 8 ビットずっ ります。 よいて、しょ - よいて、しよ - するためのビット操作にかかるオーバヘッ ん。とくに , 基数ソートて、は , キーを分割 の違いはそれほど劇的なものて、はありませ 実用的な範囲内て、は , O(n) と O(nlogn) と また , 計算量のオーダーが低いとはいえ , なります。 ムは , いすれも O ( n ) の領域作業量が必要に これに対して , 今回紹介したアルゴリズ トて、は , O(Iog n ) て、済みます。 ど必要としません。たとえばクイックソー ージソートを除けば , 作業用領域をほとん 前回まて、に紹介したアルゴリズムは , マ 大きな作業領域を必要とします。 べると高速て、すが , その代償としてかなり これは , クイックソートの O (n 10g n) に比 ずれも O (n) て、整列を行うことがて、きます。 今回紹介した三つのアルゴリズムは , い まとめ 速い可能性があります。 トを 2 回に挿入ソートを 1 回のほうが処理が ソートを 4 回行うよりも , 分布数え上げソー 質があるのて、 ,List 3 のように分布数え上げ ートには整列されたデータを好むという性 点て、 , 挿入ソートを行うわけて、す。挿入ソ かなり整列された状態になります。この時 布数え上げソートを適用すると , データは ットに対して , 4 ビットすっ 2 回に分けて分 が望ましいて、しよう。 て実験した上て、アルゴリズムを選択するの ドは無視て、きません。実際のデータを使っ

れらを合計した 0 (m 十 n) になります。 用意したビンの個数 m に比べてデータの個 数 n が十分に大きいなら , ビンソートに必要 な計算量は O ( n ) とみなすことがて、きます。 たとえば , 1 ~ 1000 の範囲の整数 200 個を 整列するなら , n = 200 , m = 1000 なのて、 , 計 算量は大体 O ( n ) とみなすことがて、きます。 しかし , 1 ~ 10000 の範囲の整数 10 個を整列 する場合 , n = 10 , m = 10000 なのて、 , 計算量 は O (n) というよりも , O (m) になってしまい ます。このようなケースて、は当然のことな がら , ビンソートよりも挿入ソートなどの ほうが高速て、す。 キーの範囲が広すぎる場合には , ビンソ ートは実用的ではありません。たとえば , キーが 32 ビット長の整数て、あったとしまし 32 よう。このとき , m は 2 = 4 , 294 , 967 , 296 に 達します。現在のコンヒ。ュータて、は , まて、大きな配列は扱うことはて、きません ( 将 来的には可能になるかもしれませんが ) 。 のような場合には , 後ほど紹介する基数ソ ートを使います。 またビンソートて、は , ビンの個数は m にな ります。計算量と同様に , m に比べて n が十 分に大きいと仮定すれば , 結局要素の個数 n に比例する作業用領域が必要になります。 これを , 領域計算量が 0 ( n ) であるといいま す。領域計算量とは , アルゴリズムを実行 するのに必要な作業用領域の大きさを , デ ータの大きさの関数として表したものて、す。 トータルて、考えれば , ビンソートは , 計 算量が O ( n ) と高速な反面 , データの分量に 比例する作業用領域が必要になります。ま た , これから紹介する分布数え上げソート , 基数ソートについても , 計算量が O (n) て、済 む代わりに , 領域計算量は O ( n ) になってい ます。いずれのケースについても , 時間と 空間のトレードオフだということがて、きま す。つまり , 比較によるアルゴリズムの限 界 O (n log n) を越える代償として , より大 きな作業領域が必要となるのて、す。 ビンソートには , 次のふたつの弱点があ 72 C M AGAZIN E 1 2 2 ります ①データの値の重複が許されない ②キーの取る値はある範囲に収まる整数 でなければならない ( 実際にはかなり狭 い範囲でなければならない ) ①は , そもそもビンにひとつだけしかデ ータが入らないのが悪いわけて , 何らかの し , 連結リストを使うとかなり大じかけに トて、つなぐチェイン法に似ています。しか ケットに割り当てられたデータを連結リス て、しよう。これは , ハッシュ法て、 , 同じバ て , 同じキーを持つデータをつなげばよい 解決します。たとえば , 連結リストを用い 方法て、 , 複数のデータが入るようにすれば Fig. 2 分布数え上げソート 結リストを使わずに重複したキーを持っデ 次に紹介する分布数え上げソートは , 連 なってしまいます。 ータを扱えます。 ②については , 分布数え上げソートもビ ンソートと同様な制限を受けます。 最後に紹介する基数ソートて、は , を受けずに済みます。 分布数え上げソート この制約 しかし き何番目に当たるかが , キーの値からわか ーの出現頻度がわかれば , 昇順に並べたと ャンして , キーの出現頻度を調べます。キ があります。まず , すべてのデータをスキ え上げソート (distribution counting sort) のもとて、整列を行うアルゴリズムに , 分布数 るという仮定をしていました。同様の条件 ビンソートは , キーがある範囲内に収ま るのて、 , 配列 a 配列 b 7 0 1 1 4 2b 2 2a 3 7 4 8 5 2b 6 この情報を元に要素の並べ換えを count 〔 2 ] = 3 ①まず配列 a の要素 2b を配列 b に移す このとき , 要素 2b は b [ count [ 2 ] ー 1 ] = b [ 2 ] にコピーされる。 また , count [ 2 ] は削徐される。 count [ 2 ] = 2 このとき , 要素 2a は b 〔 count [ 2 ] ー 1 ] = b [ 1 ] にコピーされる。 ②配列 a の要素 2a を配列 b に移す 0 1 2 3 4 5 2a 2b 配列 b 6

アルゴリズム テータ構造入門 く第 16 回〉基数ソート 近藤嘉雪 今月は , 整列アルゴリズムのうち , キーの大小 比較によらないものを取り上げましよう。この ようなアルゴリズムは , キーか特別な条件を満 たす場合にしか使えませんか , その代わり , 計 算量は 0 ( n ) で済むという特徴かあります。今回 0 ・ 00 ち , ート : 分布数 = 上げ ート , 基数ソートを紹介します キーの大小比較によらない整列アルゴリ ーがある条件を満たす必要があります。っ ズムは , いくつか存在します。ただし , まり , このようなアルゴリズムは , 常に利 のようなアルゴリズムを利用するには , キ 用て、きるわけて、はありません。 ビンソート ( bin so 較によらない 整列アルゴリズム 今回は , 前回に引き続き整列アルゴリズ ムを取り上げます。これまて、に紹介した整 列アルゴリズムは , バブルソート , 選択ソ ート , 挿入ソート , クイックソート , マー ジソート , ヒープソートの 6 種類て、す。これ らのアルゴリズムは , キーの大小を比較し た結果によってレコードを整列するものて、 す。また , 以前お話したように , キーの大 小比較を利用するかぎりにおいては , 計算 量の下限は O ( nlogn ) になります。つまり , このような「キーの大小をまじめに比較する」 アルゴリズムを使うかぎり , 0 (n log n) よ り高速なアルゴリズムは存在しえないのて、 す。 しかし , どのような手段をもってしても , O (n 10g n) の壁をやぶれないかといえば , そうて、はありません。まじめにキーの大小 比較をするから O(n log n) より速くするこ とがて、きないのて、あって , 「ずる」をすれば O (n 10g n) の壁を乗り越えることがて、きま す。 Li st 1 1 : / * 整列の対象となるデータの型。 2 : typedef struct { 3 : int key; / * 整列のキー。 0 から M の範囲内でなければならない。 4 : キーが一 1 のとき , ビンは空である。 5 : int Other; / * その他の情報。 6 : } DATA; 7 : 8 : / * キーは 0 から M までの範囲の整数。 9 : #define M 100 10 : 11 : / * ビンソートに使用するビン。 12 : DATA bin[M + 1] ; 13 : 14 : / * 大きさ n の配列 a をビンソートする。 15 : void bin_sort(DATA aC], int n) 16 : { int 1 , J; 18 : / * ビンを空にする。 19 : 20 : for (i = 0 ; i く = M; i + + ) 21 : binCi]. key 22 : / * 配列 a のデータを順番にビンに振り分ける。 23 : for (i 24 : 0 ; i く n ; i + + ) 25 : binCaCi). key] = aCi]; 26 : / * データをビンから ( 昇順に ) 取り出して , 配列 a に戻す。 28 : 29 : for (i 0 ; i ← M ; i + + ) 30 : if (binCi]. key ! = aCj + + ] = binCi]; 32 : } 70 C MAGAZINE 1992 2

ー印、 O 全ての C プログラマに贈る アルゴリズム解説書の決定版 C プログラマのための 近藤嘉雪著 と = テ - タ構造 SOFTBANK BOOKS ーアルゴリズム 近藤嘉雪著定価 2 , 200 円 ( 税込 ) 「 C MAGAZIN 連載記事を大幅加筆 プログラミング上達に必要な アルコッズムとデータ構造について、 C 言譓ユる実例凾して明解に解説 / [CONTENTS] アルゴリズムとデータ構造の基本 第 1 部 アルゴリズムとは ? / 計算量 / データ構造とは ? 第 2 部 基本的なデタ構造 配列 / 連結リスト / 木構造 第 3 部 探索 探策とは ? / ハッシュ法 / ニ分探索木 / 平衡木 第 4 部 整列 整列とは ? / 単純な整列アルゴリズム / シェルソート / クイックソート / マージソート ・お近くの書店でお求め下さい 、万トバンク出版事業部

員 mo だが , 配列形式の場合にはそのような場合 にループを構成することて、コンパクトな表 現が可能となる。 一方 , 点ということて、全体をひとまとま りのデータとして捉えて , そのまま代入し たり関数に引数として値を渡したり , 関数 の値として返したりしたくなってくるが , そのような操作は配列て、は不可能て、 , 構造 体て、なければて、きない このため , データ 全体のハンドリングの容易さを考えると構 造体に軍配が上がる。 ときとして , 構造体て、取り敢えずデータ 型を定義しておき , その先頭メンバ ( この例 て、は x) のへのポインタを作り出し , それを 元に配列的にアクセスするというコーディ ングが行われているようだが , これは移植 性を考えるとあまり好ましくない というのも , コンパイラによっては構造 体には穴が存在するかもしれず , 連続的に 宀言したメンバが必ずしも配列と同様にメ モリ上に配置されるという保証はないから て、ある。このため , 構造体のあるメンバの いて三つの座標値を d 。 uble て、表すことを考 アドレスを手がかりにそのほかの要素を配 るというテクニックを使っていることに注 える。この場合単純に考えると配列と構造 列と同じ機構て、アクセスするのは , コンパ 意されたい ( List 3 ) 。 体と両方の選択肢が考えられる。 イラと環境に大幅に依存したコーディング 配歹に構造体の使い分け てある。 まず配列を用いることにすると , 次のよ うに書けるだろう。 それやこれやて、 , このケースて、のひとつ / * 配列の場合 * / の折衷案として , 配列を構造体の中に埋め 最初に述べたように , 配列と構造体は , enum{X axiS,Y axis Z axiS,N axes}; 込んて、しまうという手法がある。 こうすれ 前者は添字て、要素にアクセスし , 後者は名 typedef double point t [N axes] ; ば全体として値をやり取りすることもて、き 前て、要素 ( メンバ ) にアクセスするという差 るし , また各要素のアクセスに添字を用い そしてもうひとつの解として構造体を用 がある。あるデータ構造を表現したい場合 いる場合にはこのように書ける。 てループを利用することが可能となる。 に , 要素の型が異なっていれば構造体を採 / * 構造体の場合 * / / * 配列を構造体の中に埋め込む * / 用するしかなく , 選択の余地はない。しか typedef struct { enum{X axiS,Y axiS Z axiS,N axes}; し , たまたますべてが同じ型て、あった場合 typedef struct { はどうだろうか。そのような場合に配列を double x ; double data [N axes] ; 使うべきか構造体を使うべきかは非常に悩 double y ; } point t ; ましいところて、ある。 double z ; } point t ; たとえば , 以下のようなケースを考えて もっとも , 筆者は必ずしもこのようなコ ーディングを推奨するものて、はない。構造 みよう。 このふたつの技法の優劣を論じてみよう。 3 次元グラフィックスて、 , 空間内の点を表 座標データの場合には , x, y, z それぞれ 体を使って , いささか冗長になったとして も素直にメンバ名ごとの処理を書き下ろす す型として point t を typedef によって定義す の軸のデータに関して , まったく同一の操 ほうがいいかなと現時点て、は考えている。 るものとする。 x, y, z の三つの座標軸を用 作を施すケースが比較的多いと思われるの 汎用のマクロ定義例 List 1 : #include く stdio. h> 2 : 3 : #define swap(xp, (P) do { struct ー f00 ( char _bar[sizeof(*(xp))] ; } -t; 4 : *(struct ー f00 * ) (xp) ; 5 : *(struct ー f00 * ) (xp) = *(struct _foo*)(yp) ; 6 : *(struct ー f00 * ) (yp) -t; } while ( の ; 7 : 8 : 9 : #define writeln(x, fmt) printf()x ” 10 : int main(void) 12 : ( = 123 int X 14 : int y = 456 15 : double xd 2. 71827 ; yd = 3.14159 ; double xa[20] ニ ” He110 , world. 17 : Char yaC20] = ” Good-night baby. 18 : Char swap(&x, (Y) ; 20 : swap(&xd, &yd) ; 21 : swap(&xa, &ya) ; 22 : writeln(), Xi); 23 : writeln(), Xi); 24 : writeln(xd, % 7. 25 : writeln(yd, % 7. 26 : writeln(xa, (s) ; writeln(ya, (s) ; 28 : 29 : return 0 ; 30 : } ANSI C ー more 113

スタートアップ C 十十 実力養成講座 「 char 型の配列」というように , 要素の型 に縛られたものてす。つまり , 配列つばい インタフェイスを選ぶと , 要素の型が限定 されてしまうことになって , いまいち使い 物になりません。 「ポインタ風のインタフ = イス て、は , ポインタ風に設計してみるのはど うて、しようか。注目点をひとつ設け , 常に そこを基準にしてアクセスが行われるよう にします。 void far * 型への型変換演算子 operator void far * ( ) を考えてみましよう (Fig. 1 ) 。 現在の注目点を物理ページの 0 ページにマ ップして , そこからフレームいつばいにウ インドウが開きつばなしになるようにして おきます。フレームが半端なセグメントに 割り当てられている場合の対策に , ポイン タを返すときに正規化するようにすれば万 全て、しよう。 たとえば , HandIeEMS ems(1024 * 32 ) ; memcpy (ems, memory, 1024 * 16 ) ; / / void far* に List EMS を扱うためのクラス宣言 1 : 0 lass HandleEMS ( s tat ic uns i gned emm—seg : 3 : int emm handle; 4 : int al loc_pages; long size; 5 : 6 : public: HandleEMS(long siz),' 7 : -HandleEMS() : 8 : 10 : 11 : unsigned HandleEMS: :emm—seg 0 : / / フレームのセグメント / んハンド丿レ / / 取得されたページ数 〃サイズ List Han 引 eEMS のコンストラクタとテストラクタ 1 : Hand1eEMS: :HandIeEMS(long siz) : emm—handle(-l) (emm-seg 日 emm-exist()) { 3 : 4 : emm—seg も emm—physpage() : SiZe Siz; al loc—pages デ (size 十 (EMM—PAGE—SIZ → 1 ) ) / EMM—PAGE_SIZ; 7 : emm—handle = emm—alloc(alloc—pages) : ~ 8 : 11 : HandIeEMS: :7 日 and1eEMS() 。コ 2 : { emm—free (emm—handl e) ; 13 : ケーションの仕様に特化されたものてす。 のような感じになるてしよう。 ランダムアクセスも必要になるだろうし , emm a110C ( ) などの関数は , TempEMS Huge クラスがそうてあったように , なるべ の際に使ったものを流用します。 く既存の型に近い振る舞いをするようにし emm seg は static メンバてあり , 1 個の同 てみたいと思います。 じ変数が HandleEMS クラスのすべてのイン 大きさの限定されたメモリの塊なのて、 , スタンスて、共有されます。一度 EMS マネー ジャの存在が確認されれば , emm seg の値 配列をまねるのがよさそうに思えます。し かし , 配列というのは , 「配列」という型が が設定されるのて , 次に別のインスタンス を生成するときには , 存在チェックをする あるわけて、はありません。 まてもありません。 List HandleEMS クラスの宣言 配列風のインタフェイス 次に , 御本尊の EMS メモリにアクセスす るためのメンバ関数を設定しなくてはなり ません。換言すれば , この HandleEMS クラ スがどういうインタフェイスを持つか , と いうことてもあります。 TempEMS< は , ファイル入出力のメタ ファーを採択していましたが , あれは , シ ーケンシャルに入出力を行うというアプリ Fig. 1 operatorvoid far* ( ) HandIeEMS: :operatorvoid far*( ) 現在の注目点をマップする ; retu 「 n MK—FP(emm—seg, ページ内 オフセット ) : 1 : class HandleEMS { static unsigned emm_seg; 3 : int emm_handle; 4 : i nt al 1 oc—pages : 5 : long size; 6 : long OS ; 7 : unsigned map() : 8 : public: 9 : HandIeEMS(long siz); ¯HandIeEMS() ; 10 : operator void far*() ; 日 andIeEMS& operator() (long れ ) : / / フレームのセグメント ~ / / ハンドル / / 取得されたページ数 / / サイズ / / 注目 〃現在位置をマップする スタートアップ C 十十 127