茨城大学 工学部 知能システム工学科 井上 康介 E2棟801号室 アルゴリズムとデータ構造 講義スライド 2 ソートとサーチ 再帰 茨城大学 工学部 知能システム工学科 井上 康介 E2棟801号室

第3章：ソートとサーチ 大量のデータを扱うために必要な基本的作業として，ソート (sort：整列) と サーチ (search：探索) がある． ソート とは，多数のデータ列をある規則に従って並べ替えることを言う． 昇順 (正順)：小さい順，降順 (逆順)：大きい順 内部ソート：コンピュータのメモリ上のデータを扱う 外部ソート：ハードディスクなどの，外部記憶装置に存在するデータを扱う (本講義では扱わない) この章では，基本的なソート法を学ぶ．より高速な クイック・ソート と ヒープソート は後の章で学ぶ． 要する計算量が p.119 の表 3.1 にまとめられている．

第3章：ソートとサーチ サーチ とは，大量の (n 個の) データの中から必要なデータを探し出す作業を言う． 大きく分けて，逐次探索法 と 2分探索法 がある. 逐次探索法 では, データを先頭から順番に探索する方法．運良くすぐ見つかれば調べる手間は小さいが, 最悪の場合は最後まで見つからず，n 回調べることになる．データ数が n であれば，要する計算量は O(n)． 2分探索法 は, あらかじめソートされたデータ群から探索するとき有効. データを大小2つのグループに半分に分け, 境目よりも小さいなら次は小さい方のグループを, 大きいなら次は大きい方のグループを捜す. 計算量は O(log2n) となる (オーダ評価においては，対数の底は略してもよい．cf. 底変換)．

高速なアルゴリズムほど不安定となる傾向がある 追加項目：ソートの安定性 ソートの安定性とは，ソート前のデータ順序を維持するかどうかを言う． 商品番号 価格 50 1000 40 2000 20 30 10 3000 順序 維持 元データ 安定 商品番号 価格 10 3000 40 2000 50 1000 20 30 不安定 商品番号 価格 50 1000 30 2000 20 40 10 3000 維持 せず これを価格でソートするとき… 高速なアルゴリズムほど不安定となる傾向がある

直接選択法 (選択ソート法) 最初に直感的に思いつく方法：直接選択法 全体の中で最も小さい数を探し，それを1番目の数として確定する． 2番目以降から最も小さい数を探し，それを2番目の数とする．以下同様． プログラミング アルゴリズム (上記手順をコンピュータに分からせる) 対象項 i を 0 から n-2 まで移しながら以下を繰返す 2. 対象項 i の値を最小値の初期値とする 3. i+1 から n-1 項について，以下を繰返す 4. 最小項を探し，その項番号を s とする． 5. i 項と s 項を交換する

直接選択法 (選択ソート法) ソース： p.122 i=0 80 50 56 30 51 70 j= 3 1 2 4 5 i=1 対象項 i を 0 から n-2 まで移しながら以下を繰返す 2. 対象項の値を最小値の初期値とする 3. i+1 から n-1 項について，以下を繰返す 4. 最小項を探し，その項番号を s とする． 5. i 項と s 項を交換する ソース： p.122 0 1 2 3 n-1 i=0 80 50 56 30 51 70 j= 3 1 2 4 5 i=1 30 50 56 80 51 70 min = 80 50 30 i=2 30 50 56 80 51 70 s = 0 1 3 i=3 30 50 51 80 56 70 i=4 30 50 51 56 80 70 i=5 30 50 51 56 70 80 (i == n-1 となったら終了)

直接選択法の計算量 直接選択法は2重ループで実行する． データ数が n のとき， i のループ：ソート対象左端 (0～n-2) j のループ：minとの比較対象 (i+1～n-1)  i のループ1回につき，n-i-1 回まわる． 比較回数は， すなわち，直接選択法の計算量のオーダは O(n2)．

バブル・ソート 隣接する2つの項を比較し，逆順であればその2項を入れ替えるという作業を，交換対象がなくなるまで繰り返す． データ数が n であるとき，まず n-1項 (最後) から 第0項に向けて, 隣接データの比較・交換を繰り返す．この結果，第0項に最小値が入る. これで第0項が確定するので，次の回は n-1項から第1項までで行う．これで第1項に2番目に小さい数が入る．以後, これを繰り返すと全体がソートされる． Bubble とは「泡」であり，水中を泡が上がっていくように，小さい数が左に寄せられていくことに対する比喩である．

バブル・ソート 1 2 3 4 5 i=0 56 30 56 30 50 50 30 51 80 30 51 80 30 70 j = 3 2 4 1 N-1(=5) i=1 30 56 50 56 50 51 70 80 80 70 i=2 30 50 56 51 51 56 70 80 i=3 30 50 51 56 70 80 i=4 30 50 51 56 70 80 (交換が一度も起こらなかった回で終了しても良い) ソース： p.123,124

バブル・ソートの計算量 バブル・ソートも2重ループで実行する． データ数が n のとき， i のループ：比較・交換のソート範囲左端 (0～n-2)  n-1 回まわる． j のループ：2データ比較の2データ目位置 (n-1～i+1)  i のループ1回につき，n-i-1 回まわる． 比較回数は， すなわち，直接選択法の計算量のオーダは O(n2)．

シェーカー・ソート バブル・ソートの効率を上げる改良版 バブルソートにおいて, 左端に最大値があったとすると，右側から左向きの走査だけでは i のループごとにじりじりと1つずつしか動かない．そこで, 右向き・左向きの走査を交互に行う. さらにもう一つの改善策がある． バブル・ソートでは何が何でも全体にわたって比較 しかし, 例えば左側から比較・交換を行ってきた場合，最後に交換した位置が j と j+1 であるとすれば，j+1 から先は既にソート済みである → 以降無視 45 30 37 30 45 37 45 21 21 45 56 70 80

シェーカー・ソート 21 89 57 45 30 70 left = 2 right = 2 4 5 21 57 89 45 57 89 1 2 3 4 5 21 89 57 45 30 70 left = 2  ソート対象左端 right = 2 4 5 21 57 89 45 57 89 45 30 89 30 70 89 89 70  ソート対象右端 shift = 2 3 1 2 3 ? 4  最後の交換位置 21 30 57 30 45 57 30 45 70 89 left == right となったら終了 21 30 57 45 45 57 70 89 バブル・ソートに比較して，大幅な効率化 (ただし，計算量のオーダは変わらず，O(n2)) (「シェーカー」というのは，バーでカクテルを混ぜるやつ) → 左右に繰り返し動くことの比喩 ソース： p.124, 125

ポインタとは？ C言語を学習する上では，2つの 鬼門 がある． 構造体 ポインタ プログラミングに対する興味を失ってドロップアウトする人の多くが，これら2つが意味不明であることに起因． 一方で，特にデータ構造に関する学習において，この2つは 必須事項 である． そこで，プログラミング演習 I ですでに扱った事項だが，本講義でもポインタに関する復習を行っておく．

ポインタとは？ ガイダンス時に説明したとおり，変数のデータはメモリ空間上の特定位置に書き込まれる．その位置をアドレスという． 例えば int a; という宣言をすると，メモリ空間上のあいている場所に変数 a を書き込む領域が確保される．(初期化前はでたらめなデータが入っている) 変数を格納した位置 (メモリアドレス) は，プログラムが管理している． メモリ空間 a 0x22cd64番地  1628884991

ポインタとは？ アドレスは，変数 a に対して &a で表示できる． #include <stdio.h> メモリ空間 a 0x22cd64番地  1628884991 #include <stdio.h> void main(void) { int a; printf("a=%d, &a=%x\n", a, &a); } 　　(16進数表示) a=1628884991, &a=22cd64

ポインタとは？ ポインタとは，データを格納したメモリアドレス (右の例では 0x22cd64番地) を格納する変数のことである． メモリ空間 pt a 612256ea 22cd64 1628884991 int a; int *pt; pt = &a;  int型へのポインタ変数 pt を宣言  pt に a のアドレスを代入 これにより，変数 pt は変数 a のありかを指し示す (pointする) 変数となる！

ポインタの使い方 ポインタ演算子 &a : a のアドレス *pt: pt が示す先にある変数の値 ポインタには型がある  指し示す先の変数 　の型に基づいて指定 #include <stdio.h> void main(void) { int a; int *pt; pt = &a; a = 3; printf("*pt = %d\n", *pt); } pt a 3  ポインタ pt が a をpoint  a に 3 を代入 *pt = 3 (pt = 0x22cd64)

配列とポインタ 例えば，short型 (1要素2バイト) で要素数が3の配列 b があるとする． 各要素のアドレスは「&」演算子を用いて取り出せる． &b[1]  0x22cd42 では，配列名 b とは何か？ 実は b は 配列の先頭アドレス を指し示すポインタ  b と &b[0] は同じ！ したがって， メモリ空間 0x22cd40番地 b[0] 12446 0x22cd42番地 b[1] 3545 0x22cd44番地 b[2] -7043 b+2  0x22cd44 2バイト ※ ポインタに対する加減算 　はデータサイズ単位 *b  0x22cd40 *b  12446  b[2] と *(b+2) は同じ

分かってないとこの講義にはついていけない！ 例えば教科書 p.285 の図 6.6 などをみてください． そこに描かれた3連結された長方形は，構造体です． そこに描かれた黒丸と矢印は，ポインタです． つまり… C言語の鬼門と呼ばれる「構造体」および「ポインタ」が分からないと，この授業を絶対に理解できません． 教科書やウェブサイトを参考にして，すぐ，理解しておいてください．できれば今日・明日中 (忘れるから)．分からなければ，次回講義までに 友人や井上に聞くこと！ Web上には様々な参考サイトがあり，本屋や図書館には さまざまな参考図書があります．

レコード型のソート レコード 型データ：フィールド と呼ばれる要素的データの組み合わせから構成されるデータ． C言語による実装では，構造体 を使って実現する． レコード フィールド 名前 名前 年齢 年齢 職業 職業 構造体 メンバ変数

レコード型のソート レコード型データでは，「名前」「年齢」「職業」「電話番号」など，様々なフィールドがある． このうちの特定のデータ (例えば年齢) を基準としてソートすることを考えるわけだが，その基準となるデータを キー (key) と呼ぶ． 例えば「年齢をキーとしてソートする」などという． レコード型データをソートする場合，レコード全体を交換しようとすると，複数のフィールドをまとめて交換しなければならないので，手間がかかる． そこで，各レコードデータへの ポインタの配列 を使ってソートを行う．

レコード型のソート レコードの配列 そのままデータ交換を行うと… フィールドデータそれぞれを全て交換するので手間がかかる，つまり，効率が悪い． 具体的には，一時待避のためのレコードを用意して，その名前欄，年齢欄，職業欄にそれぞれ片方のデータをコピーし，もう一方のデータを先のデータに上書きコピーした後，待避しておいたデータを元に戻す． メモリ空間 Kousuke Inoue 40 Teacher Taro Yamada 21 Student Akira Tanaka 29 Athlete Nobuyo Ooyama 70

レコード型のソート レコードの配列 交換の効率を上げるには… 各レコードのアドレスを指し示す ポインタ の配列を作り，そのポインタを交換する． 交換は，アドレスの書き換えで一発． Kousuke Inoue 40 Teacher Taro Yamada 21 Student ポインタの配列 Akira Tanaka 29 Athlete Nobuyo Ooyama 70

構造体へのポインタの使い方 ソースコードを見る準備 構造体 st があって， struct girl st; struct girl *pointer; pointer = &st; とする． 構造体 st 内の名前データ：st.name (構造体のメンバの参照方法)  printf(“%s”, st.name); とか． では，これを pointer を使って表現するとどうなるか． pointer->name これで参照できる． これは，(*pointer).name と同じ意味． 文字列＝ char型配列 pointer st.nameaaa 18 st 0x41 0x6e 0x00 'A' 'n' \0

レコード型のソート：ソースコード ソースコード (p.127) を見てみよう． 配列 a[] には，レコード群 が格納されている． 配列 p[] には，各レコードへのポインタ群 (各レコードのアドレス) が格納される (最初の for文)． このコードでは, 名前をアルファベット順に並べている．つまり，キー は名前 (文字列：文字コード (char型) の配列) である． 文字列の大小比較：strcmp() という関数で行う． int strcmp(char *s1, char *s2); 引数： s1, s2：文字列 (char型配列の先頭アドレス) 返値： s1 が s2 に較べて 1)小さい，2)等しい，3)大きい場合に，ゼロよりも 1)小さい，2)等しい，3)大きい整数を返す． ※ C言語の関数をネットで調べる：Googleで，“C言語 strcmp" など

レコード型のソート：ソースコード 最初の for文で，p[i]=&a[i]; とすることで，レコード a[i] への ポインタ が p[i] に記録される． 次の for文は 直接選択法 における対象項 i を回す． 「ここまでの最小値」min を最初の項で初期化．min には名前欄の文字列へのポインタが代入される (「文字列」とは char 型変数 (文字コード) の配列である)． j のループで最小値を検索．strcmp()により文字列の大小比較を行い，min よりさらに前に来るべき文字列を見つけたら min と s を更新．j のループを抜けると最小値の番号が s に入っている． 交換は，ポインタ変数 t をバッファ (一時避難場所) に使ってポインタ同士の入れ替えを行っている．

基本挿入法 (挿入ソート) i = 1 j = 0 i = 2 j = 1 i = 3 j = 1 2 i = 4 j = 1 2 3 既にソートされた要素の部分列に対して，その次の要素を適切な位置に挿入するという手順を繰り返す．挿入手順は，右から左へ向けた走査 (比較・交換の繰り返し) で実現． i = 1 50 80 80 50 56 30 51 71 j = 0 i = 2 50 56 80 80 56 30 51 71 j = 1 i = 3 50 30 50 30 56 56 80 30 30 80 51 71 j = 1 2 i = 4 30 50 56 51 80 51 56 51 80 71 j = 1 2 3 交換が起こら なかったら そこで次の ループへ i = 5 30 50 51 56 80 71 80 71 j = 4 3

基本挿入法の計算量 基本挿入法では，ソート済み部分列 (青下線) に次の要素 (黒三角) を挿入する手順を繰り返す． 挿入手順は「挿入データの左隣との比較・必要なら交換」を交換の必要がないデータまで繰り返す．以下の場合，比較回数は 3回． 必要とされる比較回数は，挿入対象データの位置 ( i とする) に対して，最小で 1回，最大で i 回． 最小となるのは，もとからデータが昇順の場合で，このとき毎回比較は1回ですむ．逆に最大となるのは降順のときで，毎回 i 回となる．ランダムなら平均的に (i / 2) 回． 50 56 80 30 51 71 50 30 50 56 30 56 80 30 30 80 51 71

基本挿入法の計算量 したがって，比較回数は以下のとおり： 最良の場合 (最初から昇順)： 1・(n-1) = n-1  O(n) 最悪の場合 (降順)： 1+2+3+…+(n-1) = n(n-1)/2  O(n2) ランダム列の場合 (期待値)： (1/2)+(2/2)+(3/2)+…+(n-1)/2 = n(n-1)/4  O(n2) 結論として，基本挿入法にとって都合のいい状況 (最初から昇順：この場合ソートする意味が無い) では，O(n) となるが，平均的 (ランダムなデータ列を仮定) および最悪の場合 (降順データ列) では，O(n2) である．

シェル・ソート 基本挿入法の改良バージョン 基本挿入法では，挿入するデータの大小で効率が変わる． そこで，「おおざっぱでいいから，あらかじめ小さめの値は前方に，大きめの値は後方に振り分けておくと，ソートが速くなる」ということになる． このために，元データをある 間隔 (gap) でとびとびにしたものを集めて，そのグループでソートしておく． シェル (Shell) は「殻」ではなく，発案者の名前． 10 20 30 40 50 60 60 50 10 20 30 20 30 40 50 40 20 50 20 60 60 20

シェル・ソート 元のデータを gap のある部分数列に分け，それぞれを基本挿入法でソート，終わったら gap をせばめる． 45 51 60 55 80 21 30 51 45 70 55 80 21 30 gap = 4/2 = 2 45 21 60 55 51 30 21 51 55 70 60 80 30 70 (教科書 p.131に誤植) gap = 2/2 = 1 21 45 30 21 45 51 30 51 55 55 60 60 80 70 80 70  データ数が多いととんでもない差になる (後で見る)

シェル・ソート ソースコード：p.132 gapをN/2で初期化して，while文の中でgapごとのソートが終わると gap=gap/2; として繰り返す． 最初のfor文は，特定のgapを持つ数列をずらしている． 次のfor文は，挿入対象を次々と選んでいく． 最後のfor文は，挿入対象を数列に挿入していく．gap で飛ばした処理をしている点に注意． p.133 の gapの選び方 は重要．gapの系列は互いに素になるように選ぶのが効率がよいとされているが， …121，40，13，4，1 という数列なら簡単に作れて効率も良くなる．この場合，次のgapは (前のgap)/3 で得られる．

シェル・ソートの計算量と安定性 シェル・ソートの計算量は，平均的には約 O(n1.25) であると予想されている (gap 系列に依存). しかしその導出はきわめて難しく，まだ完全な解析はなされていない． ランダムに生成した 50000 個のデータに対して特定のコンピュータで実行した実行時間の例によると，基本挿入法よりも圧倒的に速い． シェル・ソートは 不安定 である．その理由は，複数の同じ数字があったとき，それらが別の部分数列に所属してしまう可能性 (よって，追い越し の可能性) があるからである． 基本挿入法 13.11秒 シェル・ソート 0.09秒

逐次探索 (sequential search) ソートに続いて，サーチの内容に入る． サーチとは，たくさんのデータから目標とするデータを発見する作業である． 逐次探索 (または，線形探索 (linear search)) では，配列などに格納されたデータを先頭から1つずつ順に調べて，見つかればそこで探索を中止する． レコード のデータの配列については，そのうちの特定のフィールド (例えば「名前」) を キー として，与えられたキーに合致するフィールドを持つレコードを発見すればよい． 計算量は O(n)． ソースコード： p.135-136．

番兵を立てる 先程の逐次探索のコードでは，探索している視点を動かしていくループにおいて， while (i < N && strcmp(key,a[i].name)!=0) i++; としていた．つまり，「見ている番号 i が N に達したかどうかの判定」と, 「キーとデータが一致したかどうかの判定」の 2つを行っている． 一番最後のデータの後ろに更に1つ余分な要素を追加し，ここにキーと同じデータを加えておくと… i と N との大小比較をしなくても，最後の余分なデータに到達すれば探索が終了してくれるので, 余分な条件判定が不要となり，若干の高速化が望める (条件判定は多少時間がかかる仕事である)． この目的で最後に追加するデータを 番兵 (sentinel) と呼ぶ．

ソース・コード (p.137) の補足 関数 strcpy() について プロトタイプ： char *strcpy(char *s1, char *s2); ポインタ s1 で与えられるアドレスに， ポインタ s2 から先に並ぶ文字データの列をコピーする． null文字 (文字列の終端の記号．‘\0’ と表記し，数としてはゼロ) をコピーし終わったら終了する． 戻り値：s1 (コピーした文字列へのポインタ) s1 0x41「A」 0x6e「n」 s2 0x6e「n」 0x00「\0」 0x41「A」 0x6e「n」 0x6e「n」 0x00「\0」

2分探索 (binary search) 2分探索：データがソート済みで，昇順または降順に並んでいるときに，効率よく探索を行うアルゴリズム． 基本的には，数値計算において学んだ非線形方程式を解くための2分法と同じで，探索範囲を絞っていく方法． 教科書 p.141 の図を参照． 探索する対象の上限を upper，下限を low とする． 上限と下限のちょうど真ん中の位置 x において，データの値がキーと等しいなら発見．キーより大きいときは, 探索対象は lower と x-1 の間にあるので，upper=x-1 として下半分を探す．逆の場合は探索対象は x+1 と upper の間．そこで lower=x+1 として上半分を探す．

2分探索 (binary search) 終了条件 中央の位置 x に探すデータがあれば発見． 探索範囲の下限 low と上限 upper が入れ替わったら，対象データはないので終了． 教科書のミス： p.141 では探索範囲の下限・上限・中央がそれぞれ，low, upper, x となっているが，p.142 では，ソースコードを含めてこれらが low, high, mid となっている． 計算量は O(log n)．最悪でも log2 n 回の繰り返しで終了するので．平均はその定数倍．

2分探索の計算量 2分探索では，1回の処理ごとに検索対象データが半分になる．最悪の場合，検索対象データは1データまで減少し，そこで発見または不在が判明する． 1 データ 1 回目 2 回目 3 回目 h 回目 n データ

2分探索の計算量 h 回目の作業で検索対象データが1データにまで落ちたとすると， が成り立つので， ．両辺の対数を取ると， ． n データ 1 データ 1 回目 2 回目 3 回目 h 回目 n データ

2分探索の計算量 すなわち，最悪の場合の繰り返し回数が　　　　　であり，平均的にはその a 倍となるから，平均繰り返し回数は ．オーダでは定数係数を無視して，O(log n)． 1 データ 1 回目 2 回目 3 回目 h 回目 n データ

文字列の照合 (パターンマッチング) 元の文 text の中から照合するキー文字列 key を探す． ソースコード： p.148-149． strlen(char *p) は，文字列pの長さを返す関数． strncmp(char *s1, char *s2, size_t n)は，s1とs2の最初のn文字だけを比較する点を除けば，strcmp()と同じ． ただし，size_t型は，実体は unsigned int型と同じで，変数のサイズ (バイト数) を表すのに使う． 関数search()において，探す位置のポインタpを1つずつずらしながら文字列の照合を行っている. 最後まで見つからないときはNULLポインタを返す．

Boyer-Moore法 先程の，1文字ずつずらしていく方法では効率が悪い．とばせるところはとばすという方法が考えられる． text T h i s a p e n . c l p key p e n c i l p e n c i l p e n c i l p e n c i l 合致していないとき， 従来版：一つずらす Boyer-Moore法：ずらす量を決める ずらし量の基準：キーの右端位置のtext中の文字 このために，文字ごとに進める量の表を作っておく： l なら6文字，i なら1文字，c なら2文字… ※ 同じ文字が複数あるときは？

ハッシュ (hash) 探索を高速化するための技法で，幅広く使われている． 例えば住所録から人名をキーとして探索を行う場合，ありうる人名はきわめて多数． ハッシュ (hash) という技法で，探索が一気に早くなる． ある多対一写像を使って，「人名  0～999 の数」という対応関係 を作る． それぞれの個人データをサイズ 1000 の配列の中の当該位置に入れておく． 探索時は，探す名前を写像に従って 0～999 の数に変換し，配列の当該位置を見に行く． こうすれば，探索はデータ数によらず一定時間でできる． O(1)．

ハッシング (hashing) ハッシング (hashing)：キー (この場合, 人名) を限られた数値範囲 (この場合, 0～999) に写像することを言う． 写像の作り方は問題に応じてどうやってもよい． 次ページは教科書の例．ただし別にこの方法にこだわる必要はない．

ハッシング (hashing) の例 キーが英字の大文字からなる名前とし，A1, A2, …，An の n 文字からなるものとすると，この場合，あり得る名前は 26n 通り存在する．これは膨大な範囲である． これを 0～999 の限られた範囲に縮退するには，例えば という関数による写像を行う．すると，名前が 0～999の数字のいずれかに変換 (写像) される． 例えば "SUZUKI" さんの場合， hash(A1, A2, …, An)=(A1 + An/2×26 + An-1×262) % 1000 hash("SUZUKI")=(('S'-'A')+('Z'-'A')*26+ ('K'-'A')*26*26) % 1000 =(18+650+6760) % 1000 = 428 ※ 例えば 'S' は大文字の "S" の文字コード (83) のこと

ハッシュ (hash) このようなハッシュ処理によって，"SUZUKI" さんの名前が 428 という数に写像された． … ハッシュテーブル INOUE KOBAYASHI TANAKA … 610 2 425 999 キーの集合 数値集合 (0～999) 番号 キー 年齢 1 2 KIKUCHI 21 … 427 YAMADA 40 428 SUZUKI 28 999 428 SUZUKI 逐次探索：O(n) → ハッシュ：O(1)

ハッシュ (ソースコード) p.158-159． ハッシュの写像の実体は関数 int hash(char *s)．ここで文字列 s を数に変換して返値として返す． データの表は構造体の配列 struct tel dat[]． main 関数では，最初に表の中身を作っている． while (scanf("%s %s",a,b)!=EOF) という条件文により，a と b を何回もユーザ入力してもらう． ユーザが終了信号 Ctrl+Z を押すと，scanf() が EOF (end of file) という信号を返し，while文を抜ける． while文の中では，文字列 a (名前) を数 n に写像し，データ表の第 n 要素に名前と電話番号を記入している．

ハッシュ (ソースコード) rewind(stdin) という処理は，標準入力 (stdin) に残ったデータ (改行文字) を取り除く． scanf() でユーザが入力を行うとき，例えば "SUZUKI" と入れた後に, それを確定する意味で改行 (リターンキー) を入れる. この改行文字まで含めて読み込まれてしまうと面倒なことになることがある． そこで, ユーザからの入力が入る 標準入力ストリーム (stdin) に残っている文字をいったん全部消してしまう操作をする． (おそらく一般的な処理系では，この操作は必要ない.) 次の while文でも，ユーザから繰り返し入力を受ける． 名前を入れるとその名前をハッシュ処理して数に写像し，その数に対応するハッシュテーブル要素を見に行く．

問題：かち合い 名前の種類は無数にあり，それを1000程度の小さな値の範囲に写像しているので，当然 1対1 対応ではない． 異なる名前が同じ値になる場合をかち合い (collision) と呼ぶ．先程の方法では “ANZAI” も “SUGIYAMA” も 338． 一つの安直な方法は，既に 338 に ANZAI さんのデータが記録されていた場合，SUGIYAMA さんのデータは 339 番以降の空いている場所に書き込む (教科書 p.160の図)． 1000 番以降の，本来使わない領域も多少領域をキープしておけば，この方法で記録できる． データを検索する場合は，まずは 338 番を見に行き，そこに書かれたデータが SUGIYAMA さんのものではなかったら，次以降を逐次探索する． ( このせいで，結局 O(n))

問題：かち合い ただ，この方法では，ハッシュテーブルが詰まってくると，空のテーブルがなかなか見つからず，かなり遠いところまで逐次探索で探しに行くことになり，効率が悪い． このようにハッシュテーブルに直接データを格納する方法を オープンアドレス法 と呼ぶ．  ソース・コード：p.160 (ミス：empty フラグ初期化忘れ) これに対して，リスト構造 (第5章) を用いた別の方法が考えられる．これを チェイン法 と呼ぶ． チェイン法では，ハッシュテーブルに ANZAI さんのデータをそのまま格納するのではなく，ANZAI さんのデータへのポインタ (データのアドレス) を記入しておく． 探索時は，対応するハッシュテーブルに書かれたアドレスを見に行けばよい．

チェイン法によるハッシング リスト構造とは，データを格納する構造体に，「次のデータ」へのポインタを取り付けてデータ同士をつないでいく方法である． 探索時は，対応するリスト要素を逐次探索していく． ( O(n)) ハッシュテーブル ここに SUGIYAMA さんのデータを追加するには… リスト要素 リスト要素 338 ANZAI SUGIYAMA 年齢や電話番号などのデータ 999 まだ記録されていない番号にはNULLポインタ 次のデータへのポインタ (最後尾にはNULLポインタ)

第4章：再帰 解くべき問題によっては，以下の考え方が有効である： 解くべき問題を「同じ解き方で解ける，よりサイズの小さな副問題」に分解し，先に副問題を解く 例）n ! を求める． n ! = n・(n - 1) ! である  先に (n - 1) ! が求まれば，それを n 倍すればよい  n ! を求めるのと (n - 1) ! を求めるのは同じ手順 この考え方でプログラムを作るとどうなるだろうか…？  何が起こるかを脳内シミュレーションしてみる  n ! を求める関数を kaijo(n)とし，これを main() から呼び出すシナリオを考えよう

第4章：再帰 2! は 2 です． main() kaijo(2) kaijo(1) kaijo(0) 2 ! を表示したい 画面表示 待機中 2 を返す 記憶の棚 (スタック領域) 呼出 2 ! = 2・1 ! だな kaijo(2) kaijo(1) kaijo(0)の返事待ち 返事が来たら1倍して返す 待機中 1 を返す 呼出 1 ! = 1・0 ! だな kaijo(2) kaijo(1)の返事待ち 返事が来たら2倍して返す kaijo(1) 待機中 1 を返す 呼出 定義上 0 ! = 1 だ main() kaijo(2)の返事待ち 返事が来たらそれを表示 kaijo(0)

2 ! は 2・1 ! だから，kaijo(1)を呼び出し， 返ってきた値を 2 倍して main()関数に返す 第4章：再帰 この例では，2 ! を計算するために呼び出された関数 kaijo(2)の内部処理では， ということを行った． つまり，「 2 ! を求める」という問題を「1 ! を求める」という 部分問題 に分解した．そして，それらの問題は 同じ手順で解ける問題 となっている  kaijo という名前の関数が，その内部処理において， 　同じ kaijo という名前の関数を呼び出す構造 である！ 2 ! は 2・1 ! だから，kaijo(1)を呼び出し， 返ってきた値を 2 倍して main()関数に返す

第4章：再帰 関数 kaijo() の内部で自分自身 kaijo() を呼び出すことを，再帰呼出 (recursive call) という． kaijo(n) の処理では kaijo(n-1) が呼び出され， kaijo(n-1) では kaijo(n-2) が呼び出される. これが無限に続いてはならないので，必ず脱出口として停止条件が必要となる． 階乗の計算においては，0 ! = 1 が停止条件となる． long kaijo(int n) { if (n==0) return 1; else return n * kaijo(n-1); }

第4章：再帰 再帰呼出をしたとき，コンピュータ上では何が起こる？ kaijo(n) の中で kaijo(n-1) を呼び出した時点では，kaijo(n) の作業はまだ実行途上であり，kaijo(n-1) の値をもらうまでは仕事を続行できない状態である (制御が kaijo(n-1) に移されてしまう)．さらに，kaijo(n-1) の方では kaijo(n-2) をもらうまで仕事が中断する． 「現在中断している仕事の情報」をどこかで憶えておかないといけない．その情報とは，関数ごとのリターンアドレス (制御を戻す位置)，引数，ローカル変数である． コンピュータ上では，これらの情報がスタック (第5章) としてメモリ空間上に積み上げられる (教科書 p.167の図4.2)．つまり，再帰呼出を繰り返すたびにメモリが消費されていく．これにより，空間複雑度 が増える．

第4章：再帰 さらに，コンピュータが関数を呼び出すとき，一定の処理時間がかかる．これを 関数呼び出しのオーバーヘッド と呼ぶ．これにより，時間複雑度 も増加する． つまり，再帰呼出はメモリ消費量・実行時間の双方について，効率をいくぶん下げるものと言える． しかし，処理するべき問題やそこで扱うデータ構造が再帰呼出に適したものであるときは，再帰呼出を使った関数にすることが 自然 であり，プログラムも シンプル なものとなる． 一般的に，再帰呼出を使った関数はテクニカルであり，実行したときに何が起こるかをきっちり考えるのが難しいことがある．

4-1 再帰の簡単な例 教科書 p.168 のコードが先程の階乗の再帰的な関数． ただし，返値が long 型となっているのは，一般に階乗は非常に大きい数になるから． 4行目で return 1L; とあるが，これは return (long)1; と同じ意味で，long 型への キャスト である． long kaijo(int n) { if (n==0) return 1L; else return n*kaijo(n-1); }

4-1 再帰の簡単な例 フィボナッチ数列：1, 1, 2, 3, 5, 8, 13, 21, 34, … 第 n 項は第 n-1 項と第 n-2 項を加えたもので，第 1 項と第 2 項は 1 である．つまり， この場合，関数の中で 2つの再帰呼出 を行う (p.171)． fib(5)を呼び出すと，fib(4)+fib(3)を計算しようとする．とりあえず fib(5)の現在の状態をスタックに保存して，fib(4)を呼びだし，そちらに制御を移す．fib(4)では，fib(3)+fib(2)を計算する．いったん fib(4)の状況をスタックに保存して fib(3)を呼び出して結果待ち．fib(3)では…

4-1 再帰の簡単な例 組み合わせ nCr も再帰的に処理できる．つまり，より小さな n や r に関する問題に分解できる． 多項式の値を効率的に求める Hornerの方法 でも，再帰的に問題を解ける． ただし，再帰呼出において，係数の列 {a1, …, aN} を渡してやる必要がある (教科書 p.174 のコードでは，係数列を格納した配列の先頭へのポインタを渡している)．

ハノイの塔 再帰の問題でよく取り上げられる例題． 以下のように3本の棒 a, b, c が立っている．棒 a に，大きさの異なる n 枚のドーナツ状の板が下から大きい順に刺さっている．これを1枚ずつ移動させて棒 b に移す． ただし, 途中で小さい板の上により大きな板が積まれてはならない． 棒 c は作業用に使う． a b c

ハノイの塔 板が1枚しかないときは，考えるまでもない． a b c

ハノイの塔 板が2枚の場合, いきなり板 1 を目的地の棒 b に持って行ってしまうと, どうにもできなくなる． そこで，邪魔な板 1 を作業用の棒 c にいったん待避させ，板 2 を棒 b に持って行った上で，板 1 を板 2 の上に重ねる． 邪魔者である板 1 を いったん脇にどけてから， 板 2 を目的地へ動かし，その上に板 1 を戻す． a b c

ハノイの塔 では，n 枚の場合はどうか？ n 枚全体を a  b へ移すという問題を， (1) 上に乗る n-1 枚を a  c へ (3) n-1 枚を c  b へ という問題に分解すること ができる． (1)，(3) は,「同じ手順で解けるサイズの小さい問題」である． 　　　 再帰的解決が可能 a b c n 枚目 n-1 枚の邪魔者

ハノイの塔 さて，プログラムとしてどう記述するか？ hanoi(n,k,l)：n 枚の板を棒 k から棒 l へ移す関数 この関数では，上に乗る n-1 枚の板を残った一つの棒 m へ移動し，上が空いた n 枚目の板を棒 l へ移動した後，棒 m へ移しておいた n-1 枚を棒 l へ移動すればよい． n-1 枚の板の移動は再帰呼出 hanoi(n-1,k,m)および，hanoi(n-1,m,l) により実現できる． 終了条件として，n = 0 の場合は「何もしない」だけ． ソースコードは p.194 にあるので，各自目を通しておくこと．頭で考えようとすると非常に難しいように思える問題が，再帰呼出の利用によって，たった5行の関数になっている．これが再帰呼出の威力である．

クイック・ソート 実用上，最も速いソートアルゴリズムといわれている．quick sort と呼ばれるゆえんである．別名 分割ソート． クイック・ソートの基本原理は,「長距離の値同士を交換する方が効率的である」という発想である．例えば， 70 20 80 50 40 60 30 10 というデータがあるとき，70-20 の交換 よりも 70-10 の交換 の方が，ソートに対して 大きな寄与 を持つ． 基本的手順：配列中の適当な値 (これを 軸 と呼ぶ) を選び，軸より小さな値全てを配列の左側に，軸より大きな値全てを軸の右側に集め，「軸より小さいグループ」と「軸より大きいグループ」に 分割 する． それぞれのグループに対してクイック・ソートを行う． p.206～211

クイック・ソート 軸の選択方法は様々にあり得るが，最も安直な方法は，データ列の先頭を選択すること． 軸に対して，データ列の分割は以下のように行う．  左端の位置を i，右端の右隣の位置を j とする． i を右に動かしていき，軸以上の値の位置で止める． j を左に動かしていき，軸以下の値の位置で止める． i >= j なら⑥へ． i の位置のデータと j の位置のデータを交換して②へ． j の位置のデータを軸 (左端) と入れ替える．      left right 41 21 24 36 76 11 45 19 21 41 64 21 64 69 19 45 76 36 軸 軸 i i i i i i j i j j j j j 小さいグループ 大きいグループ left right left right 再帰呼出 (=j-1) (=j+1) 再帰呼出

クイック・ソート 再帰呼出の終了条件 (脱出口) は, 「ソート対象の長さが2以上 (left < right) でないときは何もせずに返る」 なぜなら，ソートの対象データ数が 0個あるいは 1個であるときは，何もしなくて良いから． 例えばデータ数 2 のクイック・ソートの結果は，軸の片側にデータが 1個，反対側にはデータが 0個の状態になり，次回の再帰呼出ではどちらも何もしない． 軸を left と right の中央のデータ位置 (left+right)/2 とすることもできる．この場合，軸も交換の対象に入れる． 軸を中央でとる場合，最初からある程度昇順または逆順のデータに対して，ほぼ半分ずつに分割できる．

クイック・ソート クイック・ソートが最も速くなるケースとは，分割によりデータが毎回ちょうど半分ずつに分かれる場合である． 2分探索での議論から，n 個のデータがちょうど半分ずつに分かれれば，分割の段数は log2n 段になる． 各段階のデータ総数は n, n 個のデータの分割：O(n)  クイック・ソートが 　 うまくいくと O(n log n) n 個 1 段目 2 段目 log2n 段目

クイック・ソート 一方，クイック・ソートにおいて最悪なのは，軸として選んだ値が毎回最小値または最大値の場合である． この場合，分割は 1個と残り全部 (nー1 個) となり，分割の段数は nー1 段．計算量は O(n2) となってしまう． でも平均的には O(nlogn) である. 重要なのは平均計算量．(平均計算量の導出はちょっと難しいので範囲外)． 安定性については，不安定． 30 40 20 50 10 10 30 40 20 20 30 50 10 10 50 40 20 i i i i j j i j j  20 と 20 が入れ替わってしまった

クイック・ソート 最悪のケースを想定すれば O(n2) となってしまうクイック・ソートではあるが，実用上は最速である． 5万個の整数値ソート時間 手法 ランダム 昇順　　 降順　　 直接選択法 15.82 15.80 22.11 バブル・ソート 40.09 21.75 43.46 シェーカー・ソート 24.40 0.00 35.14 基本挿入法 13.11 32.91 シェル・ソート 0.09 0.06 ヒープ・ソート (第6章) 0.05 0.03 クイック・ソート 0.02 0.01

クイック・ソート 最悪のケースを想定すれば O(n2) となってしまうクイック・ソートではあるが，実用上は最速である． 500万個の整数値ソート時間 手法 ランダム 昇順　　 降順　　 シェーカー・ソート 問題外 0.10 基本挿入法 0.17 シェル・ソート 21.42 14.66 16.27 ヒープ・ソート (第6章) 15.58 4.11 4.36 クイック・ソート 3.48 2.19 2.25 出展：林 晴比古，"C言語による実用アルゴリズム入門」， 　　　ソフトバンクパブリッシング

ではクイックソート万歳！でよいか？ 実際に研究室や企業でプログラムを組む場合，扱うデータ量が比較的少なく，ソートの起こる回数が少ない場合も 多い． このようなとき，クイック・ソートはプログラムも複雑，スタックも必要，関数呼び出しオーバーヘッドも発生， といった問題から，避けた方がよい場合もある． 実務をやっている人々の話とかを聞くと，問題によってはバブル・ソート等で済ましてしまうことも多いとか． このあたりの判断は経験の中で勘所を会得していく．

クイック・ソート (ソースコード) p.208 は，軸を左端とする場合のコード． ソート対象数列は配列 a[]．ソートを実行する実体は関数 void quick(int a[],int left,int right) 引数として a[] を渡すことによって，配列 a[] の先頭ポインタを渡している．第2, 第3引数はソート対象領域． ①で軸 s を設定し，i と j を初期化した後 while(1)のループに入る．つまり，break するまで繰り返す． 内部の1つめの while ループは，i に 1 を足してから a[i] と s を比較し，a[i] < s である間は繰り返す． while(a[++i]<s) なら 1 を足すのが先，while(a[i++]<s) なら 比較が先 となることに注意． あとは，既に見たアルゴリズム通りである．

4-3 順列の生成 n個の数字を使ってできる順列をすべて求める． n個の数字で順列を作る問題は，先頭の数字 (1, 2, …, n) ごとに，残り n-1 個の数字から順列を作る問題に帰着できる．更に，n-1 個の順列問題は n-2 個の順列問題に帰着できる  再帰的問題として解ける． 先頭の数字に 1～n を持ってくるには，数列の第 1 項と，第 1 項から第 n 項を一つ一つ交換する．1回交換するごとに，残りの n-1個の数字について同じ処理をするために，再帰呼出を行う． この再帰呼出処理が終わったら，入れ替えた数字を元に戻し，別の項との入れ替えを行って，再び再帰呼出を行う．これを繰り返せばよい．

4-3 順列の生成 例えば 1, 2, 3, 4 についての例では， 1, 2, 3, 4 の順列を求める問題 ＝ 1 と 1 を交換した 1234 のうち，2, 3, 4 の順列を求める問題 ＋ 1 と 2 を交換した 2134 のうち，1, 3, 4 の順列を求める問題 ＋ 1 と 3 を交換した 3214 のうち，2, 1, 4 の順列を求める問題 ＋ 1 と 4 を交換した 4231 のうち，2, 3, 1 の順列を求める問題 のように分解できる．更に，残り3つの数の順列問題も， 3通りの先頭数字それぞれに対する2数の順列問題になる．

4-3 順列の生成 数字同士の交換の基点 i は，再帰呼出が深くなるたびに1つずつ進めていく． 1234の順列を求める関数を呼び出す 1234の1番目の位置 1を1番目以降の位置と交換 まずは1と交換して1234 234の順列を求める関数を呼び出す 1234の2番目の位置 2を2番目以降の位置と交換 まずは2と交換して1234 34の順列を求める関数を呼び出す 1234の3番目の位置 3を3番目以降の位置と交換 …

4-3 順列の生成 1 2 3 4 1 2 3 4 終了条件：i==4 1 2 4 3 i=3 1 3 2 4 1 2 3 4 1 3 2 4 1 3 4 2 i=2 1 4 3 2 1 4 3 2 2 1 3 4 1 4 2 3 1 2 3 4 i=1 3 2 1 4 4 2 3 1

4-3 順列の生成 (ソースコード) 注意点：おそらく説明の分かりやすさを目的としてか, ここでは数字の位置の番号付けを 0 番からではなく 1 番から始めている点に注意．従って，N 個の数字を収める配列 p[] のサイズが N+1 になっている． 順列を求める再帰的関数は void perm(int i)． 数字の交換を行う位置 i が N 未満の時は，i 番目の数を i 番目以降の位置 j と順番に交換し，それぞれに対して perm(i-1) を再帰呼出したあと，入れ替えた順番を元に戻してから，関数を抜ける． 終了条件として，i == N に達したら，できた順列を画面に表示して関数を抜ける． 配列 p[N+1] はグローバル変数 (好ましくはない)．

辞書順式に順列生成 p.183 の図4.8を見ると分かるとおり，先程の例では，数字が辞書式順 (昇順) に生成されない． 例えば 1234 の1文字目を決める手順に関して，交換による方法では 1234, 2134, 3214, 4231 となった． ローテーションによる方法では，1234，2134，3124, 4123 となる．