第7講: 平成19年11月2日 (金) 4限 E252教室 クイックソートと オーダー記法.

Presentation on theme: "第7講: 平成19年11月2日 (金) 4限 E252教室 クイックソートと オーダー記法."— Presentation transcript:

1 第7講: 平成19年11月2日 (金) 4限 E252教室 クイックソートと オーダー記法

2 第4講の復習 整列アルゴリズム ソーティング，並べ替え O(n2) のアルゴリズム 選択ソート バブルソート 挿入法
最小値を探して前から並べる バブルソート 隣の要素の大小関係で交換していく 挿入法 前から順番に入るべき位置に入れていく 第7講 クイックソートとオーダー記法 平成19年11月2日

3 第5,6講の復習 整列アルゴリズム O(n log n) のアルゴリズム マージソート クイックソート
2つ，4つ，8つと整列する列を併合（マージ）していく クイックソート 基準値（ピボット）を選んで，それより小さい数値の列と大きい数値の列に分けていく 分割統治法 第7講 クイックソートとオーダー記法 平成19年11月2日

4 今日の講義の内容 整列アルゴリズム クイックソートの復習 オーダー記法の復習 第7講 クイックソートとオーダー記法 平成19年11月2日

5 整列（ソーティング）問題とは ソーティング：Sorting，整列，並べ替え 昇順ソート（Ascending Sort）
ｎ個のデータ列をある基準に従って順に並べ替える処理 昇順ソート（Ascending Sort） 単調増加に整列（小さいもの順に整列） 一般的にソートといえばこちらを指す 降順ソート（Descending Sort） 単調減少に整列（大きいもの順に整列） 昇順と降順は比較に用いる不等号を逆にする ソーティングにおける時間計算量は比較の回数を基準として考える if 文を用いた大小比較 第7講 クイックソートとオーダー記法 平成19年11月2日

6 整列問題の分類 安定性 記憶領域 安定ソート 外部ソート 内部ソート ソートの際，同等なデータには元の並び順が保存されているソート法
元々学籍番号順に並んでいたデータをその成績順にソートしたとき，同じ点数の生徒は学籍番号順に並んでいるようなソート法 記憶領域 外部ソート ソートの際，定数個より多くの外部記憶領域を必要とするソート法 現在操作中の配列の他に，その長さに応じた別のデータ格納用の配列が必要なソート法 内部ソート ソートの際，定数個の記憶領域で十分なソート法 現在操作中の配列の内部の入れ替えだけで十分なソート法 第7講 クイックソートとオーダー記法 平成19年11月2日

7 準備 入力は長さ n の数値の列 数値の大小関係には推移律が成り立つ Swap 手続き
{a1, a2, a3, a4, … , an} で表す 数値の大小関係には推移律が成り立つ a < b で b < c なら a < c Swap 手続き 配列中の２つの要素の値を入れ替える手続き 実際には以下のようにテンポラリ（一時的）の変数を準備して入れ替えする swap (a, b) { temp ← a ; a ← b ; b ← temp ; } 第7講 クイックソートとオーダー記法 平成19年11月2日

8 クイックソート クイックソート：Quick Sort Charles A. R. Hoare が考案 内部ソートでは最も速いアルゴリズム
平均計算量：O(n log n) 第7講 クイックソートとオーダー記法 平成19年11月2日

9 クイックソート：概要 アルゴリズム 再帰アルゴリズムで実装（しない方法もある） 分割統治法：Divide and Conquer
分割された２つの部分に同様の操作を，分割部分の要素数が１になるまで繰り返す 再帰アルゴリズムで実装（しない方法もある） 分割統治法：Divide and Conquer a* a* a* 以下のデータ a* 以上のデータ 第7講 クイックソートとオーダー記法 平成19年11月2日

10 クイックソート：概念図 a* b* a* c* d* b* e* a* f* c* g* 整列済みデータ a* 以下のデータ
x < b* b* b* > x a* x < c* c* c* < x d* b* e* a* f* c* g* 整列済みデータ 第7講 クイックソートとオーダー記法 平成19年11月2日

11 クイックソート：partition手続き
基準値 (ピボット) によってデータを２つの部分に分割 partition( a* , left , right ) 手順 基準値を a[right] とする（簡単のため） 左から走査し基準値より大きい要素を探索：位置 i 右から走査し基準値より小さい要素を探索：位置 j 両者の位置関係が i < j ならば交換 i ≧ j となるまで繰り返す i ≧ j となったら i と right の位置の要素を交換 a[left] a[right] 第7講 クイックソートとオーダー記法 平成19年11月2日

12 クイックソート：partition手続き
10 8 5 7 9 2 6 3 1 4 両方見つかったら 交換 i は左から，基準値より大きな値を探す j は右から，基準値より小さな値を探す 1 8 5 7 9 2 6 3 10 4 1 3 5 7 9 2 6 8 10 4 a* < 6 なので飛ばす 1 3 2 7 9 5 6 8 10 4 i ≧ j となったら，i と right を交換 1 3 2 4 9 5 6 8 10 7 第7講 クイックソートとオーダー記法 平成19年11月2日

13 何故こんなややこしい交換をするのか 内部ソートにするため 外部ソートにしていいなら，もう少し簡単
基準値より大きいか小さいかで 2 つの 配列を用意し，前から順番に振り分ける 4 ２ 3 1 10 8 5 7 9 6 小の配列，基準値，大の配列 の順でつなぎ合わせる 外部に長さ n に比例した記憶領域が必要（マージソートと同じ欠点） 10 8 5 7 9 2 6 3 1 4 基準値より小さい値用配列 ２ 3 1 基準値より大きい値用配列 10 8 5 7 9 6 第7講 クイックソートとオーダー記法 平成19年11月2日

14 クイックソート：計算量 最良の場合 最悪の場合 基準値によって左側の列と右側の列が半分に別れていくとき 再帰の繰り返しは log n 回
全体は O(n log n) 最悪の場合 基準値が最大値，または最小値のとき 列の大きさが 1 つずつしか減っていかない 再帰の繰り返しは n 回 全体は O(n2) 第7講 クイックソートとオーダー記法 平成19年11月2日

15 クイックソート：高速化の知恵 基準値 (ピボット) の選び方
今までは右端の値 (a[right]) を基準値にしたが，三数値を取って (a[left], a[(left+right)/2], a[right]) その真ん中の値を基準値 a* に採用 こうすると最悪の状況になる可能性が小さくなる 規模が小さい等、クイックサーチが不適であることがわかれば挿入法にスイッチ（そのほうが早い） 第7講 クイックソートとオーダー記法 平成19年11月2日

16 クイックソートのまとめ 平均計算量 O(n log n) 最悪計算量 O(n2) 安定ソートではない 内部ソート
整列されていない列でのデータの入れ替えでは元の順番が保存されない 内部ソート 外部記憶を必要としない 最悪計算量は悪いが，実際の使用状況では最速のソーティングアルゴリズム (マージソートより速い) さまざまなところで使用されている 第7講 クイックソートとオーダー記法 平成19年11月2日

17 整列問題の計算量の下限 いままで勉強した整列アルゴリズム O(n log n) より早いアルゴリズムはあるか?
大きく分けて O(n2) のアルゴリズムと O(n log n) のアルゴリズム O(n log n) より早いアルゴリズムはあるか? ないなら，既に2つの O(n log n) のアルゴリズム（マージソートとクイックソート）は勉強したので問題ない あるなら，最も早いアルゴリズムも勉強せねばならない・・・・というか知りたいよね? 第7講 クイックソートとオーダー記法 平成19年11月2日

18 整列問題の計算量の下限の証明 並べ替える問題＝元の要素を適切に置き換える問題 配列の添字を並べ替えて，配列の内容を整列させる
添字の並べ方は 10×9×8×…×2×1=10!通り つまり n! 通り（n の階乗）の組合せのうち， 正解は 1 通り ここで，n! = O(nn) であることがわかっている [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 1 2 3 4 5 6 7 8 9 10 [8] [5] [7] [9] [2] [6] [3] [1] [4] [0] 10 8 5 7 9 2 6 3 1 4 第7講 クイックソートとオーダー記法 平成19年11月2日

19 整列問題の計算量の下限の証明 if 文では2つに分岐できる ＝場合の数を半分に減らせる
m回 if 文で判定すると 2m の組合せを分けられる n!通りの組合せから正解の1つを選ぶには 最低でも 2m=O(nn) 回の比較が必要 両辺を底が2の対数を取ると log2 2m = m = O(log2 nn) = O(n log n) つまり，比較回数 m は少なくとも O(n log n) よって，最も最良の計算量は O(n log n) 第7講 クイックソートとオーダー記法 平成19年11月2日

20 アルゴリズムのオーダー n n0 f (n) のオーダーである：O( f (n) ) と書く
ある正定数 c , n0 が存在し，n0 < n である n に 対して常に g(n) < c・f (n) が成立するなら g(n) = O( f(n) ) である アルゴリズムの実行時間が関数 f(n) の増加率を超えない c・f (n) 係数は考えない (c はいくらでも良い) 実際の計算量 g (n) n n0 第7講 クイックソートとオーダー記法 平成19年11月2日

21 オーダーの見積もり 計算量のオーダー表現： アルゴリズムを，小さな操作単位に分割 各操作単位のオーダーを評価
きわめて大雑把な評価尺度 大雑把な見積もりで導出することができる アルゴリズムを，小さな操作単位に分割 各操作単位のオーダーを評価 操作単位のオーダーを合成して，全体のオーダーを得る 第7講 クイックソートとオーダー記法 平成19年11月2日

22 アルゴリズムの分割 実行時間が入力サイズに依存しないステップ （基本ステップ） ループ回数が入力サイズに依存するループ構造
search(key) /* 配列permの中から値keyの位置を探す */ int key; { int i = 0; while (i < MAX) { if (perm[i] == key) return(i); i++; } return(-1); 実行時間が入力サイズに依存しないステップ （基本ステップ） ループ回数が入力サイズに依存するループ構造 第7講 クイックソートとオーダー記法 平成19年11月2日

23 オーダーの評価（１） ルール１：基本ステップのオーダーは O(1) 基本ステップ 一般に，以下は基本ステップでないことに注意
実行時間が入力サイズに依存しないステップ 変数への代入 数値の演算 ポインタ操作　etc. 一般に，以下は基本ステップでないことに注意 （入力サイズに依存した）配列のコピー 関数呼び出し 第7講 クイックソートとオーダー記法 平成19年11月2日

24 オーダーの評価（２） ルール２： O( f (n) ) の操作と O( g(n) ) の操作を連続して行う場合，操作全体のオーダーは O(max( f (n), g(n) )) O( f (n) ) O(max( f (n), g(n) )) O( g(n) ) ただし，関数の大小比較は増加率により行う 1 < log n < n < n log n < n2 < n3 < … 2n 第7講 クイックソートとオーダー記法 平成19年11月2日

25 オーダーの評価（３） ルール３： O( f (n) ) 回だけまわるループの内部で O( g(n) ) の操作を実行する場合，全体のオーダーは O( f (n) × g(n) ) 係数は無視してよい 最高次の項以外は無視してよい O( f (n) ) 回ループ O( f (n) * g(n) ) O( g(n) ) 第7講 クイックソートとオーダー記法 平成19年11月2日

26 ポイント (1/3) 係数は無視する 2n→n，3n→n，10n2→n2，5log n→log n 足し算は足し算でなくなる
O(n)+O(n) → O(n+n) → O(2n) → O(n) O(1)+O(1) → O(1+1) → O(2) → O(1) 仮に元の係数が 100 だとしても，定数 c はいくらでも大きく決められるので，c を 100 倍にすれば問題ない 係数と増加率は関係ない (係数大きくしても関数の増加率は変わらない) 第7講 クイックソートとオーダー記法 平成19年11月2日

27 ポイント (2/3) 次数の大きい項だけ残す n2+n → n2，n3+100n2 → n3， n + n log n → n log n
足し算すると次数の低い項は消える O(n2)+O(n) → O(n2+n) → O(n2) O(n2)+O(n2)+O(n3)+O(n2) → O(n3+3n2) → O(n3) n2+10n というのは n2+10n+25-25=(n+5)2-25 であり，n2 のグラフをただ x 軸方向に-5， y 軸方向に-25ずらしただけ つまり増加率は n2 となんら変わらないので 10n は無視できる -5 -25 無限に大きな n を考えてみよう (例えば n = ) そうすれば -5 も -25 もほとんど増加率には無意味 第7講 クイックソートとオーダー記法 平成19年11月2日

28 ポイント (3/3) ループは掛け算 O(n)×O(n2) → O(n×n2) → O(n3) 括弧の中の計算は先にやっておく
O(n)×{O(1)+O(n)} → O(n)×{O(n)} → O(n2) 内側から順番に計算していくとややこしくない 必ず1つの掛け算になる O(n) × { O(n) × {{O(1) + O(n)} × {O(1) + (1)}}} も括弧を1つずつ外していけばやさしい 第7講 クイックソートとオーダー記法 平成19年11月2日

29 オーダー評価の例 O(1) O(n) O(1) O(n) O(n) O(1) O(1) O(1) O(1)
search(key) int key; { int i = 0; while (i < MAX) { if (perm[i] == key) return(i); i++; } return(-1); O(1) O(n) O(1) O(n) O(1) O(n) O(1) O(1) O(1) ループの回数：平均時，最悪時とも O(n) ⇒　平均時間計算量，最大時間計算量とも O(n) 第7講 クイックソートとオーダー記法 平成19年11月2日

30 練習問題１ 以下の手続きのオーダーを求めよ 全体は O(1) + O(n) + O(1) = O(n)
void maxmin(int a[], int n) { int i, max, min; max = min = a[0]; for (i = 1; i < n - 1; i++)　{ if (max < a[i]) max = a[i]; if (min > a[i]) min = a[i]; } printf(“%d, %d\n”, max, min); O(1) 全体は O(1) + O(n) + O(1) = O(n) O(n) O(1)×O(n) = O(n) 第7講 クイックソートとオーダー記法 平成19年11月2日

31 練習問題２ 以下の手続きのオーダーを求めよ (ミニレポート) 全体は O(1) + O(n) + O(n) + O(1) = O(n)
void maxmin2(int a[], int n) { int i, max, min; max = min = a[0]; for (i = 1; i < n - 1; i++) if (max < a[i]) max = a[i]; if (min > a[i]) min = a[i]; printf(“%d, %d\n”, max, min); } O(1) 全体は O(1) + O(n) + O(n) + O(1) = O(n) O(n) O(1)×O(n) = O(n) 第7講 クイックソートとオーダー記法 平成19年11月2日

32 練習問題３ 以下の手続きのオーダーを求めよ (ミニレポート) 全体は O(n2) void bubble(int a[], int n) {
int i, j, t; for (i = 0; i < n - 1; i++) for (j = n - 1; j > i; j--) if (a[j – 1] > a[j]) { t = a[j]; a[j] = a[j – 1]; a[j – 1] = t; } O(n)×O(n) = O(n2) O(n) O(1)×O(n) = O(n) O(n) O(1) 第7講 クイックソートとオーダー記法 平成19年11月2日

33 オーダー評価：特殊ケース１ 条件分岐部の評価には要注意 if (x % 2 == 0) O( f (n) ) の処理 else 計算量は
O( g(n) ) の処理 計算量は O(max( f (n), g(n) )) if (x % 2 == 3) O( f (n) ) の処理 else O( g(n) ) の処理 計算量は O( g(n) ) 表現上の構造にとらわれず，実質的な振舞いの把握が必要 第7講 クイックソートとオーダー記法 平成19年11月2日

34 オーダ記法に用いる関数 ：n の多項式 ：n の指数関数 多項式時間アルゴリズム Polynomial Time Algorithm 現実的
指数時間アルゴリズム Exponential Time Algorithm 非現実的 第7講 クイックソートとオーダー記法 平成19年11月2日

35 多項式オーダーと指数オーダー 計算速度向上の効果 第7講 クイックソートとオーダー記法 平成19年11月2日

36 再帰アルゴリズム 処理手順が自身を用いて定義されているもの 自身の引数より小さな引数で自身を呼び出す 自明なケースの処理が存在
recursive (n) { if (自明なケース) { 自明なケースの処理 ; /* 終了条件 */ } else { recursive (m) ; /* m < n */ (処理) ; } 自身の引数より小さな引数で自身を呼び出す 自明なケースの処理が存在 表面的にループが出現しない 第7講 クイックソートとオーダー記法 平成19年11月2日

37 再帰プログラムの例: 階乗の計算 階乗 ヒント プログラム 例: 6! = 5×4×3×2×1
例: 6! = 5×4×3×2×1 ヒント 6!=6×5!，5!=5×4!，･･･，2!=2×1!，1!=1 プログラム ちょっとフロー チャートでは書けない int fact (int n) { int m; if(n = 1) return(1); else{ m = fact(n-1); return(n × m); } 第7講 クイックソートとオーダー記法 平成19年11月2日

38 再帰プログラムの概念 ちょっと分かりにくいので以下の図のように考えるとよい fact(4) = 24 6 2 return(4×6);
int fact (4) { m = fact(3); return(4 × m); } int fact (3) { m = fact(2); return(3 × m); } 6 2 int fact (2) { m = fact(1); return(2 × m); } return(4×6); return(3×2); fact(4) = 24 = 4×3×2×1 int fact (1) { return(1); } 1 return(2×1); 第7講 クイックソートとオーダー記法 平成19年11月2日

39 r=0 でないなら n と r の 最大公約数を求める
ユークリッドの互除法を再帰で書く ヒント r = 0 でないなら，m, n の最大公約数の代わりに n, r の最大公約数を求める int gcd (int m, int n) { int r; r = m % n; if(r = 0) return(n); else return( gcd(n,r) ); } r=0 なら n が 最大公約数 r=0 でないなら n と r の 最大公約数を求める 第7講 クイックソートとオーダー記法 平成19年11月2日

40 入力が n のときのこの再帰プログラムの計算量を Tn とする
オーダー評価：特殊ケース２ 再帰プログラムのオーダー評価は，少し面倒 int recursive(int n) { if (n <= 1) return(1); else return(recursive(n – 1) + recursive(n – 1)); } 入力が n のときのこの再帰プログラムの計算量を Tn とする この場合のステップ数は，漸化式 Tn = 2Tn-1 で与えられる ⇒　計算量は O(2n) (互除法は Tn = Tn-1 なので O(n)) 第7講 クイックソートとオーダー記法 平成19年11月2日

41 演習問題：マージソート 基本ステップと繰り返し に分類してみる 関数呼び出しがある 関数は別々に考える 関数の中身を見てみる
Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; 関数呼び出しがある 関数は別々に考える 関数の中身を見てみる 第7講 クイックソートとオーダー記法 平成19年11月2日

42 関数 Put は基本ステップ のみで構成 → O(1)
演習問題：マージソート メインの部分 Straight_Merge_Sort { seqsize ← 1 ; while (seqsize < n) { Merge_Seq(seqsize, a, b) ; Merge_Seq(2*seqsize, b, a) ; seqsize ← 4 * seqsize ; } Put (index) { into[k] ← from[index] ; index ← index + 1 ; k ← k + 1 ; 関数 Put は基本ステップ のみで構成 → O(1) 第7講 クイックソートとオーダー記法 平成19年11月2日

43 演習問題：マージソート O(1)だった よって繰り返しの 内部は全て O(1) Merge_Seq(size, from, into) {
start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; O(1)だった よって繰り返しの 内部は全て O(1) 第7講 クイックソートとオーダー記法 平成19年11月2日

44 i と j がそれぞれ iend, jend まで繰り返す
演習問題：マージソート 繰り返しの回数 を考えてみる Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; i の指す配列 3 6 7 2 4 5 8 10 j の指す配列 iend jend size i と j がそれぞれ iend, jend まで繰り返す i と j はどう増える？？ Put() とを見てみないとわからないな 第7講 クイックソートとオーダー記法 平成19年11月2日

45 Put(index) の中では ()内の値 index を 1 増やしている
演習問題：マージソート メインの部分 Straight_Merge_Sort { seqsize ← 1 ; while (seqsize < n) { Merge_Seq(seqsize, a, b) ; Merge_Seq(2*seqsize, b, a) ; seqsize ← 4 * seqsize ; } Put (index) { into[k] ← from[index] ; index ← index + 1 ; k ← k + 1 ; Put(index) の中では ()内の値 index を 1 増やしている Put(i) なら i を 1 増やす Put(j) なら j を 1 増やす 第7講 クイックソートとオーダー記法 平成19年11月2日

46 演習問題：マージソート 繰り返しの回数 を考えてみる i は start から start + size -1 まで
Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; i の指す配列 3 6 7 2 4 5 8 10 j の指す配列 iend jend size i は start から start + size -1 まで j は start + size から start + 2×size -1 まで つまり最大で 2×size 回まわる → O(size) 第7講 クイックソートとオーダー記法 平成19年11月2日

47 演習問題：マージソート 繰り返しの回数 を考えてみる それぞれ最大で size 回まわるけど， 各回では，どちらかしか回らない
Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; それぞれ最大で size 回まわるけど， 各回では，どちらかしか回らない これは上の繰り返しで余った分 iの列が余ったらwhile(i <= iend)で，jの列が余ったらwhile(j <= jend)で結果の列に追加するための繰り返し 第7講 クイックソートとオーダー記法 平成19年11月2日

48 演習問題：マージソート 繰り返しの回数 を考えてみる よく考えてみると，この繰り返し3つ合わせて，2×size回しか回らない！
Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; i の指す配列 3 6 7 2 4 5 8 10 j の指す配列 iend jend size よく考えてみると，この繰り返し3つ合わせて，2×size回しか回らない！ 繰り返し内部はO(1)なので，ここ全体でO(2×size)×O(1)=O(size) 第7講 クイックソートとオーダー記法 平成19年11月2日

49 演習問題：マージソート 繰り返しの回数 を考えてみる この繰り返しは何回まわる？？
Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; この繰り返しは何回まわる？？ start が 1 から 2×size ずつ増えていって n を超えるまで つまり，n/(2×size) 回 → O(n/(2size))=O(0.5n/size)= O(n/size) 第7講 クイックソートとオーダー記法 平成19年11月2日

50 演習問題：マージソート O(1) O(size) O(n/size) Merge_Seq(size, from, into) {
start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; O(size) O(1) O(n/size) 第7講 クイックソートとオーダー記法 平成19年11月2日

51 O(1)+O(size)+O(1)= O(size)
演習問題：マージソート Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; O(1) O(1)+O(size)+O(1)= O(size) O(n/size) 第7講 クイックソートとオーダー記法 平成19年11月2日

52 O(size)×O(n/size) = O(n)
演習問題：マージソート Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; O(1) O(size)×O(n/size) = O(n) 第7講 クイックソートとオーダー記法 平成19年11月2日

53 引数 size の値に関わらず O(n) となる
演習問題：マージソート Merge_Seq(size, from, into) { start ← 1 ; while (start < n) { i ← start ; j ← start + size ; k ← start ; iend ← min (start+size-1, n) ; jend ← min (start+2*size-1, n) ; while (i <= iend) and (j <= jend) { if (from[i] <= from[j]) { Put(i); } else { Put(j) ; } } while (i <= iend){ Put(i); } while (j <= jend) { Put(j); } start ← start+2*size; O(n)+O(1) = O(n) 引数 size の値に関わらず O(n) となる 第7講 クイックソートとオーダー記法 平成19年11月2日

54 演習問題：マージソート メインの部分 基本ステップと繰り返し に分類してみる Straight_Merge_Sort {
seqsize ← 1 ; while (seqsize < n) { Merge_Seq(seqsize, a, b) ; Merge_Seq(2*seqsize, b, a) ; seqsize ← 4 * seqsize ; } 基本ステップと繰り返し に分類してみる 関数Merge_Seq() の計算量はさっき求めた! 引数(括弧の中の値 seqsize)に関わらず O(n) 第7講 クイックソートとオーダー記法 平成19年11月2日

55 演習問題：マージソート さてこの繰り返しは何回まわる？？ メインの部分 Straight_Merge_Sort {
seqsize ← 1 ; while (seqsize < n) { Merge_Seq(seqsize, a, b) ; Merge_Seq(2*seqsize, b, a) ; seqsize ← 4 * seqsize ; } seqsize が1から繰り返し毎に4倍され n になるまで 1→4→42→43→･･･→4m=n m=log4n つまり O(log n) 回 第7講 クイックソートとオーダー記法 平成19年11月2日

56 演習問題：マージソート O(log n) メインの部分 Straight_Merge_Sort { seqsize ← 1 ;
while (seqsize < n) { Merge_Seq(seqsize, a, b) ; Merge_Seq(2*seqsize, b, a) ; seqsize ← 4 * seqsize ; } O(log n) O(1) O(n) 第7講 クイックソートとオーダー記法 平成19年11月2日

57 演習問題：マージソート O(log n) メインの部分 Straight_Merge_Sort { seqsize ← 1 ;
while (seqsize < n) { Merge_Seq(seqsize, a, b) ; Merge_Seq(2*seqsize, b, a) ; seqsize ← 4 * seqsize ; } O(1) O(n)+O(n)+O(1)= O(n) O(log n) 第7講 クイックソートとオーダー記法 平成19年11月2日

58 O(n)×O(log n) = O(n log n)
演習問題：マージソート メインの部分 Straight_Merge_Sort { seqsize ← 1 ; while (seqsize < n) { Merge_Seq(seqsize, a, b) ; Merge_Seq(2*seqsize, b, a) ; seqsize ← 4 * seqsize ; } O(1) O(n)×O(log n) = O(n log n) 第7講 クイックソートとオーダー記法 平成19年11月2日

59 O(n log n)+O(1) = O(n log n)
演習問題：マージソート メインの部分 Straight_Merge_Sort { seqsize ← 1 ; while (seqsize < n) { Merge_Seq(seqsize, a, b) ; Merge_Seq(2*seqsize, b, a) ; seqsize ← 4 * seqsize ; } O(n log n)+O(1) = O(n log n) マージソートのオーダーはO(n log n) 第7講 クイックソートとオーダー記法 平成19年11月2日

60 第7講のまとめ クイックソートの復習 オーダー記法の復習 第7講 クイックソートとオーダー記法 平成19年11月2日