ALG2010-03

情報工学概論
(アルゴリズムとデータ構造)
第3回
今までのソーティングアルゴリズム
1. 挿入ソート： (n2) 時間だが，入力サイズが
小さいときには高速．in-place
2. マージソート： (n lg n) 時間だが，実行に
は一時的な配列が必要
2
新しいソーティングアルゴリズム
1. ヒープソート： (n lg n) 時間, in-place.
2. クイックソート：最悪 (n2) 時間だが平均実行
時間は(n lg n)．実際上は高速．in-place.
3
クイックソート
• n 個の数に対して最悪実行時間(n2)のソー
ティングアルゴリズム
• 平均実行時間は(n log n)
• 記法に隠された定数も小さい
• in-place (一時的な配列が必要ない)
4
クイックソートの記述
• 分割統治法に基づく
• 部分配列 A[p..r] のソーティング
1. 部分問題への分割:
– 配列 A[p..r] を2つの部分配列 A[p..q] と
A[q+1..r] に再配置する．
– A[p..q] のどの要素も A[q+1..r] の要素以下にする．
– 添字 q はこの分割手続きの中で計算する．
2. 部分問題の解決 (統治):
•
部分配列 A[p..q] と A[q+1..r] を再帰的にソート
3. 部分問題の統合
•
A[p..r] はすでにソートされているので何もしない
5
クイックソートのコード
void QUICKSORT(data *A, int p, int r)
{
int q;
if (p < r) {
q = PARTITION(A,p,r);
QUICKSORT(A,p,q);
QUICKSORT(A,q+1,r);
}
}
main()
{
QUICKSORT(A,0,n-1);
}
6
注：これはin-placeではない
def quick_sort(a)
（一時的に余分な記憶領域が必要）
n = a.length
if n <= 1 then
return a
else
pivot = a[0]
less = a.select{|x| x < pivot}
equal = a.select{|x| x == pivot}
greater = a.select{|x| x > pivot}
return quick_sort(less) + equal + quick_sort(greater)
end
end
a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0]
b = quick_sort(a)
pb
7
配列の分割
int PARTITION(data *A, int p, int r) // O(n) 時間
{
int q, i, j;
data x, tmp;
x = A[p];
i = p-1; j = r+1;
while (1) {
do {j = j-1;} while (A[j] > x);
do {i = i+1;} while (A[i] < x);
if (i < j) {
tmp = A[i]; A[i] = A[j]; A[j] = tmp;
} else {
return j;
}
}
}
8
A[p..r]
5 3 2 6 4 1 3 7
i
j
5 3 2 6 4 1 3 7
i
A[i]  x
A[j]  x となる最初の i, j
7 は正しい分割位置にある
j
3 3 2 6 4 1 5 7
i
初期状態：
i と j は配列の範囲外
x = A[p] = 5 によって分割
x: 枢軸 (pivot) と呼ぶ
j
A[i] と A[j] を交換
正しい分割位置になる
9
3 3 2 6 4 1 5 7
i
j
3 3 2 1 4 6 5 7
i
A[i]  x
A[j]  x となる最初の i, j
A[i] と A[j] を交換
j
3 3 2 1 4 6 5 7
j i
i  j となったので
q = j を返す
A[p..q] は x 以下
A[q+1..r] は x 以上
10
PARTITIONの正当性
• PARTITIONの返り値を q とする
• A[p..r] の分割後に満たされるべき条件
– A[p..q] はある pivot x 以下
– A[q+1..r] は x 以上
–pq<r
• q = r となると，QUICKSORTは停止しないため，
どんな A に対しても q < r となることを保障する
必要がある
11
• 初期状態は i < j
• do {j = j-1;} while (A[j] > x);
do {i = i+1;} while (A[i] < x); の終了後
– p  i, j  r
– A[j+1..r] は x 以上
– A[p..i-1] は x 以下
– A[i]  x  A[j]
• i < j のとき，A[i] と A[j] を交換すると
– A[j..r] は x 以上
– A[p..i] は x 以下
• i  j のとき q = j
12
• PARTITIONの終了時に q = j = r とする
– while (1) のループを実行する毎に j は1以上減る
– 終了時に j = r ならばこのループは1度しか実行され
ていない
– しかし1回目のループでは x = A[p] なので i = p
• PARTITIONは p < r の場合のみ呼ばれるので，
1回目のループでは p = i < j = r
• つまり1回目のループでは終了しない
• よってPARTITION終了時に q = r とはならない．
つまり q < r
13
8.2 クイックソートの性能
• クイックソートの実行時間は分割が平均化さ
れているかどうかに依存
• これはpivotの選択に依存
• 分割が平均化されていれば実行時間は漸近
的にマージソートと同じ ((n log n))
• 最悪時は (n2)
14
最悪の分割
• 最悪の場合は，PARTITIONによって領域が
1 要素と n-1 要素に分けられる場合
• 分割には (n) 時間かかる
• 実行時間に対する漸化式は
– T(n) = T(n1) + (n), T(1) = (1)
• T(n) = (n2)
• 最悪実行時間は挿入ソートと同じ
• 入力が完全にソートされているときに起こる
(挿入ソートなら O(n) 時間)
15
n
n
n 1
1
n 1
n2
1
1
n
n
n2
n 3

3
2
2
1
再帰木
1
 
Total :  n
2
16
最良の分割
• クイックソートが最も速く動作するのは，
PARTITIONによってサイズ n/2 の2つの領域
に分割されるとき.
• T(n) = 2T(n/2) + (n)
• T(n) = (n lg n)
• ちょうど半分に分割される場合が最速
17
n
n
n
2
n
2
n
4
n
4
n
4
n
n
4
n
lg n
n n n n n n n n
8 8 8 8 8 8 8 8
n

n
Total : nlg n
18
平衡分割
• PARTITIONで常に 9 対 1 の比で分割されると
仮定する
• T(n) = T(9n/10) + T(n/10) + (n)
• 再帰木の各レベルのコストは O(n)
• 再帰の深さは log 109 n  lg n 
• 漸近的には中央で分割するのと同じ
• 分割の比が 99 対 1 でも同じ (定数比なら良
い)
19
8.3 クイックソートの
確率的アルゴリズム
• クイックソートの平均的な場合の実行時間を解析
する場合，入力の頻度を仮定する必要がある．
• 通常は，すべての順列が等確率で現れると仮定
• しかし実際にはこの仮定は必ずしも期待できない
• この仮定が成り立たなくてもうまく動作するクイック
ソートの確率的アルゴリズムを示す
20
確率的 (randomized) アルゴリズム
• 動作が入力だけでなく乱数発生器 (randomnumber generator)に依存するアルゴリズム
• 関数 RANDOM(a,b): a 以上 b 以下の整数を
等確率で返すとする．
• プログラミング言語は擬似乱数発生器
(pseudorandom-number generator) を備え
る
• 擬似乱数: 統計的にはランダムに見えるが，
決定的に作られる数(の列)
21
確率的アルゴリズム1
• クイックソートを行う前に入力配列の要素をラン
ダムに並び替える
• 実行時間は入力順序に依存しなくなる
• アルゴリズムがうまく動作しないのは，乱数発生
器によって運の悪い順列を作る場合のみ
• 最悪の実行時間は改善されない ((n2))
• 最悪の場合はほとんど起きない
22
確率的アルゴリズム2
• 配列を A[p..r] を分割する前に， A[p] と
A[p..r] からランダムに選んだ要素を交換
• pivotが rp+1 個の要素から等確率で選ばれ
ることを保障する
• 分割が平均的にはバランスのとれたものにな
ることが期待できる
23
int RANDOMIZED_PARTITION(data *A, int p, int r)
{
int i;
data tmp;
i = RANDOM(p,r);
tmp = A[i]; A[i] = A[p]; A[p] = tmp; // 値の交換
return PARTITION(A,p,r);
}
void RANDOMIZED_QUICKSORT(data *A, int p, int r)
{
int q;
if (p < r) {
q = RANDOMIZED_PARTITION(A,p,r);
RANDOMIZED_QUICKSORT(A,p,q);
RANDOMIZED_QUICKSORT(A,q+1,r);
}
}
24
8.4.1 最悪の場合の解析
• T(n): サイズ n の入力に対するQUICKSORT
の最悪実行時間
T (n)  max T (q)  T (n  q)  (n)
1 q n 1
• T(n) = O(n2) を示す
• m < n に対し T(m)  cm2 と仮定
25
T (n)  max T (q)  T (n  q )   (n)
1 q  n 1


 c  max q  (n  q)  (n)
2
2
1 q  n 1


 c  1  (n  1)  (n)
2
2
 cn  2c(n  1)  (n)
2
 cn
2
c は 2c(n1) が (n) の項よりも大きくなるように
十分大きくとる
よって T(n) = O(n2) が示された
26
8.4.2 平均的な場合の解析
• T(n): サイズ n の入力に対するRANDOMIZED
QUICKSORTの平均実行時間
• T(n) に関する漸化式を解く
• 入力データはすべて異なる数とする
27
分割の解析
• RANDOMIZED_PARTITIONでPARTITIONが呼
ばれるとき，A[p] の要素は A[p..r] のランダムな
要素と置き換えられている．
• 観察：PARTITIONによって返される q の値は
A[p..r] の中での x = A[p] のランクのみに依存
• x のランク rank(x) = 集合中の x 以下の要素数
• 要素数 n = rp+1
• rank(x) = i となる確率は 1/n
28
• rank(x) = 1 のとき，PARTITIONでのループは
i = j = p で終了
• このとき q = j = p つまり分割の小さい方のサ
イズは 1．この事象が起きる確率は 1/n
• rank(x)  2 のとき，x = A[p] より小さい値が少
なくとも1つ存在
• PARTITIONでの最初のループ実行後は
i = p，j > p
• A[i] と A[j] を入れ替えるため，x = A[p] は右
の分割に入る
29
• PARTITIONが停止したとき，左の分割には
rank(x)1 個の要素があり，それらは x より小さい
• rank(x)  2 のとき，左の分割のサイズが i である
確率は 1/n (i = 1,2,...,n-1)
• rank(x) が1の場合と2以上の場合を合わせると，
• 左の分割のサイズ rp+1 が
– 1 になる確率: 2/n
– i になる確率: 1/n (i = 2,3,...,n-1)
30
平均時に対する漸化式
• T(n): n 要素の入力配列をソートするのに必要
な平均時間
• T(1) = (1)
• 長さ n の配列に対してソートする場合
– 配列の分割: (n) 時間
– 統治: 長さ q と nq の部分配列を再帰的にソート
n 1

1
T (n)   T (1)  T (n  1)   (T (q)  T (n  q))   (n)
n
q 1

31
T(1)=(1), T(n1) = O(n2) より

1
1
T (1)  T (n  1)  (1)  O(n 2 )
n
n
 O(n)

よって T(n) は次のように書ける
1 n 1
T (n)   (T (q )  T (n  q ))  (n)
n q 1
2 n 1
  T ( k )  ( n )
n k 1
32
m < n に対し T(m)  am lg m + b (a>0, b>0) と仮定
2 n 1
T ( n )   T ( k )  ( n )
n k 1
2 n 1
  (ak lg k  b)  (n)
n k 1
2a n 1
2b

k lg k  (n  1)  (n)

n k 1
n
n 1
1 2
1 2
k lg k  n lg n  n を用いる

2
8
k 1
a
n が (n)+b 以上になるように a を選ぶと
4
33
2a  1 2
1 2  2b
T ( n) 
 n lg n  n   (n  1)  (n)
n 2
8  n
a
 an lg n  n  2b  (n)
4
a 

 an lg n  b   (n)  b  n 
4 

 an lg n  b
T(n) においても成り立つ
よってクイックソートの平均実行時間は O(n lg n)
34
n 1
1 2
1 2
k lg k  n lg n  n の証明

2
8
k 1
n 1
n / 2 1
n 1
k 1
k 1
k  n / 2 
 k lg k   k lg k   k lg k

n / 2 1

k 1
n 1
n 1
n / 2 1
n
k lg   k lg n  (lg n  1)  k  lg n  k
2 k  n / 2 
k 1
k  n / 2 
n 1
n / 2 1
k 1
k 1
 lg n k 
k
1
1n n
 n(n  1) lg n    1
2
22 2
1 2
1 2
 n lg n  n
2
8
35
9.1 ソーティングの下界
• ソーティングの入力：〈a1, a2, ..., an〉
• 比較ソートでは要素間の比較のみを用いて
ソートを行う
• 2つの要素 ai, aj が与えられたとき，それらの相
対的な順序を決定するためにテストを行う
– ai aj, ai aj, ai aj, ai aj, ai aj のみ
• これ以外の方法では要素のテストはできない
36
仮定
• すべての入力要素は異なると仮定する
– ai aj という比較は行わないと仮定できる
• ai aj, ai aj, ai aj, ai aj は全て等価
• 全ての比較は ai aj という形と仮定できる
37
決定木モデル
• 比較ソートは決定木 (decision tree) とみなせる
• 決定木はソーティングアルゴリズムで実行される
比較を表現している
• アルゴリズム中における制御，データの移動など
の要因は無視する
38
5,4,3
2,4,1
2,4,1
a1 : a2

入力：数の列
各ノードでは ai  aj
の比較を行う
 5,4,3
a2 : a3

a1 : a3

2,4,1
a1 : a3
a1, a2, a3



a2, a1, a3
a1, a3, a2 a3, a1, a2
1,2,4
葉は入力の置換に対応
5,4,3
a2 : a3


a2, a3, a1 a3, a2, a1
3,4,5
39
決定木の高さと比較回数
• 決定木はソートアルゴリズム A から決まる
• 入力数列を与えると決定木の対応する葉が決まる
• 根から葉までのパスの長さ
＝Aを実行する際の比較回数
• 根から葉までのパス長の最大値
＝実行されるソートアルゴリズムの最悪比較回数
• 比較ソートでの最悪の比較回数は決定木の高さに
対応
40
最悪時の下界
• 決定木の高さの下界＝任意の比較ソートアルゴ
リズムの実行時間の下界
定理 9.1 n 要素をソートするどんな決定木の高さも
(n lg n)
証明 n 要素をソートする高さ h の決定木を考える．
ソートを正しく行うには，n 要素の n! 通りの置換全
てが葉に現れなければならない．
高さ h の2分木の葉の数は高々 2h. よって
n!  2h ではソートできない. つまり h  lg(n!) 41
h  lg( n!)
Stirling
n
n!  
e
n
の公式よりn! 2n  e 
n

 1 
1    
 n 

n
n
n
h  lg  
e
 n lg n  n lg e
 (n lg n)
42
系 9.2 ヒープソートとマージソートは漸近的に
最適な比較ソートである
証明これらの実行時間の上界 O(n lg n) は
定理 9.1 の最悪時の下界 (n lg n) と一致する．
43

Download Report