岩井 儀雄 iwai@sys.es.osaka-u.ac.jp コンピュータ基礎演習 　ー探索、整列ー 岩井　儀雄 iwai@sys.es.osaka-u.ac.jp.

Presentation on theme: "岩井 儀雄 iwai@sys.es.osaka-u.ac.jp コンピュータ基礎演習 　ー探索、整列ー 岩井　儀雄 iwai@sys.es.osaka-u.ac.jp."— Presentation transcript:

1 岩井 儀雄 iwai@sys.es.osaka-u.ac.jp
コンピュータ基礎演習 　ー探索、整列ー 岩井　儀雄

2 データベース データベース 検索キー データの集まり．検索の効率を上げる工夫がされている 検索のための小さなデータ（キーワード）
… （例）個人データの場合，電話番号をキーに，住所，生年月日 　　　氏名などをデータに

3 データベース 挿入 データをキーとともに登録する 探索 与えられたキーを持つデータを探し出す 削除 与えられたキーを持つデータを削除する

4 線形探索と二分探索 線形探索法(linear search) 二分探索法(binary search) データを最初から順番に探索する
例）{2, 4, 5, 8, 9, 11, 6, 7, 15, 20} から15を探す 　最初の要素から始めて９回目→計算量O(n) 二分探索法(binary search) データをあらかじめソートしておき，中央の要素から検索する．

5 二分探索(binary search) {2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す １回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す １回目 {2, 4, 5, 6, 7, 8, 9, 11, 15, 20}

6 二分探索(binary search) {2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す ２回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す ２回目 {2, 4, 5, 6, 7, 8, 9, 11, 15, 20}

7 二分探索(binary search) {2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す ３回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す ３回目 {2, 4, 5, 6, 7, 8, 9, 11, 15, 20} 探索回数　３回 計算量　　log2(n) O(log n)

8 整列(sort) 内部整列(internal sort) 外部整列(external sort) 主記憶上で行う整列
外部記憶装置（テープ等）上で行う 整列アルゴリズムの優劣→比較回数と交換回数の大小

9 安定な整列(stable sort) 同じ値を持つデータ間の順序関係が整列の前後で保たれている 例）整列前： 7 9 5A 4 8 5B 2
　　整列後： 2 4 5B 5A 　（不安定）

10 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
整列前　 １回目 比較

11 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
１回目　 入替

12 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
１回目　 比較

13 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
１回目　 入替

14 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
１回目　 比較

15 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
１回目　 比較

16 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
１回目　 入替

17 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
１回目　 比較

18 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
１回目　 　　　　

19 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
２回目　 　　　　 30 46 30 45 13 30 13 74 13 55 6 13 6 20

20 単純な整列（バブルソート） 配列の後ろから先頭に向かって走査し，もし隣り合う二つの要素の大小関係が逆であったら入れ替える
２回目　 ３回目 ４回目 ５回目 ６回目 ７回目 ８回目　 ９回目　

21 バブルソート（疑似コード） for (i←0..n-1) for (j←n-1..i)
if !(a[j-1] ≦ a[j]) swap(a[j-1],a[j]) 右辺値の交換 整列アルゴリズムが満たす事後条件 計算量は O(n2)

22 バブルソート（Ｃ言語） for (i←0..n-1) for (j←n-1..i)
if !(a[j-1] ≦ a[j]) swap(a[j-1],a[j]) void bubble_sort(int a[],int n) { int I,j,t; for (int I=0; I<n-1; ++I) for (int j=n-1; j>I; --j) if (a[j-1] > a[j]) { t = a[j]; a[j] = a[j-1]; a[j-1] = t; } swap(a[j-1],a[j])に相当する

23 単純な整列（選択ソート） 未整列部分から最小の要素を選び出し，それを未整列部分の先頭と入れ替える 未整列部分 整列済
未整列部分から最小値を取り出し 続けると下記の条件を満たす 整列アルゴリズムが満たす事後条件

24 選択ソート 整列前　 １回目 入替

25 選択ソート 整列前　 １回目

26 選択ソート 整列前　 １回目 ２回目 入替

27 選択ソート 整列前　 １回目 ２回目 ３回目　 ４回目　 ５回目　 ６回目　 ７回目　 ８回目　 ９回目　

28 選択ソート（疑似コード） for (i←0..n-2) lowest←argmin(a[j]) i<j<n
swap(a[i],a[lowest])

29 選択ソート（Ｃ言語） void selection_sort(int a[],int n) {
int i,j,t,lowest,lowval; for (i = 0; i<n-1; ++i) { lowest = i; lowval = a[i]; for (j = i+1; j < n; ++j) if (a[j] < lowval) { lowval = a[j]; lowest = j; } t = a[I]; a[I] = a[lowest]; a[lowest] = t; argminの計算部分

30 選択ソートの計算量 ループ n 回，argmin の計算量 O(n) 選択ソートの計算量は O(n2)

31 単純な整列（挿入ソート） 配列の一部分が整列済みの時に，残りの要素を一つずつ整列済みの中に挿入する
整列前　 １回目　 ２回目 ３回目　 ４回目　 ５回目　 ６回目　 ７回目　 ８回目　 ９回目　

32 挿入ソート（疑似コード） for (i←0..n-1) j←i while (! (a[j-1] ≦ a[j]) )
swap( a[j-1], a[j] ) j←j-1 計算量：外側ループ O(n) 内側ループ O(n) 合計：　O(n2)

33 岩井 儀雄 iwai@sys.es.osaka-u.ac.jp
コンピュータ基礎演習 　ー計算量ー 岩井　儀雄

34 計算量(complexity) 時間計算量(time complexity) 空間計算量(space complexity)
アルゴリズムがデータに対してどれくらい時間がかかるかを示す 空間計算量(space complexity) アルゴリズムがデータに対してどれくらい記憶領域を必要とするかを示す 時間計算量と空間計算量はトレードオフの関係にあることが多い 計算機にとって記憶資源は潤沢にあるので，通常時間計算量の方が重きを置かれることが多い

35 オーダー記法Ｏ 計算量T(n)の上界値を評価するとき，O(f(n))という記法を用い，オーダーf(n) と読む．
ある正定数cとn0が存在して，n0以上のnに対して， 常に T(n) ≦cf(n) が成立するという意味 n0の役割は有限個の例外を許すことにある．

36 オーダー記法Ω 計算量の下界値のオーダーを表すには，記法Ωを用いる．T(n)=Ω(f(n))とは，

37 計算量とオーダ表記の関係 計算量の上界O 計算量 実際の計算量 有限個の 例外はOK 計算量の下界Ω n n0

38 オーダーの演算 例）

39 最悪計算量と平均計算量 同じアルゴリズムでも入力するデータに応じて計算量が変化する．そこで，客観的に測定し評価する必要がある．
最悪計算量 worst case complexity 全ての入力パターンに対して最大の計算量を要するものに基づいて定める 平均計算量 average complexity 全ての入力パターンとその入力の生起確率に基づいて計算量の平均を求める