大阪電気通信大学 情報通信工学部 光システム工学科 2年次配当科目
コンピュータアルゴリズム
クイックソートと
オーダー記法
第12講: 平成20年12月18日 (金) 4限 E252教室
中村 嘉隆(なかむら よしたか)
奈良先端科学技術大学院大学 助教
[email protected]
http://narayama.naist.jp/~y-nakamr/
今日の講義の内容
整列アルゴリズム
クイックソートの復習
オーダー記法の復習
2009/12/18
第12講 クイックソートとオーダー記法
2
整列(ソーティング)問題とは
 ソーティング: Sorting,整列,並べ替え
 n 個のデータ列をある基準に従って順に並べ替える処理
 昇順ソート(Ascending Sort)
 単調増加に整列(小さいもの順に整列)
 一般的にソートといえばこちらを指す
 降順ソート(Descending Sort)
 単調減少に整列(大きいもの順に整列)
 昇順と降順は比較に用いる不等号を逆にする
 ソーティングにおける時間計算量は比較の回数を基
準として考える
 if 文を用いた大小比較
2009/12/18
第12講 クイックソートとオーダー記法
3
整列問題の分類
 安定性
 安定ソート
 ソートの際,同等なデータには元の並び順が保存されているソー
ト法
例) 元々学籍番号順に並んでいたデータをその成績順にソートしたとき,
同じ点数の生徒は学籍番号順に並んでいるようなソート法
 記憶領域
 外部ソート
 ソートの際,定数個より多くの外部記憶領域を必要とするソート法
例) 現在操作中の配列の他に,その長さに応じた別のデータ格納用の
配列が必要なソート法
 内部ソート
 ソートの際,定数個の記憶領域で十分なソート法
例)現在操作中の配列の内部の入れ替えだけで十分なソート法
2009/12/18
第12講 クイックソートとオーダー記法
4
準備
 入力は長さ n の数値の列
 {a1, a2, a3, a4, … , an} で表す
 数値の大小関係には推移律が成り立つ
 a < b で b < c なら a < c
 Swap 手続き
 配列中の 2 つの要素の値を入れ替える手続き
 実際には以下のようにテンポラリ(一時的)の変数を準備して入
れ替えする
swap (a, b) {
temp ← a ;
a ← b ;
b ← temp ;
}
2009/12/18
第12講 クイックソートとオーダー記法
5
クイックソート
クイックソート:Quick Sort
Charles A. R. Hoare が考案
内部ソートでは最も速いアルゴリズム
平均計算量:O(n log n)
2009/12/18
第12講 クイックソートとオーダー記法
6
クイックソート: 概要
 アルゴリズム
基準値 a* を選ぶ
基準値 a* 以下のデータを左側,残りを右側に分割
分割された 2 つの部分に同様の操作を,分割部分の
要素数が 1 になるまで繰り返す
 再帰アルゴリズムで実装(しない方法もある)
 分割統治法: Divide and Conquer
a*
a* 以下のデータ
2009/12/18
a* a* 以上のデータ
第12講 クイックソートとオーダー記法
7
クイックソート: 概念図
a* 以下のデータ
a* a* 以上のデータ
x < b* b*
a* x < c* c* c* < x
d*
b*
b* > x
e*
a*
f*
c*
g*
整列済みデータ
2009/12/18
第12講 クイックソートとオーダー記法
8
クイックソート: partition 手続き
 基準値(ピボット)によってデータを 2 つの部分に分割
 partition( a* , left , right )
 手順
 基準値を a[right] とする(簡単のため)
 左から走査し基準値より大きい要素を探索: 位置 i
 右から走査し基準値より小さい要素を探索: 位置 j
 両者の位置関係が i < j ならば交換
 i ≧ j となるまで繰り返す
a[left]
2009/12/18
a[right]
第12講 クイックソートとオーダー記法
9
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
8 5
i
7
9
2
6
3 10 4
j
1
3
5
i
7
9
2
j
6
8 10 4
1
3
2 7
j i
9
5
6
8 10 4
1
2009/12/18
3
2
4 9
i
5
6
1
j
4
8 10 7
第12講 クイックソートとオーダー記法
a* < 6 なので
飛ばす
どんどん飛ばして
最後は a* と交換
10
クイックソート: partition 手続き
a*
10 8
5
7
9
2
6
3
1
4
右端の値 a[right] を
a* として採用
2009/12/18
第12講 クイックソートとオーダー記法
11
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
4
a[i] > a* なる i を探索
たまたま 1 つ目で当たる
2009/12/18
第12講 クイックソートとオーダー記法
12
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
j
4
a[j] < a* なる j を探索
またもや 1 つ目で当たる
2009/12/18
第12講 クイックソートとオーダー記法
13
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
5
7
9
2
6
3 10 4
8
1
j
4
というわけで交換
2009/12/18
第12講 クイックソートとオーダー記法
14
クイックソート: partition 手続き
a*
10 8
i
1
5
7
9
2
6
3
1
j
4
8 5
i
7
9
2
6
3 10 4
a[i] > a* なる i を探索
次から探していることに注意
2009/12/18
第12講 クイックソートとオーダー記法
15
クイックソート: partition 手続き
a*
10 8
i
1
5
7
9
2
6
3
1
j
4
8 5
i
7
9
2
6
3 10 4
j
a[j] < a* なる j を探索
こちらも同様
2009/12/18
第12講 クイックソートとオーダー記法
16
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
8 5
i
7
9
2
6
3 10 4
j
1
3
7
9
2
6
8 10 4
5
1
j
4
見つかったので交換
2009/12/18
第12講 クイックソートとオーダー記法
17
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
8 5
i
7
9
2
6
3 10 4
j
1
3
7
9
2
6
8 10 4
5
i
1
j
4
a[i] > a* なる i を探索
2009/12/18
第12講 クイックソートとオーダー記法
18
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
8 5
i
7
9
2
6
3 10 4
j
1
3
7
9
2
6
j
8 10 4
5
i
1
j
4
a[j] < a* なる j を探索
これは条件に当てはまらない
2009/12/18
第12講 クイックソートとオーダー記法
19
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
8 5
i
7
9
2
6
3 10 4
j
1
3
7
9
2
j
6
8 10 4
5
i
ただし終了条件に注意
2009/12/18
1
j
4
見つかるまでずらす
ここで見つかった
第12講 クイックソートとオーダー記法
20
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
j
4
1
8 5
i
7
9
2
6
3 10 4
j
1
3
5
i
7
9
2
j
6
8 10 4
1
3
2
7
9
5
6
8 10 4
交換
2009/12/18
第12講 クイックソートとオーダー記法
21
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
j
4
1
8 5
i
7
9
2
6
3 10 4
j
1
3
5
i
7
9
2
j
6
8 10 4
1
3
2
7
i
9
5
6
8 10 4
a[i] > a* なる i を探索
2009/12/18
第12講 クイックソートとオーダー記法
22
クイックソート: partition 手続き
a*
10 8
i
5
7
9
2
6
3
1
8 5
i
7
9
2
6
3 10 4
j
1
3
5
i
7
9
2
j
6
8 10 4
1
3
2 7
j i
9
5
6
8 10 4
最後まで見つから
ないこともある!
2009/12/18
1
j
4
a[j] < a* なる j を探索
見つかったけれど j < i
第12講 クイックソートとオーダー記法
23
クイックソート: partition 手続き
a*
10 8
i
2009/12/18
5
7
9
2
6
3
1
8 5
i
7
9
2
6
3 10 4
j
1
3
7
9
2
j
6
8 10 4
9
5
6
8 10 4
4 9
i
5
6
8 10 7
5
i
1
3
2 7
j i
1
3
2
1
j
4
分割完了!
第12講 クイックソートとオーダー記法
最後なので
a* と交換
24
クイックソート
1
3
2
4
9
5
6
8 10 7
左右で再帰的に
クイックソートを行う
左
1
3
2
4
9
5
6
8 10 7
1
2
3
4
9
5
6
8 10 7
1
2
3
4
9
5
6
8 10 7
4
9
5
6
8 10 7
9
5
6
8 10 7
まず左から
左
再帰はスタックを
利用することに注意!
さらに左から
左
右
1
2
3
右
1
2
3
4
といっても長さが 1 なの
で即座に終了
右
1
2009/12/18
2
3
4
9
5
6
8 10 7
第12講 クイックソートとオーダー記法
即座終了が発生
したらやっと右
25
何故こんなややこしい交換をするのか
 内部ソートにするため
 外部ソートにしていいなら,もう少し簡単
基準値より大きいか小さいかで 2 つの
配列を用意し,前から順番に振り分ける
a*
小の配列,基準値,大の配列
10 8 5 7 9 2 6 3 1 4
の順でつなぎ合わせる
基準値より小さい値用配列
2
3
1
基準値より大きい値用配列
10 8
2009/12/18
5
7
9
6
2
3
1
4 10 8
5
7
9
6
• 外部に長さ n に比例した記憶
領域が必要(マージソートと同
じ欠点)
第12講 クイックソートとオーダー記法
26
クイックソート: 計算量
 最良の場合
基準値によって左側の列と右側の列が半分に別れて
いくとき
再帰の繰り返しは log n 回
全体は O(n log n)
 最悪の場合
基準値が最大値,または最小値のとき
列の大きさが 1 つずつしか減っていかない
再帰の繰り返しは n 回
全体は O(n2)
2009/12/18
第12講 クイックソートとオーダー記法
27
クイックソート: 高速化の知恵
基準値(ピボット)の選び方
今までは右端の値(a[right])を基準値にした
が,三数値を取って(a[left],
a[(left+right)/2],a[right]),その真
ん中の値を基準値 a* に採用
こうすると最悪の状況になる可能性が小さくなる
規模が小さい等,クイックサーチが不適である
ことがわかれば挿入法にスイッチ(そのほうが
早い)
2009/12/18
第12講 クイックソートとオーダー記法
28
クイックソートのまとめ
 平均計算量 O(n log n)
 最悪計算量 O(n2)
 安定ソートではない
 整列されていない列でのデータの入れ替えでは元の順番
が保存されない
 内部ソート
 外部記憶を必要としない
 最悪計算量は悪いが,実際の使用状況では最速の
ソーティングアルゴリズム (マージソートより速い)
 さまざまなところで使用されている
2009/12/18
第12講 クイックソートとオーダー記法
29
整列問題の計算量の下限
いままで勉強した整列アルゴリズム
大きく分けて O(n2) のアルゴリズムと O(n log n)
のアルゴリズム
O(n log n) より早いアルゴリズムはあるか?
ないなら,既に2つの O(n log n) のアルゴリズム
(マージソートとクイックソート)は勉強したので問
題ない
あるなら,最も早いアルゴリズムも勉強せねばなら
ない・・・・というか知りたいよね?
2009/12/18
第12講 クイックソートとオーダー記法
30
整列問題の計算量の下限の証明
 並べ替える問題=元の要素を適切に置き換える問題
 配列の添字を並べ替えて,配列の内容を整列させる
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
10 8
5
7
9
2
6
3
1
4
[8] [5] [7] [9] [2] [6] [3] [1] [4] [0]
1
2
3
4
5
6
7
8
9 10
 添字の並べ方は 10×9×8×…×2×1=10! 通り
 つまり n! 通り(n の階乗)の組合せのうち,正解は 1 通り
 ここで,n! = O(nn) であることがわかっている
2009/12/18
第12講 クイックソートとオーダー記法
31
整列問題の計算量の下限の証明
 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)
2009/12/18
第12講 クイックソートとオーダー記法
32
アルゴリズムのオーダー
 f (n) のオーダーである:O( f (n) ) と書く
ある正定数 c , n0 が存在し,n0 < n である n に
対して常に g(n) < c・f (n) が成立するなら
g(n) = O( f(n) ) である
実行時間が関数 f(n) の増加率を超えない
係数は考えない
(c はいくらでも良
い)
2009/12/18
n0
c・f (n)
実際の計算量 g (n)
n
第12講 クイックソートとオーダー記法
33
オーダーの見積もり
 計算量のオーダー表現:
 きわめて大雑把な評価尺度
 大雑把な見積もりで導出することができる
1. アルゴリズムを小さな操作単位に分割
2. 各操作単位のオーダーを評価
3. 操作単位のオーダーを合成して,全体の
オーダーを得る
2009/12/18
第12講 クイックソートとオーダー記法
34
アルゴリズムの分割
search(key) /* 配列 perm の中から値 key の位置を探す */
int
key;
{
int
i = 0;
while (i < MAX) {
if (perm[i] == key)
return(i);
i++;
}
return(-1);
}
実行時間が入力サイズに依存しないステップ
(基本ステップ)
ループ回数が入力サイズに依存するループ構造
2009/10/9
オーダーの評価 (1)
 ルール 1:基本ステップのオーダーは O(1)
 基本ステップ
 実行時間が入力サイズに依存しないステップ
 変数への代入
 数値の演算
 ポインタ操作 etc.
 一般に,以下は基本ステップでないことに注意
 (入力サイズに依存した)配列のコピー
 関数呼び出し
2009/10/9
オーダーの評価 (2)
ルール 2: 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
2009/10/9
オーダーの評価 (3)
ルール 3: O(f(n)) 回だけまわるループの内
部で O(g(n)) の操作を実行する場合,全体の
オーダーは O(f(n) × g(n))
O(f(n)) 回ループ
O(g(n))
O(f(n) × g(n))
係数は無視してよい
最高次の項以外は無視してよい
2009/10/9
ポイント (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 倍にすれば
問題ない
係数と増加率は関係ない(係数大きくしても関数の増
加率は変わらない)
2009/12/18
第12講 クイックソートとオーダー記法
39
ポイント (2/3)
次数の大きい項だけ残す
n2+n → n2,n3+100n2 → n3,
n + n log n → n log n
足し算すると次数の低い項は消える
-5
-25
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 は無視できる
2009/12/18
無限に大きな n を考えてみよう
(例えば n = 100000000000000000000000000)
そうすれば -5 も -25 もほとんど増加率的には無意味
第12講 クイックソートとオーダー記法
40
ポイント (2/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
つずつ外していけばやさしい
2009/12/18
第12講 クイックソートとオーダー記法
41
オーダー評価の例
search(key) /* 配列 perm の中から値 key の位置を探す */
int
key;
{
int
i = 0;
O(1)
while (i < MAX) {
if (perm[i] == key)
return(i);
i++;
}
return(-1);
}
O(n)
O(1)
O(1)
O(1)
O(1)
O(n)
O(1)
ループの回数: 平均時,最悪時とも O(n)
⇒ 平均時間計算量,最大時間計算量とも O(n)
2009/10/9
O(n)
練習問題 1
以下の手続きのオーダーを求めよ
void maxmin(int a[], int n)
{
int i, max, min;
max = min =
for (i = 1;
if (max <
if (min >
}
printf(“%d,
}
a[0];
O(1)
i < n - 1; i++) {
O(n)
a[i]) max = a[i]; O(1)
a[i]) min = a[i]; O(1)
%d\n”, max, min); O(1)
全体は O(1) + O(n) + O(1) = O(n)
2009/10/9
O(1)×O(n) = O(n)
練習問題 2
以下の手続きのオーダーを求めよ
void maxmin2(int a[], int n)
{
int i, max, min;
max = min =
for (i = 1;
if (max <
for (i = 1;
if (min >
printf(“%d,
}
a[0];
i < n - 1; i++)
a[i]) max = a[i];
i < n - 1; i++)
a[i]) min = a[i];
%d\n”, max, min);
O(1)
O(n)
O(1)
O(n)
O(1)
O(1)
全体は O(1) + O(n) + O(n) + O(1) = O(n)
2009/10/9
O(1)×O(n) = O(n)
O(1)×O(n) = O(n)
練習問題 3
以下の手続きのオーダーを求めよ
void bubble(int a[], int n)
{
int i, j, t;
O(n)×O(n) = O(n2)
O(n)
O(1)×O(n) = O(n)
for (i = 0; i < n - 1; i++)
for (j = n - 1; j > i; j--)
O(n)
if (a[j – 1] > a[j]) {
t = a[j]; a[j] = a[j – 1]; a[j – 1] = t; O(1)
}
}
全体は O(n2)
2009/10/9
オーダー評価:特殊ケース 1
条件分岐部の評価には要注意
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))
表現上の構造にとらわれず,実質的な振舞いの把握が必要
2009/10/9
オーダー記法に用いる関数
 n,nlogn,n2,n3
: n の多項式
多項式時間アルゴリズム
Polynomial Time Algorithm
現実的
 2n,n!,nn
: n の指数関数
指数時間アルゴリズム
Exponential Time Algorithm
非現実的
2009/10/9
多項式オーダーと指数オーダー
計算速度向上の効果
2009/10/9
再帰アルゴリズム
 処理手順が自身を用いて定義されているもの
recursive (n) {
if (自明なケース) {
自明なケースの処理 ; /* 終了条件 */
} else {
recursive (m) ; /* m < n */
(処理) ;
}
}
自身の引数より小さな引数で自身を呼び出す
自明なケースの処理が存在
表面的にループが出現しない
2009/10/9
再帰プログラムの例: 階乗の計算
 階乗
 例: 6! = 5×4×3×2×1
 ヒント
 6! = 6×5!,5! = 5×4!,・・・,2! = 2×1!,1! = 1
 プログラム
2009/10/9
int fact (int n)
{
int m;
if(n = 1)
return(1);
else{
m = fact(n-1);
return(n × m);
}
}
ちょっとフローチャー
トでは書けない
再帰プログラムの概念
ちょっと分かりにくいので以下の図のように考
えるとよい
int fact (4)
{ 6
m = fact(3);
return(4 × m);
} return(4×6);
int fact (3)
{
2
m = fact(2);
return(3 × m);
}
return(3×2);
fact(4)
int fact (1)
{
return(1);
= 4×3×2×1
}
= 24
2009/10/9
int fact (2)
{
1
m = fact(1);
return(2 × m);
}
return(2×1);
ユークリッドの互除法を再帰で書く
ヒント
r = 0 でないなら,m,n の最大公約数の代わり
に n,r の最大公約数を求める
int gcd (int m, int n)
{
int r;
r = m % n;
r=0 なら n が 最大公約数
if(r = 0)
return(n);
r=0 でないなら n と r の 最
else
大公約数を求める
return( gcd(n,r) );
}
2009/10/9
オーダー評価:特殊ケース 2
再帰プログラムのオーダー評価は,少し面倒
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))
2009/10/9
演習問題: マージソート
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;
}
}
2009/12/18
第12講 クイックソートとオーダー記法
54
演習問題: マージソート
メインの部分
Straight_Merge_Sort {
seqsize ← 1 ;
while (seqsize < n) {
Merge_Seq(seqsize, a, b) ;
Merge_Seq(2*seqsize, b, a) ;
seqsize ← 4 * seqsize ;
}
}
関数 Put は基本ステップ
のみで構成 → O(1)
Put (index) {
into[k] ← from[index] ;
index ← index + 1 ; k ← k + 1 ;
}
2009/12/18
第12講 クイックソートとオーダー記法
55
演習問題: マージソート
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){
O(1)だった
Put(i); }
while (j <= jend) {
Put(j); }
よって繰り返しの
start ← start+2*size;
}
内部は全て
}
O(1)
2009/12/18
第12講 クイックソートとオーダー記法
56
演習問題: マージソート
Merge_Seq(size, from, into) {
繰り返しの回数
start ← 1 ;
を考えてみる
while (start < n) {
i ← start ; j ← start + size ; k ← start ;
i の指す配列
iend ← min (start+size-1, n) ;
3 6 7 10
jend ← min (start+2*size-1, n) ;
iend
while (i <= iend) and (j <= jend) {
j の指す配列
if (from[i] <= from[j]) { Put(i); }
else { Put(j) ; }
2 4 5 8
jend
}
while (i <= iend){
size
Put(i); }
while (j <= jend) {
i と j がそれぞれ iend, jend まで繰り返す
Put(j); }
i と j はどう増える??
start ← start+2*size;
}
}
Put() を見てみないとわからないな
2009/12/18
第12講 クイックソートとオーダー記法
57
演習問題: マージソート
メインの部分
Straight_Merge_Sort {
seqsize ← 1 ;
while (seqsize < n) {
Merge_Seq(seqsize, a, b) ;
Merge_Seq(2*seqsize, b, a) ;
seqsize ← 4 * Put(index)
seqsize ; の中では () 内の値
index を 1 増やしている
}
Put(i) なら i を 1 増やす
}
Put(j) なら j を 1 増やす
Put (index) {
into[k] ← from[index] ;
index ← index + 1 ; k ← k + 1 ;
}
2009/12/18
第12講 クイックソートとオーダー記法
58
演習問題: マージソート
Merge_Seq(size, from, into) {
繰り返しの回数
start ← 1 ;
を考えてみる
while (start < n) {
i ← start ; j ← start + size ; k ← start ;
i の指す配列
iend ← min (start+size-1, n) ;
3 6 7 10
jend ← min (start+2*size-1, n) ;
iend
while (i <= iend) and (j <= jend) {
j の指す配列
if (from[i] <= from[j]) { Put(i); }
else { Put(j) ; }
2 4 5 8
jend
}
while (i <= iend){
size
Put(i); }
i は(jstart
から{ start + size -1 まで
while
<= jend)
Put(j);
j は start
+ }size から start + 2×size -1 まで
start ← start+2*size;
}
}
つまり最大で 2×size 回まわる →
O(size)
2009/12/18
第12講 クイックソートとオーダー記法
59
演習問題: マージソート
Merge_Seq(size, from, into) {
繰り返しの回数
start ← 1 ;
を考えてみる
while (start < n) {
i ← start ; j ← start + size ; k ← start ;
i の指す配列
それぞれ最大で
size
回まわるけど,
iend ← min (start+size-1, n) ;
3 6 7 10
jend ← min (start+2*size-1,
n)
;
各回では,どちらかしか回らない
iend
while (i <= iend) and (j <= jend) {
j の指す配列
if (from[i] <= from[j]) { Put(i); }
else { Put(j) ; }
2 4 5 8
jend
}
while (i <= iend){
size
Put(i); }
while (j <= jend) {
Put(j); }
start ← start+2*size;
これは上の繰り返しで余った分
}
} i の列が余ったら while(i <= iend) で,j の列が余った
ら while(j <= jend)
で結果の列に追加するための繰り返
第12講 クイックソートとオーダー記法
60
2009/12/18
演習問題: マージソート
Merge_Seq(size, from, into) {
繰り返しの回数
start ← 1 ;
を考えてみる
while (start < n) {
i ← start ; j ← start + size ; k ← start ;
i の指す配列
iend ← min (start+size-1, n) ;
3 6 7 10
jend ← min (start+2*size-1, n) ;
iend
while (i <= iend) and (j <= jend) {
j の指す配列
if (from[i] <= from[j]) { Put(i); }
else { Put(j) ; }
2 4 5 8
jend
}
while (i <= iend){
size
Put(i); }
よく考えてみると,この繰り返し 3 つ合わせ
while (j <= jend) {
て,2×size 回しか回らない!
Put(j); }
start ← start+2*size;
繰り返し内部は O(1) なので,ここ全体で
}
}
O(2×size)×O(1)=O(size)
2009/12/18
第12講 クイックソートとオーダー記法
61
演習問題: マージソート
Merge_Seq(size, from, into) {
繰り返しの回数
start ← 1 ;
を考えてみる
while (start < n) {
i ← start ; j ← start + size ; k ← start ;
i の指す配列
iend ← min (start+size-1, n) ;
3 6 7 10
この繰り返しは
jend ← min (start+2*size-1, n) ;
iend
何回まわ
while (i <= iend) and (j <= jend) {
j の指す配列
if (from[i] <= from[j]) { Put(i); }
る??
else { Put(j) ; }
2 4 5 8
jend
}
while (i <= iend){
start が 1 から 2×sizesize
ずつ
Put(i); }
増えていって n を超えるまで
while (j <= jend) {
Put(j); }
つまり,n/(2×size) 回
start ← start+2*size;
→ O(n/(2size))=O(0.5n/size)=
}
}
O(n/size)
2009/12/18
第12講 クイックソートとオーダー記法
62
演習問題: マージソート
Merge_Seq(size, from, into) {
start ← 1 ;
O(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(n/size)
2009/12/18
第12講 クイックソートとオーダー記法
63
演習問題: マージソート
Merge_Seq(size, from, into) {
start ← 1 ;
O(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(1)=
O(size)
O(n/size)
2009/12/18
第12講 クイックソートとオーダー記法
64
演習問題: マージソート
Merge_Seq(size, from, into) {
start ← 1 ;
O(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(n/size) =
O(n)
2009/12/18
第12講 クイックソートとオーダー記法
65
演習問題: マージソート
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); }
引数 size
の
else { Put(j) ; }
}
値に関わらず
while (i <= iend){
O(n) となる
Put(i); }
while (j <= jend) {
Put(j); }
start ← start+2*size;
}
}
O(n)+O(1) =
O(n)
2009/12/18
第12講 クイックソートとオーダー記法
66
演習問題: マージソート
メインの部分
基本ステップと繰り返し
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)
2009/12/18
第12講 クイックソートとオーダー記法
67
演習問題: マージソート
さてこの繰り返しは何
メインの部分
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 つまり
2009/12/18
O(log n) 回
第12講 クイックソートとオーダー記法
68
演習問題: マージソート
メインの部分
Straight_Merge_Sort {
seqsize ← 1 ;O(1)
while (seqsize < n) {
O(n)
Merge_Seq(seqsize,
a, b) ;
O(n)
Merge_Seq(2*seqsize,
b, a) ;
seqsize ← 4 O(1)
* seqsize ;
O(log n)
}
}
2009/12/18
第12講 クイックソートとオーダー記法
69
演習問題: マージソート
メインの部分
Straight_Merge_Sort {
seqsize ← 1 ;O(1)
while (seqsize < n) {
Merge_Seq(seqsize, a, b) ;
O(n)+O(n)+O(1)=
Merge_Seq(2*seqsize, b, a) ;
seqsize ←
O(n)
4 * seqsize
}
;
O(log n)
}
2009/12/18
第12講 クイックソートとオーダー記法
70
演習問題: マージソート
メインの部分
Straight_Merge_Sort {
seqsize ← 1 ;O(1)
while (seqsize < n) {
Merge_Seq(seqsize, a, b) ;
O(n)×O(log n) =
Merge_Seq(2*seqsize, b, a) ;
seqsize ←
O(n
log
n)
4 * seqsize ;
}
}
2009/12/18
第12講 クイックソートとオーダー記法
71
演習問題: マージソート
メインの部分
Straight_Merge_Sort {
seqsize ← 1 ;
while (seqsize < n) {
O(n log n)+O(1) =
Merge_Seq(seqsize, a, b) ;
O(n log n)
Merge_Seq(2*seqsize, b, a) ;
seqsize ← 4 * seqsize ;
}
}
2009/12/18
マージソートのオーダーは O(n log n)
第12講 クイックソートとオーダー記法
72
第12講のまとめ
クイックソートの復習
オーダー記法の復習
2009/12/18
第12講 クイックソートとオーダー記法
73
今後の予定
2010/1/8
復習その 2
探索木など
2010/1/15
模擬試験
2010/1/29
試験
持ち込み:自筆ノート・ミニレポート,講義資料は持ち込
み不可!
2009/12/18
第12講 クイックソートとオーダー記法
74
ダウンロード

クイックソートと オーダー記法