データ構造論講義ノート（３章）

第３章
　

　探索問題と配列
　

　多数のデータを格納しておき、その中から適切なデータを探索するという問題は非常に応用範囲が広い。本章では、比較的変化の少ない静的なデータ処理に適している配列を利用した探索問題について説明する。

　３．１　探索問題

○課題

住所録が与えられた時、指定された氏名の住所を検索できるようにせよ。
　

○外部仕様

　以下のような住所録ファイルを読み込み、標準入力から入力された氏名に対する住所を標準出力に出力する。

　　　　　　　住　所　録　フ　ァ　イ　ル

氏　名　欄	住　　所　　欄
福井太郎　･･･金沢花子	福井市文京３－９－１　･･･金沢市角間町

○概要設計

　１．住所録データを住所録表に読み込む

　２．標準入力から入力された氏名を住所録表中の氏名フィールドで検索する

　３．氏名フィールドに対応する住所フィールドを標準出力に出力する

　　　　　　　　　住　所　録　表

氏名フィールド	住所フィールド
福井太郎　･･･金沢花子	福井市文京３－９－１　･･･金沢市角間町

○詳細設計

　●抽象データ型によるカプセル化－アクセス関数の定義

　ａ．住所録表の生成

　　T=CREATE(F)：住所録ファイル F からデータを読み込み、住所録表 T を生成する

　ｂ．住所の検索

　　A=SEARCH(T, N)：住所録表 T から氏名 N を検索し、住所 A を返す

　●データ構造

　ａ．住所レコード

typedef struct {

　　　　char name[NAME_SIZE];

　　　　char address[ADDRESS_SIZE];

} AddressRec;

　ｂ．住所録レコード

typedef struct {

　　　　int size;　　　　　　　　　　　 /* 住所録データ数 */

　　　　AddressRec table[TABLE_SIZE];　 /* 住所録表本体 */

} AddressTableRec, *AddressTable;

AddressTableRec address_rec;　　　　　　/* 住所録表を静的に割り当てる */

○コーディング

【CREATE操作】

AddressTable CREATE(char *F)

{

　　　　FILE *stream; int i;

　　　　if((stream=fopen(F, "r"))==NULL) {

　　　　　　　　fprintf(stderr, "ファイル %s は読めません\n", F);

　　　　　　　　exit(1);

　　　　}

　　　　for(i=0; fscanf(stream, "%s %s",

　　　　　　　　　　　　address_rec.table[i].name,

　　　　　　　　　　　　address_rec.table[i].address)!=EOF; ++i);

　　　　address_rec.size=i;

　　　　return(&address_rec);

}

【main関数】

#include <stdio.h>

#define NAME_SIZE 20　　　/* 氏名の最大長 */

#define ADDRESS_SIZE 50　　　/* 住所の最大長 */

#define TABLE_SIZE 100　　 /* 氏名・住所の最大数 */

void main(int argc, char **argv)

{

AddressTable T;

char name[NAME_SIZE], *address;

if(argc!=2) {

fprintf(stderr, "使用法： %s ファイル名\n", argv[0]);

exit(1);

}

T=CREATE(argv[1]);

for(;;) {

printf("Name> ");

if(gets(name)==NULL) break;

if((address=SEARCH(T, name))==NULL)

printf("見つかりません。\n");

else printf("%s\n", address);

}

問 3.1.1　氏名・住所以外に電話番号欄があり、氏名を指定して住所・電話番号を出力したい場合にはどのようなアクセス関数を準備すればよいか考えよ。

問 3.1.2　氏名・住所以外に電話番号欄があり、氏名あるいは電話番号を指定し、指定した以外の項目を出力したい場合にはどのようなアクセス関数を準備すればよいか考えよ。

問 3.1.3　同姓同名を考慮したり、部分一致による検索を可能とすると、検索結果が複数存在する場合がある。この時、どのようなアクセス関数を準備すればよいか考えよ。

　３．２　線形探索

《概要》比較対象ｘを配列のｎ個の要素と順番に比較して探索する

　　　　　　配列Ａ

　　　　0

　　　　1

　　　 n-1
　

比較
　　　　　　 (1) i=0
　　　　ｘ
　　　　　　 (2) i>=n ならば、終了（見つからなかった）

　　　　　　 (3) A[i]==x ならば、終了（見つかった）

　　　　　　 (4) i=i+1

　　　　　　 (5) (2) へ
　

○コーディング

【SEARCH操作】

　配列Ａは T->table、要素数ｎは T->size に対応する。

char *SEARCH(AddressTable T, char *x)

{

　　　　int i;

　　　　for(i=0; i<T->size; ++i)

　　　　　　　　if(strcmp(T->table[i].name, x)==0)

　　　　　　　　　　　　return(T->table[i].address);

　　　　return(NULL);

}

○時間量

・比較回数を時間量とする

　最悪時間量：最大ｎ個のデータと比較する

　　　　Ｔ_ｍａｘ(n)＝n＝Ｏ(n)

　平均時間量：全てのデータが均一に検索されると仮定すると、

　　　　Ｔ_ａｖｇ(n)＝(n+1)/2＝Ｏ(n)

・時間量Ｏ(n)は、データ量に比例して処理時間がかかる

　　　　大きなデータには対処しにくい

問 3.2.1　検索の結果として、データの比較回数を出力する処理を追加せよ。

問 3.2.2　氏名以外の項目で検索できるように、フィールドの指定を行う検索機能を持つ SEARCH操作を定義せよ。

問 3.2.3　前方一致検索を行うために、SEARCH操作で最初のデータを見つける処理と、それ以後のデータを見つける処理ができるようにせよ。

問 3.2.4　全てのデータが均一に検索される場合の平均時間量が (n+1)/2 となることを確認せよ。（ヒント）比較回数は１回からｎ回までである。

　３．３　２分探索

《概要》探索範囲の中央のデータと比較することにより探索範囲を半分にする

《条件》昇順に整列済みのデータを対象に探索する

　　　　　　　　配列Ａ　　　　　　　　　　　　　　　　配列Ａ

　top
　　　　　　0
　探索範囲

　mid　　　n/2

　　　　　 n-1
　bot

比較　　　　 top
　　　　ｘ　　　　　　　0
　　　　　　　探索範囲

　　　　　　　mid　　　n/4

　探索範囲の　bot
　　　　　　　　　　　 n/2
　　中央

　　　　　　　　　　　 n-1
　

比較
　　　　ｘ

　　探索範囲の

　　　中央

　

(1) 探索範囲先頭 top=0、探索範囲最後尾 bot=n-1

(2) top>bot ならば、終了（見つからなかった）

(3) 中央位置 mid=(top+bot)/2

(4) x==A[mid] ならば、終了（見つかった）

(5) x<A[mid] ならば、x は top～mid-1 の間にあるので、bot=mid-1

(6) x>A[mid] ならば、x は mid+1～bot の間にあるので、top=mid+1

(7) (2) へ

例題3.3.1　２分探索により「０　１　２　３　４　５　８」から、４を探索せよ。

　①　４：　０　１　２　３　４　５　８

　　　　　　　　　　　　　　　　　　　探索範囲

　　　　　　　　　　　中央（4>3）

　②　４：　０　１　２　３　４　５　８

　　　　　　　　　　　　　　　　　　　探索範囲

　　　　　　　　　　　　　　　中央（4<5）

　③　４：　０　１　２　３　４　５　８

　　　　　　　　　　　　　　　探索範囲

　　　　　　　　　　　　　中央

　比較回数３回（２分探索の最大比較回数）。線形探索の最大比較回数７。

○コーディング

【CREATE操作】

　他の部分に影響を与えないために、CREATE操作に整列のための処理を追加する。現在の CREATE操作の名前を CREATE_REC とし、住所録表を整列するための操作を SORT操作とする。（3.4節で説明する）

AddressTable CREATE(char *F)

{

　　　　AddressTable T;

　　　　T=CREATE_REC(F);　　　　/* 古いCREATE操作と同じ処理 */

　　　　SORT(T);

　　　　return(T);

}

【SEARCH操作】

　配列Ａは T->table、要素数ｎは T->size に対応する。

char *SEARCH(AddressTable T, char *x)

{

　　　　int top, mid, bot, cmp;

　　　　top=0; bot=T->size-1;

　　　　while(top<=bot) {

　　　　　　　　mid=(top+bot)/2;

　　　　　　　　cmp=strcmp(x, T->table[mid].name);

　　　　　　　　if(cmp==0) return(T->table[mid].address);

　　　　　　　　　　　　　　　　　　　　　　　　/* x==A[mid] */

　　　　　　　　else if(cmp<0) bot=mid-1;　　　 /* x<A[mid] */

　　　　　　　　else top=mid+1;　　　　　　　　 /* x>A[mid] */

　　　　}

　　　　return(NULL);

}

○時間量

・比較回数を時間計算量とする

　最悪時間量をＴ_ｍａｘ(n)とおくと、ｎ＝２^ｋ－１の場合には、

　　　Ｔ_ｍａｘ(１)＝１　　　　　　　　　　要素数が１の時は、比較は１回

　　　Ｔ_ｍａｘ(ｎ)＝１＋Ｔ_ｍａｘ((n-1)/2)　　一回比較すると探索範囲は1/2になる

　　　　ここで、ｎ＝２^ｋ－１を代入して、

　　　　　　　　＝１＋Ｔ_ｍａｘ(２^{（ｋ－１）}－１)

　　　　　　　　　　・　・　・　・

　　　　　　　　＝(ｋ－１)＋Ｔ_ｍａｘ(２^１－１)＝(ｋ－１)＋Ｔ_ｍａｘ(１）＝ｋ

　　　　　　　　＝log_２(ｎ＋１)

　 ∴Ｔ_ｍａｘ(ｎ)＝Ｏ(log_２ｎ)

　平均時間量は、全てのデータが均一に検索される場合、１回で検索されるデータが１個、２回が２個、３回が２^２個、... となるので、全てのデータについての時間量の総合計を、Ｔ_ｓｕｍ(n)とすると、

　　　　Ｔ_ｓｕｍ(n)＝１×１＋２×２＋３×２^２＋・・・＋Ｔ_ｍａｘ(n)×２^Ｔ_ｍａｘ^{（ｎ）ー１}

　　　　　　　　＝１×１＋２×２＋３×２^２＋・・・＋ｋ×２^ｋー１

　　　　　　　　＝(ｋ－１)×２^ｋ＋１

　　　　　　　　＝(ｋ－１)×(２^ｋ－１)＋ｋ

　 ∴Ｔ_ａｖｇ(ｎ)＝Ｔ_ｓｕｍ(n)／ｎ

　　　　　　　＝（ｋ－１）＋ｋ／ｎ

　　　　　　　＝log_２(ｎ＋１)－１＋log_２(ｎ＋１)／ｎ

　　　　　　　＝Ｏ(log_２ｎ)

・時間量Ｏ(log_２ｎ)は、データ量が大きくなっても処理時間があまり大きくならない

　　　　大きなデータに対処できる

○線形探索と２分探索の計算量の比較

ｎ	Ｏ(ｎ)	Ｏ(log_２ｎ)
１０１０^２１０^３１０^４	１０　　１００　１０００１００００	４ ( 3.32) 　７ ( 6.64) １０ ( 9.97) １４ (13.29)

問 3.3.1　２分探索において、問 3.2.1、問 3.2.2、問 3.2.3 を実現せよ。

問 3.3.2　２分探索により「０　１　２　３　４　５　６　７　８」から７を探索する場合、比較回数は何回か。また、最大比較回数は何回か。

問 3.3.3　全てのデータが均一に検索される場合にｎ＝２^ｋ－１ならば平均時間計算量が(k-1)×2^ｋ+1 となることを確認せよ。（ヒント）Ｔ_ｓｕｍ(n)－２×Ｔ_ｓｕｍ(n)を考えよ。

問 3.3.4　一般的な場合について、最悪時間計算量を求めよ。（ヒント）ｎが偶数の場合には、Ｔ_ｍａｘ(ｎ)＝１＋Ｔ_ｍａｘ(n/2)である。

　３．４　整列（ソート）

　ソートとは、何らかの基準に基づきデータに順序を付け、その順序に従ってデータを並べ直す操作である。

　　内部ソート：　メモリのみを利用する

　　外部ソート：　外部の補助記憶装置を利用する

　以下では異なる内部ソート法により、SORT操作を実現する

３．４．１　バブルソート(bubble sort)

《概要》

　１．下から上方向に、隣接する２つの要素を順に比較し、必要ならば要素を交換する

　２．最小の要素が最も上に浮上がるので、それ以外の要素について１．を繰り返す

　　　　　　配列Ａ　　　　　　　　下から上へ

　　　　0

　　　　1

　　　 n-1
　

　　　　　　　　　　　　　0
　比較・交換
　　　　　　　　　　　　　1
　比較・交換

　比較・交換

　比較・交換
　　　　　　　　　　　　 n-1
　

最小要素

　比較・交換

　比較・交換

　比較・交換

　

(1) ソート範囲上限 i=0

(2) i>=n-1 ならば、ソート終了

(3) 比較下側位置 j=n-1

(4) j<=i ならば、i=i+1、(2) へ

(5) A[j-1]>A[j] ならば、A[j-1] と A[j] を交換する

(6) j=j-1

(7) (4) へ

例題3.4.1.1　「３　２　０　５　８　３　４　１」という８個のデータに対して、バブルソートを行え。比較回数および交換回数はそれぞれ何回か。

　下（右）から上（左）方向に比較・交換を進める。

　①　３　　２　　０　　５　　８　　３　　４　　１

　　　　交換　交換　　　　交換　交換　交換　交換

　②　０　　３　　２　　１　　５　　８　　３　　４

　　　　　　　交換　交換　　　　交換　交換

　③　０　　１　　３　　２　　３　　５　　８　　４

　　　　　　　　　　交換　　　　　　　交換　交換

　④　０　　１　　２　　３　　３　　４　　５　　８

　⑤　０　　１　　２　　３　　３　　４　　５　　８

　⑥　０　　１　　２　　３　　３　　４　　５　　８

　⑦　０　　１　　２　　３　　３　　４　　５　　８

　比較回数は２８回、交換回数は１３回である。

○コーディング

【SORT操作】

void SORT(AddressTable T)

{

　　　　int i, j;

　　　　for(i=0; i<T->size-1; ++i)

　　　　　　for(j=T->size-1; j>i; --j)

　　　　　　　　if(strcmp(T->table[j-1].name, T->table[j].name)>0)

　　　　　　　　　　　　SWAP(&T->table[j-1], &T->table[j]);

　　　　　　　　　　　　/* SWAP: 要素を交換する関数 */

}

【SWAP関数】

void SWAP(AddressRec *rec1, AddressRec *rec2)

{

　　　　AddressRec rec;

　　　　memcpy(&rec, rec1, sizeof(AddressRec));

　　　　memcpy(rec1, rec2, sizeof(AddressRec));

　　　　memcpy(rec2, &rec, sizeof(AddressRec));

}

○時間量

・比較と交換の２種類の操作が存在するが、交換回数の最悪値は明らかに比較回数に一致　する。ここでは、比較回数を時間量とする。

①最悪時間量をＴ_ｍａｘ(n)とおくと、ソート範囲上限 i は 0～(n-2)、ソート対象位置 j は (n-1)～(i+1) まで変化するので、

　　　　Ｔ_ｍａｘ(n)＝(ｎ－１)＋(ｎ－２)＋・・・＋１

　　　　　　　　＝ｎ(ｎ－１)／２

　　　　　　　　＝ｎ^２／２－ｎ／２

　　　∴Ｔ_ｍａｘ(n)＝Ｏ(ｎ^２)

②平均時間量は、最悪時間量と同じである。

・時間量Ｏ(ｎ^２) は、データ量の２乗に比例する

　　　　大きなデータでは急速に処理時間が長くなる

問 3.4.1.1　ソートの際のデータの比較回数および交換回数を出力する処理を追加せよ。

問 3.4.1.2　バブルソートにおいては、データが整列された状態になった後も比較を続ける場合がある。データが整列された時にはソートを終了するように改良せよ。（ヒント）ソート対象位置 j のループにおいて交換が起こらなければ整列されたと判断できる。

問 3.4.1.3　「３　２　０　５　８　３　４　１　３　２」をバブルソートした場合、比較回数と交換回数はそれぞれ何回か。問 3.4.1.2 を実現したときはどうか。

問 3.4.1.4　バブルソートにおいて、どのようなデータを対象としたとき交換回数が最小となるか、また最大となるか。

３．４．２　シェルソート(shell sort)

《概要》

　１．ｈ間隔離れた要素の各系列において、それぞれソートを行う

　２．ｈを小さくして１．を繰り返すことにより異なる系列のデータが組み合わされる

　３．ｈ＝１の時には全ての系列が組み合わされ、ソートが完了する

　　　　　　配列Ａ

A[0]

A[1]

・・・

A[h]

A[h+1]

・・・

A[mh]

A[mh+1]

・・・
　

ｈ間隔の系列　　１間隔の系列

　

A[0]

A[1]

・・・

A[h]

A[h+1]

・・・

A[mh]

A[mh+1]

・・・
　

　ｈの減少の方法によって計算量は変化する。ここでは、ｈ＝[n/2], [n/4], ..., 1 という方法を採用する。なお、[x] は、ガウス記号であり、ｘを越えない最大の整数である。

(1) 間隔 h=n/2

(2) h<1 ならば、ソート終了

(3) 系列下側位置 i=h

(4) i>=n ならば、h=h/2、(2) へ

(5) 比較上側位置 j=i-h

(6) j<0 ならば、i=i+1、(4) へ

(7) A[j]<A[j+h] ならば、i=i+1、(4) へ

(8) A[j] と A[j+h] を交換する

(9) j=j-h

(10) (6) へ

例題3.4.2.1　「３　２　０　５　８　３　４　１」という８個のデータに対して、シェルソートを行え。ただし、ｈ＝[n/2], [n/4], ..., 1 とする。

　①ｈ＝４：　３　　２　　０　　５　　８　　３　　４　　１

　　　　　　　　　　　　　　　　　　　　　交換

　②ｈ＝２：　３　　２　　０　　１　　８　　３　　４　　５

　　　　　　　　　交換

　　　　　　　０　　２　　３　　１　　８　　３　　４　　５

　　　　　　　　　　　　交換

　　　　　　　０　　１　　３　　２　　８　　３　　４　　５

　　　　　　　　　　　　　　　比較　　　　交換

　　　　　　　０　　１　　３　　２　　４　　３　　８　　５

　③ｈ＝１：　０　　１　　３　　２　　４　　３　　８　　５

　　　　　　　　　　　比較　交換

　　　　　　　０　　１　　２　　３　　４　　３　　８　　５

　　　　　　　　　　　　　　　　　比較　交換

　　　　　　　０　　１　　２　　３　　３　　４　　８　　５

　　　　　　　　　　　　　　　　　　　　　　　比較　交換

　　　　　　　０　　１　　２　　３　　３　　４　　５　　８

　比較回数は２１回、交換回数は７回である。

　（バブルソートの比較回数は２８回、交換回数は１３回）

○コーディング

【SORT操作】

void SORT(AddressTable T)

{

　　　　int i, j, h;

　　　　for(h=T->size/2; h>0; h/=2)　　 /* h=n/2, n/4, ..., 1 */

　　　　　　for(i=h; i<T->size; ++i)

　　　　　　　　for(j=i-h; j>=0; j-=h)

　　　　　　　　　　if(strcmp(T->table[j].name, T->table[j+h].name)>0)

　　　　　　　　　　　　SWAP(&T->table[j], &T->table[j+h]);

　　　　　　　　　　else

　　　　　　　　　　　　break;

}

○時間量

・比較と交換の２種類の操作が存在するが、交換回数の最悪値は比較回数以下である。

　最悪時間量は、証明は省略するが、以下のようになる。

　　　　Ｔ_ｍａｘ(n)＝Ｏ(ｎ^１．５) 　（ｈ＝[ｎ／２^α], α＝1, 2, 3, ...）

問 3.4.2.1　シェルソートにおいて、問 3.4.1.1　を実現せよ。

問 3.4.2.2　「３　２　０　５　８　３　４　１　３　２」をｈ＝[n/2], [n/4], ..., 1によりシェルソートした場合、比較回数と交換回数はそれぞれ何回か。

問 3.4.2.3　問 3.4.2.2 と同じデータをｈ＝[0.45454n], [0.45454^２n], ..., 1 によりシェルソートした場合、比較回数と交換回数はそれぞれ何回か。

問 3.4.2.4　シェルソートにおいて、どのようなデータを対象としたとき交換回数が最小となるか。

３．４．３　クイックソート(quick sort)

《概要》

　１．ある要素（ピボットと呼ぶ）を選択し、上の区間にはピボット以下のもの、下の区　間にはピボット以上のものが配置されるように並べ直す。

　２．上の区間および下の区間各々について１．を繰り返す。

　３．全ての区間で要素数が１になれば、ソートが完了する。

　　　　　　配列Ａ

　　　　0

　　　 n-1
　

ピボット

　　　　　　　　　　　0
　　　ピボット以下

　　　　　のデータ

ピボットの選択

　　　ピボット以上

　　　　　のデータ
　　　　　　　　　　 n-1
　

　クイックソート

　クイックソート

　

　ピボットの選択方法には、①先頭、中央、あるいは末尾の要素、②上から順に見て最初に得られる異なる大きい方の値、③先頭・中央・末尾の３要素の中央値、⑤ランダムに選択した３要素の中央値、などがあり、全要素を均等に２つの部分に分割できるものを選択することが望ましい。ここでは、①の先頭要素とする。

(1) ソート対象区間上限 l=0

(2) ソート対象区間下限 r=n-1

(3) ピボット pivot=A[l]

(4) PARTITION(l, r, pivot, &L, &R)

　l から r の区間を、pivot 以下の要素の区間と、pivot 以上の要素の区間に分割し、pivot 以下の要素の末尾位置 L と pivot 以上の要素の先頭位置 R を返す

(5) l から L の区間をクイックソートする

(6) R から r の区間をクイックソートする

　(5),(6) は、区間を縮小してクイックソート自体を呼び出す、すなわち、再帰呼び出しを行っていることになる。

　(4) は、以下のような処理である。

　　　　　　配列Ａ　 l　　　　　　　　　　　　　配列Ａ

　　　　0

　　　 n-1
　

・・・

>=pivot

<=pivot

・・・

ピボットより

小さい要素

　　　　　　　　　　　 l

　交　　　　　　　 L

　換　　　　　　　 R

　　　　　　　　　　　r

ピボットより

大きい要素

・・・

<=pivot

>=pivot

・・・

　ピボット以下の

　　要素

　ピボット以上の

　　要素

　

(1) l>r ならば、終了

(2) A[l]<pivot ならば、l=l+1、(2) へ

(3) A[r]>pivot ならば、r=r-1、(3) へ

(4) l>r ならば、終了

(5) A[l] と A[r] を交換する

(6) l=l+1, r=r-1

(7) (1) へ

例題3.4.3.1　「３　２　０　５　８　３　４　１」という８個のデータに対して、クイックソートを行え。ただし、ピボットとして、先頭の要素を採用せよ。

　各段階におけるピボットに下線を付す。

　①　３　　２　　０　　５　　８　　３　　４　　１

　　ｌ　　　　　　　　　交換　　　　　　　　　ｒ

　　　１　　２　　０　　５　　８　　３　　４　　３

　　　　　　　　　　　ｌ　交換　　ｒ

　　　１　　２　　０　　３　　８　　５　　４　　３

　　　　　　　　　　　ｒ　　　　ｌ

　②　１　　２　　０　　３｜８　　５　　４　　３

　　ｌ　　交換　ｒ　　　　　　　　交換

　　　０　　２　　１　　３｜３　　５　　４　　８

　　　ｒ　　ｌ　　　　　　　　　　　　　　ｒ　　ｌ

　③　０｜２　　１　　３｜３　　５　　４｜８

　　　　　ｌ交換ｒ　　　ｌ　ｒ

　　　０｜１　　２　　３｜３　　５　　４｜８

　　　　　ｒ　　　ｌ　　　ｒ　　　　ｌ

　④　０｜１｜２　　３｜３｜５　　４｜８

　　　　　　　　ｌ　ｒ　　　　　　ｌ交換ｒ

　　　０｜１｜２　　３｜３｜４　　５｜８

　　　　　　　　ｒ　　　ｌ　ｒ　　　ｒ　　ｌ

　比較および交換の回数は以下のようになる。

　　　　ピボットとの比較：　　　　　　　４０回（10+12+10+8）

　　　　交換：　　　　　　　　　　　　　　６回（2+2+1+1）

　比較回数がかなり多いが、ピボットとの比較は要素間の比較よりコストが小さい。

○コーディング

【SORT操作】

void SORT(AddressTable T)

{

　　　　QSORT(T, 0, T->size-1);

}

void QSORT(AddressTable T, int l, int r)

{

　　　　char *pivot;

　　　　int L, R;

　　　　if(l<r) {

　　　　　　　　pivot=T->table[l].name; /* 先頭要素をピボットとする */

　　　　　　　　PARTITION(T, l, r, pivot, &L, &R);

　　　　　　　　if(l<L) QSORT(T, l, L);

　　　　　　　　if(R<r) QSORT(T, R, r);

　　　　}

void PARTITION(AddressTable T, int l, int r, char *x, int *L, int *R)

{

　　　　while(l<=r) {

　　　　　　　　while(strcmp(T->table[l].name, x)<0) ++l;

　　　　　　　　while(strcmp(T->table[r].name, x)>0) --r;

　　　　　　　　if(l<=r) {

　　　　　　　　　　　　if(l<r) SWAP(&T->table[l], &T->table[r]);

　　　　　　　　　　　　++l; --r;

　　　　　　　　}

　　　　*L=r; *R=l;

}

○時間量

・比較と交換の２種類の操作が存在するが、交換回数の最悪値は比較回数以下である。

　比較回数を時間量とする。

①最良時間量は、ｎ個の要素が常に半分に分かれるという、分割を行った場合である。

　ただし、ｎ＝２^ｋ（ｋは整数）を満足すると仮定している。

　　　　　　　　　　　　ｎ

　　　　 n+2

　　　　ｎ／２　　　　

(n/2+2)*2=n+4

　ｎ／４

(n/4+2)*4=n+8　log_２n 段

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 (=k)

　・　・　・　・　・　・　・　・　・　・　・　・　・

２

・　・　・　・　・　・

２

(2+2)*n/2=n+n

・　・　・　・　・　・

　　　　　　　 ^ｌｏｇ_２^ｎ

　∴Ｔ_ｍｉｎ(ｎ)≦∑(n+2^ｉ)＝nlog_２n+2(2^ｌｏｇ_２^ｎ-1)＝n(log_２n+2)-2＝Ｏ(nlog_２n)

　　　　　　　　^ｉ＝１

②最悪時間量は、ｎ個の要素が常に 1:(n-1) に分かれるという、分割を行った場合である。

　PARTITION での比較は、l > r の状態となるまで行うので、最大 n+2 回である。

　　　　　　　　　　　　ｎ

n+2

　　　　　　　　　　ｎ－１

n+1

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 n-1 段

　　　　　　　　　ｎ－２

　　・　・　・　・　・　・　・　・　・　・　・　・

・　・　・　・　・　・

２

・　・　・　・　・　・

　　　　　　　　^ｎ＋２

　∴Ｔ_ｍａｘ(ｎ)≦∑ｉ＝(n+6)(n-1)/2＝n^２/2+5n/2-3＝Ｏ(n^２)

　　　　　　　　^ｉ＝４

③平均時間量は、ｎ個の要素の分割の仕方として、i:(n-i) が均等に起ると仮定する。

　　　　　　　^ｎ－１

　Ｔ_ａｖｇ(ｎ)≦∑(Ｔ_ａｖｇ(i)+Ｔ_ａｖｇ(n-i))/(n-1)+(n+2)

　　　　　　　^ｉ＝１

　　　　　　 ^ｎ－１

　　　　＝２∑Ｔ_ａｖｇ(i)/(n-1)+(n+2)

　　　　　　 ^ｉ＝１

　数学的帰納法により、Ｔ_ａｖｇ(ｎ)≦４ｎlogｎを証明する。

ｎ＝２の時、Ｔ_ａｖｇ(1)＝０より、

　　　　Ｔ_ａｖｇ(2)≦2Ｔ_ａｖｇ(1)/1+(2+2)＝4≦8log2＝5.545...

ｎ＝ｉの時成立すると仮定すれば、ｎ＞ｉの時、

　　　　　　　　　　^ｎ－１　　　　　　　　　　　　^ｎ

　　　　Ｔ_ａｖｇ(n)≦2∑4ｉlogｉ/(n-1)+(n+2)≦8∫ｘlogｘdx/(n-1)+(n+2)

　　　　　　　　　　^ｉ＝１　　　　　　　　　　　　^２

　　　　　　　　　　　　　　　　　　　^ｎ

　　　　　　　　＝8[(x^２/2)logx-(x^２/4)]/(n-1)+(n+2)

　　　　　　　　　　　　　　　　　　　^２

　　　　　　　　＝4nlogn-(2n^２-4nlogn+16log2-8-(n+2)(n-1))/(n-1)

　　　　　　　　＝4nlogn-(n^２-4nlogn-n+16log2-6)/(n-1)

　　　　　　　　≦4nlogn

　∴Ｔ_ａｖｇ(ｎ)＝Ｏ(ｎlogｎ)

○その他

①既に一部が整列しているようなデータでは、分割位置が偏り効率が非常に悪くなる。

　このようなデータに対してはシェルソートの方が有効である。

②区間内のデータ数が少ないときには単純なソート法を用いる方が速い。

　クイックソートにより分割し、要素数がある程度以下になれば、他のソート法に切り替えるという組み合わせ的な方法も有効である。

問 3.4.3.1　クイックソートにおいて、問 3.4.1.1　を実現せよ。

問 3.4.3.2　先頭・中央・末尾要素の中央値をピボットに選択するように、QSORT関数を修正せよ。

問 3.4.3.3　要素数が１０以下の場合にはシェルソートに切り替えるように、QSORT関数を改良せよ。

問 3.4.3.4　「３　２　０　５　８　３　４　１　３　２」をクイックソートした場合、比較回数と交換回数はそれぞれ何回か。ピボットの選択方法を変更した時、どのような影響があるかを調べよ。

問 3.4.3.5　クイックソートにおいて、Ｔ_ａｖｇ(ｎ)＝Ｏ(ｎlogｎ) となることを確認せよ。

問 3.4.3.6　高速なクイックソートでさえ、Ｔ_ａｖｇ(ｎ)＝Ｏ(ｎlogｎ) であり、ソートと２分探索をあわせれば明らかに線形探索よりも効率が悪い。それにも関わらず２分探索が用いられる理由を述べよ。

３．４．４　マージソート

　３．５　ハッシング

《概要》

　１．データを整数値化し、その数値をインデックスとして配列に格納しておく

　２．検索対象を数値化し、その数値をインデックスとして配列を参照する

　　　　　　配列Ａ　　ハッシュ関数

　　　　0

　　　ｈ

　　　 n-1
　

　ｘ

　　　　　　　　　ｘの整数値化→ｉ　　　ｈ＝ｈ(ｘ)　　　　　　　　　ｉのｎ進数値化→ｈ

　　　　　　　　　（０≦ｈ≦ｎ－１）

　　検索対象ｘは、ｈに存在する

　

　　　　　ハッシュ表

・異なるデータに対してハッシュ関数値が同じになった場合、データの格納方法を工夫す　る必要がある

○オープンハッシュ法（外部ハッシュ法）

　複数のデータを保持するための領域（ハッシュバケット）を設ける

　　　　　　　　　　　　　　　　ハッシュバケット

　　　　　バケット表

　　　　0

　　　　1

　　　 n-1
　


	ｘ	ｙ	ｚ

	ｕ
・　・　・

	ｖ	ｗ

・データを格納する領域に制限が存在しない

○クローズドハッシュ法（内部ハッシュ法）

　再ハッシュにより別の値を求め、空き領域に格納する

　　　　　ハッシュ表

　　　　0

　　　 n-1
　

　ｘ

空き領域

　　ｙ（h(y)=h(x)）

　　再ハッシュ h_ｉ(y), i=1,2,3,...

　　・空き領域を見つける

　

・実現が容易であるが、一定領域を使用するため、データ数がｎを越えてはならない

・再ハッシュの方法

①線形探索法（linear probing）

　　　　h_ｉ(y)=(h(y)+i) mod N

②２次関数検査法（quadratic probing）

　　　　h_ｉ(y)=(h(y)+i^２) mod N

③ダブルハッシング（double hashing）

　　　　h_ｉ(y)=(h(y)+h_ｉｎｃ(y)*i) mod N, h_ｉｎｃは２段階目のハッシュ関数

○文字データのハッシュ関数

　文字データは基本的に可変長であるが、各文字は文字コードを持つため、文字コードを元にハッシュ関数を構成する。文字列 x が、文字 x_１ x_２ ... x_Ｌ（Ｌは文字長）と表現される場合には、

　①単純加算

　　　　　　　　^Ｌ

　　　　h(x)＝Σx_ｉ

　　　　　　　 _ｉ＝１

　②重み付け加算

　　　　　　　　^Ｌ

　　　　h(x)＝Σａ^{（Ｌ－ｉ）}x_ｉ、ａは重み係数

　　　　　　　 _ｉ＝１

などがある。

例題3.5.1　a, ab, abc, ..., abcdefghij という１０個のデータを n=15 の大きさの配列でハッシングすることを考える。ハッシュ関数として、各文字コードの和を n で割った余り、再ハッシュを線形探索法とした時、全てのデータを検索する際の比較回数の合計と平均値を求めよ。なお、a, b, c, ... の文字コードは、97, 98, 99, ... とする。

　ハッシュ関数値は、順に 7, 0, 9, 4, 0, 12, 10, 9, 9, 10 であるから、ハッシュ表は以下のようになる。

　　　　　ハッシュ表

　　　　0　　　　1　　　　2　　　　3　　　　4　　　　5　　　　6　　　　7　　　　8　　　　9　　　 10　　　 11　　　 12　　　 13　　　 14
　

ababcde

abcd

a

abcabcdefgabcdefghabcdefabcdefghiabcdefghij
　

h(ab)=0h(abcde)=0, h_１=1

h(abcd)=4

h(a)=7

h(abc)=9h(abcdefg)=10h(abcdefgh)=9, h_１=10, h_２=11h(abcdef)=12h(abcdefghi)=9, h_１=10, h_２=11, h_３=12, h_４=13h(abcdefghij)=10, h_１=11, h_２=12, h_３=13, h_４=14
　

　比較回数の合計は、1+1+1+1+2+1+1+3+5+5=21、平均値は、2.1 である。２分探索法の比較合計 1回*1+2回*2+3回*4+4回*3=29、平均値 2.9 と比較してもかなり高速である。

○ハッシュ表アクセス関数

　ハッシュ表に対するアクセス関数を定義する。ただし、クローズドハッシュ法で、再ハッシュには線形探索法を採用するものとする。

　ａ．ハッシュ関数

　　h=HASH(x)： x に対するハッシュ値を返す

　ｂ．データの参照

　p=FIND(T, x)：住所録表 T から、キー x に対するデータの存在位置あるいは空き領域 p を返す

　ｃ．データの格納

　　INSERT(T, x, y)：住所録表 T のキー x に対して、データ y を格納する

　ｄ．空き領域の判定

　int EMPTY(x)：空き領域かどうかを判定し、空き領域ならば１(true)、そうでなければ０(false)を返す。

○コーディング

●ハッシュ表アクセス関数

【HASH関数】

int HASH(char *x)

{

　　　　int i;

　　　　unsigned int h;　　　　 /* 加算結果が溢れても正の数とする */

　　　　h=0;

　　　　for(i=0; x[i]!='\0'; ++i)

　　　　　　　　h+=x[i];　　　　/* 文字コードの合計 */

　　　　　　　　/* h=(h<<1)+x[i]; a=2 の重み付け加算*/

　　　　return(h % TABLE_SIZE);

}

【FIND関数】

　検索するキーの存在するインデックスあるいは再ハッシュによる空き領域のインデックスの値を返す。

int FIND(AddressTable T, char *x)

{

　　　　int h, h0;　　　　　　　　　　　　　　　/* h0: 起点 */

　　　　h=h0=HASH(x);

　　　　do {

　　　　　　　　if(EMPTY(T->table[h].name) ||　 /* 空き領域 */

　　　　　　　　　　　　strcmp(x, T->table[h].name)==0)

　　　　　　　　　　　　return(h);

　　　　　　　　if(++h==TABLE_SIZE) h=0;　　　　/* h_ｉ(x)=HASH(x)+i */

　　　　} while(h!=h0);　　　　　　　　　　　　 /* 表を一巡しない間 */

　　　　return(-1);

}

【INSERT関数】

void INSERT(AddressTable T, char *x, char *y)

{

　　　　int h;

　　　　h=FIND(T, x);

　　　　if(h>=0) {

　　　　　　　　strcpy(T->table[h].name, x);

　　　　　　　　strcpy(T->table[h].address, y);

　　　　}

　　　　else

　　　　　　　　fprintf(stderr, "ハッシュ表が溢れました。");

}

【EMPTYサブ関数】

int EMPTY(char *x)

{

　　　　return(x[0]=='\0');

}

●アクセス関数

【CREATE 操作】

AddressTable CREATE(char *F)

{

　　　　FILE *stream; int i;

　　　　AddressRec rec;

　　　　if((stream=fopen(F, "r"))==NULL) {

　　　　　　　　fprintf(stderr, "ファイル %s は読めません\n", F);

　　　　　　　　exit(1);

　　　　}

　　　　for(i=0; fscanf(stream, "%s %s", rec.name, rec.address)!=EOF;

　　　　　　　　 ++i)

　　　　　　　　INSERT(&address_rec, rec.name, rec.address);

　　　　address_rec.size=i;

　　　　return(&address_rec);

}

【SEARCH操作】

char *SEARCH(AddressTable T, char *x)

{

　　　　int h;

　　　　h=FIND(T, x);

　　　　if(!EMPTY(T->table[h].name))

　　　　　　　　return(T->table[h].address);

　　　　else　　return(NULL);

}

○時間量

　データ格納時と検索時の比較操作を時間量とする。比較回数については、データを格納・検索する際には FIND 関数を用いているため、FIND における比較回数を考慮すればよい。

①最良時間量

　データ格納・検索の時に、再ハッシュが起きなければ、比較回数は１回である。

　∴Ｔ_ｍｉｎ(ｎ)＝１＝Ｏ(１)

②最悪時間量

　データ格納・検索の時に、再ハッシュが起こり続けた場合、最大ｎ回比較が必要である。

　∴Ｔ_ｍａｎ(ｎ)＝ｎ＝Ｏ(ｎ)

③平均時間量

　Ｍ個のデータを大きさＮ（≧Ｍ）のハッシュ表に登録する場合を考える。

・格納時の比較回数

　既にｍ個のデータが格納されており、ｍ＋１番目のデータを格納する場合を考える。ｍ個のデータがランダムに位置しているとすれば、最初の場所 h(x) がふさがっている確率は、ｍ／Ｎである。次の場所もふさがっている確率は、残りＮ－１カ所にｍ－１個がランダムに位置していると考えると、(m-1)/(N-1) となる。したがって、空き領域を見つけるまでの平均回数は、次のようになる。

　　　　　　m　 m(m-1)　　　　　 m(m-1)･･･(m-N+2)(m-N+1)

　　　　1+　　+　　　　+ ･････ +　　　　　　　　　　　　

　　　　　　N　 N(N-1)　　　　　 N(N-1)･･･　 2　　　1　

　　　　　　m　　m^２　　　　　 m^Ｎ　　　^∞　　　　 ^∞

　　　≦1+　　+　　+ ･････ +　　 ≦1+Σ(m/N)^ｉ＝Σ(m/N)^ｉ＝N/(N-m)

　　　　　　N　　N^２　　　　　 N^Ｎ　　 _ｉ＝１　　　 _ｉ＝０

　したがって、ハッシュ表にＭ個のデータを格納する際の合計回数は、

　　　　^Ｍ－１　　　　　^Ｍ　　　　　　　　　　　 ^Ｍ

　　　　ΣN/(N-m)≦∫ N/(N-x)dx＝[-Nlog(N-x)] ＝Nlog(N/(N-M))

　　　　_ｍ＝０　　　　　_０　　　　　　　　　　　 _０

であり、１個当たりの平均回数は、

　　　　Ｔ_ａｖｇ(N, M)≦(N/M)log(N/(N-M))

・検索時の比較回数

　検索対象が存在しない場合は、１個のデータを格納する時と同じなので、

　　　　N/(N-M)

　検索対象が存在する場合は、１回目からＭ回目までいずれかで一致するため、Ｍ個のデータを格納する時と同様に、

　　　　(N/M)log(N/(N-M))

・M=n/2 とすれば、N/(N-M)=2, (N/M)log(N/(N-M))=1.38... であり、１，２回で格納あるいは検索が可能となる。

問 3.5.1　ハッシングにおいて、問 3.2.1、問 3.2.2、問 3.2.3 を実現せよ。

問 3.5.2　線形探索法以外の再ハッシュ方法を実現せよ。

問 3.5.3　例題3.5.1 において、ハッシュ表の大きさを n=20 とした場合の比較回数の合計と平均値を求めよ。

問 3.5.4　例題3.5.1 において、ハッシュ関数を文字コードに末尾から順に 1, 2, 22, ...という重みをつけた場合の比較回数の合計と平均値を求めよ。

問 3.5.5　例題3.5.1 において、再ハッシュを２次関数検査法で行った場合の比較回数の合計と平均値を求めよ。

問 3.5.6　オープンハッシュ法において、格納・検索の際の時間量を評価せよ。

問 3.5.7　文字列に対するハッシュ値の計算方法にはどのようなものが考えられるか。