アルゴリズムとデータ構造1

アルゴリズムとデータ構造
2012年7月2日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html
1
ヒープソート（１８５ページ）
ソート前
0
ソート済み
i
length-1
挿入法では、ソート未完了の列から線形探索により
次の挿入対象を探していた。
配列[i]の位置に、配列[0]から配列[i]までの間の
最大値を置くことを、配列末端から繰り返せばソートできる。
ただし、線形探索を毎回繰り返すのは効率が悪い。
比較回数の合計がおおむね ( n -1) + ( n - 2 ) +
n2
+ 2 +1 »
2
2
部分順序付き木（１８６ページ）
•挿入法におけるソート前データ列から探索しやすいように
データの置き方を工夫する。これまでの探索木のような順序木ではなく、
部分順序付き木というものにデータを置く。
•データを置くルールは、親の値が子の値より小さくないこと。
•そうすると、根には最大値が来る。
23
19
21
17
11
15
13
9
1
5
7
3
二分探索木ではないので、
このような配置でも問題ない
3
部分順序付き木の組み替え1
(原理的•187ページ)
a
ab
a
cd
d
c
ab
c
b
b
d
b
a
ab
a
b
e
f
ab
f
e
ef
4
ソートのための部分順序付き木
•ソートのために特別なデータ構造を定義し使用することは非効率。
•これを配列に置くことを考える。
•木の高さがバランスしていないとソート途中の探索も非効率。
•配列上のデータの並びから、一律に木の形を定義する。
•配列[i]の子は、根を配列[0]とすると、配列[2*i+1]配列[2*i+2]になる。
•教科書と違うことに注意。
23 0
21
9
17
3
7
3
8
1
13
19
15
4
9
5
11
10
1
5
2
7
6
11
5
配列に木を表現したことにする（１８８ページ）
13 21 19
根
9
２段目
11 7
5
３段目
17
3
15 23
1
４段目
木にバランスよくデータを置くには
配列上にあるデータ列を区切って
木に対応付けるとよい。
でも、部分順序付き木ですらない。
（このページの現状では…）
13
21
19
9
17
11
5
3
15
23
7
1
6
部分順序付き木の組み替え2
(ソート目的•190ページ)
木のバランスを崩さないように
頂点ｆを根に動かした。
根を取り除いた。
a
c
af
ab
a
b
d
f
e
f
d
c
b
e
根は配列[0]、fは配列の最後にある。
aとfを入れ替え
a
d
c
a
dとfを入れ替え
f
b
f
e
df
d
c
cd
b
e
7
最初のヒープを作る
（１８９ページから１９１ページ、手続きdownheap）
9 15
21
13 21
23
23 19 17
13
23
13
5 11 7
9
17
3
15
13 23
5
1
配列にデータを置いているので、
葉とその親の位置は計算で
一意に求まる。
そこで、葉に近いところから、
部分順序付き木のルールに
従ってデータをそろえていく。
（１９２ページ）
13
23
13
21
23
19
9
17
17
9
11
23
21
13
15
5
3
15
13
23
5
7
1
8
最大値を部分順序付き木から
探しながら挿入法のようにソート（１９２・１９３ページ）
21
15
11
39157 17
15
21
3159 19
11
93 11
7 15
3 19
13
17
23
19
13
537 17
197 15
13
5 13
19 17
13 21
5 23
1
1
33
77
55
11 13
99 11
13 15 17 19 21 23
13
11
21
17
23
95317
19
15
21
13
17
591
15
11
37
19
3
13
15
17
19
19
3
13
11
5
5
7
1
1. 最大値をソート済み列に加える。
2. 未ソートデータ列の最後のデータを根に置く。
3. 部分順序付き木になるようにデータを移動する。
9
public class HeapSort {
private final static <E extends Comparable<E>> int downheap(E[] array, int root, int last){
int n = 0;
E v = array[root];
while(true){
int j = 2*root+1; // 左の子
if(j > last) break; // 左の子がない(もちろん、右にも子がない)場合は終了
if(j != last){ // 両方の子がある
n++;
if(array[j+1].compareTo(array[j]) > 0) j++; // 右の子 > 左の子、大きいほうを選ぶ
}
n++;
if(v.compareTo(array[j]) >= 0) break;
array[root] = array[j];
root = j; // 上→下
xの子は2*x+1と2*x+2にあるので、
}
lengthが奇数なら、2*x+2=length-1, x=(length-3)/2
array[root] = v;
return n;
lengthが偶数なら、2*x+1=length-1, x=(length-2)/2
}
public static <E extends Comparable<E>> int sort(E[] array) {
int n = 0;
for(int i = array.length/2 - 1; i >= 0; i--) n += downheap(array, i, array.length - 1); //下→上
for(int i = array.length - 1; i > 0; i--){
E temp = array[0]; array[0] = array[i]; array[i] = temp;
n += downheap(array, 0, i-1);
}
return n;
10
}}
private final static String[] test_data_string = {
"東京", "北海道", "高知", "兵庫", "鹿児島", "沖縄", "青森"};
private final static Integer[] test_data_int = {
47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10};
public static void main(String[] args) {
int n;
StringBuffer sb = new StringBuffer();
String[] data1 = test_data_string.clone();
n = sort(data1);
for (String e : data1) {
sb.append(e).append(", ");
}
sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n');
Integer[] data2 = test_data_int.clone();
n = sort(data2);
for (Integer e : data2) {
sb.append(e).append(", ");
}
sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n');
System.out.print(sb.toString());
}
兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島,
compareTo()を呼んだ回数 18
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
compareTo()を呼んだ回数 66
11
ヒープソートの計算量(193ページ)
• 完全２分木とすると、downheapで調べる
段数は、部分木の範囲ごとに次のようになる。
1段
2段
3段
4段
n/4からn/2
n/8からn/4
n/16からn/8
n/32からn/16
• 全体では、
• k  log2 n とすると
n
n
n
n
1  2   3   4     (log 2 n  1) 1
4
8
16
32
1 2k 2  2  2k 3  3 2k 4   (k  2)  2  (k 1) 1  2k  (k  1)
k  O(log2 n) だったので、 O(n)
初期操作にはO(n)必要。
12
ヒープソートの計算量（つづき）
• 最大値を一つづつ取り出して、ソートする
作業では、
最大値を取り出す作業が n 回
その後で木を作り替える作業が log2 n 回
つまり O(n log n) になる。
13
アルゴリズムとデータ構造演習
学生番号：
名前：
問題: 部分順序付き木を作り替える過程を記入しなさい。
23
21
19
1
17
11
15
7
21
9
3
13
5
19
1
17
1. 最初期のヒープ
9
11
15
3
13
5
7
23
2. 最大値を取り出し、未ソート配列より
値を取り出し、根に置く。
23
3. 途中経過
14
23
4. 途中経過
23
21
5. 途中経過
17
19
9
1
11
15
3
13
5
7
23
6. データ１個のソートが終わり、木の再構成も終わった状態。
15
5
17
19
9
1
11
15
3
13
21
7
23
7. 2個目のデータのソート開始。
21
23
途中経過(必要に応じて使うこと）
21
23
途中経過(必要に応じて使うこと）
16
21
23
途中経過(必要に応じて使うこと）
21
23
途中経過(必要に応じて使うこと）
21
23
データ２個のソートが終わり、木の再構成も終わった状態。
17

Download Report