Views
Document
Event
File
Folder
Image
Link
News Item
Photo
Photo Album
Topic
Weblog
Wiki Page
整列・探索
Document Actions
整列
- bubble sort （あまり使ってはいけない例）
- quick sort （と、言う名前のライブラリがある）
バブルソート
- データの交換で整列を行う
- メモリー領域が少なくて済む
バブルソートのアルゴリズム
- 配列にデータが入っている
- 隣同士を比較して、順が違えば交換。
- 1回走査すると最後に最大（又は最小）が収まる。
- 2回目の走査は配列の最後からひとつ手前までやればよい。
- 比較・交換の回数は O( n2 )
バブルソートのプログラム例
クイックソート
- 中間値を決める
- 小さいものが左に、大きいもの右に行くように、交換する。
- 左、右、それぞれに入ったものを上記と同様にして分けていく。
- この再帰的操作を繰り返すことで全体が整列される。
- 比較・交換の回数は O( n log n )
クイックソートのプログラム例
- quicksort.py
- 上の例は「中間値」がわかっている（ので簡単になっている）
- 実際に使われている例: FreeBSD qsort()
探索（データ検索）
- 探索しやすい構造にデータを入れていく
- 二分探索（整列済みのデータ）
- ハッシュ法
- B 木
線形探索
二分探索
- データは整列済み
- 配列の中央にあるデータと比較
- 大小によって右又は左を探す
- 以上の繰り返し
- 探索は O( log n ) データの追加は O(n)
ハッシュ法
- データを配列に入れれば、探索は「配列の要素指定」と同じ
- 探索鍵となるデータが疎であると配列空間（メモリー）が無駄
- 鍵 -> ハッシュ関数で探索空間を圧縮する
- ハッシュ関数の例: 剰余
- ハッシュの衝突：工夫が必要
B 木
- 根以外の節には、m個以上、2m個以下のキー(n個)... a[i]
- 根には 1個以上 2m個以下のキー
- 葉はすべて同一レベル
- 葉以外の節には、部分木へのポインタが n+1個 ... p[i]
- 任意の節において、キーは昇順に整列
- p[i-1]に属するキー < a[i] < p[i] に属するキー
m 次の B-tree
２次の B-tree
キーの追加
- 単純な例
キーの追加
- 葉の分割
キーの削除
- 単純な例
キーの削除
- アンダーフロー
キーの削除
問題
- 次のうちデータ数が多くなると比較的に遅くなるものを選べ
- バブルソート
- クィックソート
- 線形探索
- ハッシュ法探索
