- アルゴリズムの実践
アルゴリズムの実例としてデータの探索・整列を考えて見ます。
データを探したり、並び替える方法はいくつか考えられますが、
手順によって処理速度や必要な記憶領域などが異なります。
高速な手順ほど考え方がより複雑になってきます。
例えば100個のデータを処理する場合、探索では約100倍、
整列では約15倍の差が発生する場合があります。
データの個数が増えるほど、その差はより大きくなります。
- 探索法(サーチ)
- 線形探索法
先頭から順にデータを探す
※末尾に番兵(探索値と同じ値)を付加する場合もある
- 2分探索法
探索範囲を2等分しながら探す
※データが整列されている必要がある
- ハッシュ法
ハッシュ関数（計算式）で格納位置を求める
（例） 「値 mod ７」（余りを求める) → 格納位置
(ハッシュ関数)
ある値に対して一意となる別の値を生成
→ ハッシュ値
※ハッシュ値の競合（シノニム）
<探索イメージ> ※データ「５」の探索
| 対象データ |
１ |
２ |
３ |
４ |
５ |
６ |
| 線形 |
↑ |
↑ |
↑ |
↑ |
↑ |
|
| 2分 |
|
↑ |
|
↑ |
|
| ハッシュ |
|
|
↑ |
|
- 整列法(ソート)
・内部ソート（メモリ内）
小量のデータ
（基本整列法）
- 交換法(バブルソート)
隣り合うデータを比較して入れ替える
- 選択法
先頭から順に他のデータと比較して確定していく
- 挿入法
左側のデータ列と比較して最適な位置に値を移動する
後方から順に比較、入替えを行う
※挿入位置以降のデータを右側にずらす方法もある
（応用整列法）
基本整列法より高速に並び替えを行う
- シェルソート
- ある間隔離れたデータをグループ化する
(※配列の半分の長さなど)
※A、B、Cグループに分けた場合
- グループ内を挿入法でソートする
- グループの間隔を小さく(1/2)して上記を繰り返す
- ヒープソート
データ列をヒープ木に見立てて整列
(ヒープ木)
完全二分木 かつ 親＞＝子 又は 親＜＝子
※左右の子に大小関係はない
※完全二分木：同じ高さの子を左から右へ順に追加
（注：二分探索木は左の子＜＝親＜＝右の子）
(配列の添え字との対応)
※子の番号は2n + 1と2n + 2となる
- 親と子のデータを比較しヒープ木を構築
※親＞＝子、葉から根へ大きい値を移動
- 根の要素を取り出し、末尾の要素を根へ移動
※昇順の場合
- ヒープ木を再構成して繰り返す
- クイックソート
- 基準値を決める(主に配列の中心位置の値)
- 基準値を中心に左右に大小のグループ分けを行う
- 各グループ内で基準値を決めて上記を繰り返す
・外部ソート（メモリ外 ※主にHD上のファイル）
大量のデータ
- マージソート
- データ列分割（最小2個）
- グループ内でソート
- グループの併合（左右グループ）
| ５、９、２、１ |
| ↓（分割） |
| ５、９ |
２、１ |
| ↓ |
（入換） |
| ５ |
９ |
１ |
２ |
| ↓（併合） |
| １ |
２ |
５ |
９ |
- オーダー（O記法）
要素数と処理回数の増加関係式
探索や整列の速度評価の目安となるおおよその数値
探索法
| 線形探索法 |
O（n） |
遅い
↓
早い |
| 2分探索法 |
O（log2n） |
| ハッシュ法 |
O（1） |
整列法
| 基本 |
交換ソート | O（n^2） |
遅い
↓
早い |
安定性
○ |
| 選択ソート |
△ |
| 挿入ソート |
○ |
| 挿入 |
シェルソート | O（n^3/2）※O（n^1.2） |
× |
| 選択 |
ヒープソート |
O（nlog2n） |
× |
| 交換 |
クイックソート |
× |
| 併合 |
マージソート |
○ |
※log2 10 = 3.321928095
※log2 100 = 6.64385619
※log10 2 = 0.301029996
- 安定な整列
同値データ → 整列前の順序を保つ
（該当ソート）交換、挿入、マージ
※安定でない整列（保たない）
（該当ソート）クイック、ヒープ、シェル
※選択は両パターン
|
