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

Document