先週はオンデマだった
範囲はここから今回まで
今回はマージソートと探索
マージソート
- 分割統治
- 配列に自由にアクセスできないときや大きなサイズの配列に対して実用的
- クイックソートより遅いが安定
整列済みのデータ2つのマージは先頭を見て小さい方を取り出せば完了する
→リストとの相性がいい(アクセスするのが常に先頭だから)
長さ1になるまで分割すればソート済みだからあとは合わせるだけになる
graph TD A["5 4 6 1 2 7 3"] --> B["5 4 6 1"] A --> C["2 7 3"] B --> D["5 4"] B --> E["6 1"] C --> F["2 7"] C --> G["3"] D --> H["5"] D --> I["4"] E --> J["6"] E --> K["1"] F --> L["2"] F --> M["7"] H --> N["4 5"] I --> N J --> O["1 6"] K --> O L --> P["2 7"] M --> P G --> R["2 3 7"] P --> R N --> Q["1 4 5 6"] O --> Q Q --> S["1 2 3 4 5 6 7"] R --> S
分割して要素数1（＝整列済み）になったら、隣同士をマージしていく。
void merge_array( recordtype a[], int M, recordtype b[], int N ){
int i, j, k;
recordtype c[LIMIT]; // マージ結果を格納する一時配列
i = 1; // 配列aの先頭インデックス
j = 1; // 配列bの先頭インデックス
// 番兵: 各配列の末尾にINT_MAXをセット
// → 一方の配列が空になっても必ず他方から選ばれる
a[M+1].key = INT_MAX;
b[N+1].key = INT_MAX;
for( k = 1; k <= M+N; k++ ) {
if ( a[i].key < b[j].key ) {
c[k] = a[i++]; // aの方が小さければaから取り出し
} else {
c[k] = b[j++]; // bの方が小さければbから取り出し
}
}
}リストのマージ
終端が共通の二股になったリストを扱う
graph TD subgraph "① 元のリスト" direction LR A1["5"] --> A2["4"] --> A3["6"] --> A4["1"] --> A5["2"] --> A6["7"] --> A7["3"] --> A8["z"] end subgraph "② Tortoise & Hareで中央を探して分割" direction LR B1["5"] --> B2["4"] --> B3["6"] --> B4["1"] --> B5["z"] C1["2"] --> C2["7"] --> C3["3"] --> C4["z"] end subgraph "③ 再帰的mergesort → マージ結果" direction LR D1["1"] --> D2["2"] --> D3["3"] --> D4["4"] --> D5["5"] --> D6["6"] --> D7["7"] --> D8["z"] end
struct node {
elementtype element;
struct node *next;
};
typedef struct node *link;
link merge ( link a, link b ){
link c = z; // cは終端zを指す（マージ結果の末尾）
do {
if ( a->element <= b->element ) {
c->next = a; // aのノードをcの後ろに繋ぐ
c = a; // cを今繋いだノードに更新
a = a->next; // aを次のノードに進める
} else {
c->next = b; // bのノードをcの後ろに繋ぐ
c = b; // cを今繋いだノードに更新
b = b->next; // bを次のノードに進める
}
} while ( c->element != INT_MAX ); // 終端zに到達するまで繰り返す
c = z->next; // マージ結果の先頭ノードを取得
z->next = z; // zを終端（自己参照）に戻す
return c;
}1つの配列を使うときは両端に最小値が来るようにしてから両端から走査することで番兵がなくても良くなる(先に使い果たした配列の次のインデックスに対応するのは全体の最大値だから)
void mergesort ( recordtype a[], int l, int r ){
int i, j, k, m;
recordtype b[LIMIT]; // マージ用の一時配列
if ( l < r ) {
m = ( r + l ) / 2; // 中央を求める
mergesort ( a, l, m ); // 左半分を再帰的にソート
mergesort ( a, m+1, r ); // 右半分を再帰的にソート
// 左半分をbの左半分にそのままコピー
for ( i = m; i >= l; i-- ) { b[i] = a[i]; }
i = l;
// 右半分をbの右半分に**逆順**でコピー（番兵代わり）
for ( j = m+1; j <= r; j++ ) { b[r - (j - (m+1))] = a[j]; }
j = r;
// 両端からマージ（左端iと右端jを比較）
for ( k = l; k <= r; k++) {
if ( b[i].key < b[j].key ) {
a[k] = b[i++]; // 左側が小さければ左から
} else {
a[k] = b[j--]; // 右側が小さければ右から
}
}
}
}リストの場合は中央を見つけてに分割して配合する
中央のノードのnextを終端に設定し、再帰的にソートする
→中央をどうやって見つける？
ウサギとカメのアルゴリズム
ウサギ（hare）は2倍速、カメ（tortoise）は1倍速でリストを走査する。
中央の見つけ方：
a = c（カメ）,b = c->next->next->next（ウサギ、初回だけ3つ進む）- ウサギが終端
zに着くまで、カメを1歩、ウサギを2歩進める- ウサギが終端に着いたとき、カメが指しているのが中央
効率は？
方式 ポインタを進める回数 ① 長さを数えてから半分進む 回 ② ウサギとカメ ウサギ + カメ 回
→ 効率は同じ 。メリットは「1回の走査で中央が求まる＝コードがスマート」「循環検出にも応用できる（フロイドの循環検出法）」
配列なら
a[(l+r)/2]で終わりなので、リストだからこそ生きるアルゴリズム。
link mergesort ( link c ){
link a, b;
// 要素数1ならソート済み → そのまま返す
if ( c->next == z ) { return c; }
a = c; // aは先頭を保持（カメのスタート位置）
b = c->next; b = b->next; b = b->next; // b(ウサギ)を2歩+1歩先行させる
// Tortoise & Hare: b(ウサギ)が終端zに着くまで
while ( b != z ) {
c = c->next; // c(カメ)は1歩進む
b = b->next; b = b->next; // b(ウサギ)は2歩進む
}
// この時点でc(カメ)は中央を指している
b = c->next; // bを後半の先頭ノードに
c->next = z; // 前半の末尾を終端zに繋ぐ（2分割）
return merge( mergesort( a ), // 前半を再帰的にソート
mergesort( b ) ); // 後半を再帰的にソート
}マージソートは安定していてかつ実用的な速度
探索
- 線形探索
- 二分探索
- 内挿探索
線形探索
int search( elementtype x, elementtype a[], int N ){
int i;
i = 0;
while ( i < N && a[i] != x ) { i++; } // 先頭から順に探索
return i < N; // 見つかれば真(1)、Nまで探し切れば偽(0)
}これだとループごとに比較が3つ（i<N, a[i]!=x, i++）あって効率が良くない
→ 番兵によってループ内の演算を減らす
int search( elementtype x, elementtype a[], int N ){
int i;
a[N] = x; // 番兵: 末尾にxをセット
for ( i = 0; a[i] != x; i++ ) ; // 条件は1つだけ！必ず見つかる
return i < N; // i<Nなら番兵以外、i==Nなら番兵
}比較回数は最悪 回、成功時平均 回
→ データが整列済みなら になった時点で探索終了でき、不成功時も平均 に抑えられる
int search( elementtype x, elementtype a[], int N ){
int i;
a[N] = x; // 番兵
for ( i = 0; a[i] < x; i++ ) ; // x以上の要素を探す（整列済みを利用）
return ( i < N && a[i] == x ); // 見つかって、かつ値が一致すれば真
}二分探索
ソート済みが前提
データをに分割して入っている可能性のある部分データに対してまたに分割という操作を繰り返す
中央を求めて探索対象と中央を比較するのを繰り返す
比較回数はで平均は
int search( elementtype x, elementtype a[], int N ){
int l, r, m;
l = 0; r = N - 1;
while ( l < r ) {
m = ( l + r ) / 2; // 中央を求める
if ( x < a[m] ) {
r = m - 1; // 前半側を探索
} else if ( x > a[m] ) {
l = m + 1; // 後半側を探索
} else {
l = r = m; // 見つかった→範囲を収束
}
}
return ( l == r && a[l] == x ); // 候補が1つに絞られた＆一致?
}内挿探索
データが整列済み、一様に分布しているならそのあたりにあるだろうというあたりを見に行く
→区間の比を見る
int search( elementtype x, elementtype a[], int N ){
int l, r, m;
l = 0; r = N - 1;
while ( l < r ) {
// 内挿: 値の分布から位置を推定（一様分布を仮定）
m = l + ( x - a[l] ) * ( r - l ) / ( a[r] - a[l] );
if ( x < a[m] ) {
r = m - 1;
} else if ( x > a[m] ) {
l = m + 1;
} else {
l = r = m;
}
}
return ( l == r && a[l] == x );
}理論上は二分探索より速い()が、m の計算コストが高いので が大きくないと二分探索より遅いこともある