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

アルゴリズムとデータ構造
2013年7月4日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html
マージソート(198ページ)
手続きf(p)
• 問題pを半分にする
それぞれの部分問題に対して次の処理
– 部分問題の要素数が2個
• 小さい順に並び替える→次の処理へ
– 部分問題の要素数が1個
• 並び替える必要が無い→次の処理へ
– 部分問題の要素数が2個より多い
• 手続きfを部分問題を引数に呼ぶ
• 半分にした問題をマージする
– 部分問題列の先頭から、小さい順に取り出す
2
53 12 41 69 11
2
84 28 31 63 97 58 76 19 91 88
53 69 69
11 84 84
63 97 97
12 53 41 84
2
31 63 58 97 19 88 88
2
28 28
76 91 91
41
69
11
58
91
76
12
53
2
31
88
19
11
41
76
28
63
12
58
11
31
2
19
12 19 28 31 41 53 58 63 69 76 84 88 91 97
3
マージソート
(逐次処理, 201ページ)
• データの分割にかかる時間(2要素に分解)
n/2
• ソートにかかる時間(段数log2n, データ数n)
n log2n
• ステップ数は n/2 + n log2n
つまり O(n logn)
•
クイックソートと並ぶオーダーで処理ができる
4
public class StraightMergeSort {
private final static <E extends Comparable<E>> int merge(int seqsize, E[] from, E[] into){
int n = 0;
for(int start = 0; start < from.length;){
int i = start;
int j = start + seqsize;
int iend = Math.min(start + seqsize, from.length);
int jend = Math.min(start + 2*seqsize, from.length);
while((i < iend) && (j < jend)){
n++;
into[start++] = (from[i].compareTo(from[j]) <= 0)? from[i++]: from[j++];
}
while(i < iend) into[start++] = from[i++];
作業領域を余分に必要とし、
while(j < jend) into[start++] = from[j++];
空間計算量がO(n)になる。
}
実行時の型に合わせて確保。
return n;
}
public static <E extends Comparable<E>> int sort(E[] array) {
E[] work = (E[])Array.newInstance(array.getClass().getComponentType(), array.length);
int n = 0;
for(int seqsize = 1; seqsize <= array.length; seqsize *= 4){
n += merge(seqsize, array, work);
n += merge(seqsize*2, work, array);
}
return n;
}
データの移動先と移動元を交互に入れ替えながら
}
5
使うので、2回のマージ操作がループ中にある。
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()を呼んだ回数 14
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
compareTo()を呼んだ回数 36
6
分割統治法(162ページ)
• 元の問題をサイズの小さいいくつかの部
分問題に分割
• 個々の部分問題を何らかの方法で解決
• それらの解を統合することで元の問題の
解を得る
7
比較を使わないソート
ビンソート（２１５ページ）
•
•
ビン（瓶ではない、bin = 箱）を使う
データの持つ性質を利用する
–
例:情報の2年生の学生番号（範囲が限られる）
1. ビンをデータの取りうる範囲分確保する
2. データをビンに仕分ける
3. 仕分け完了＝ソート完了なので出力
8
データは0から8までの範囲であると
いうことが事前にわかっている場合
0から8までのビンを用意する
0
1
2
3
4
7
3
6
0
8
3
2
5
6
7
8
ビン
9
出現回数を数えることによる整列アルゴリズム
（２１５ページ）
1. 0からmaxまでの値がそれぞれ何回現れるか数える。
2. これを元にその値以下の値の個数を計算する。
3. 入力のそれぞれの値が出力のどの位置に収まるかを計算し出力する。
public class CountSort {
public static <E extends Number> void sort(E[] array, int max) {
int[] count = new int[max + 1];
E[] original = array.clone();
for(E e: original){
count[e.intValue()]++; // 出現回数
}
for(int i = 1; i < count.length; i++){
count[i] += count[i-1]; // 順位付け
}
for(E e: original){
int j = --count[e.intValue()];
array[j] = e;
}
作業領域を余分に必要とする
}
}
10
ビンソートのプログラム（２１６ページ）
1. データを入れるビンの実装にリストを使う。ビンは配列として並べる。
2. 入力データを対応するビンに仕分ける。
3. ビンを順に取り出し、ビンの中のデータを順に出力する。
public class BinSort {
public static <E extends Number> void sort(E[] array, int max) {
List<E>[] bin = new List[max + 1];
for(E e: array){
if(bin[e.intValue()] == null){
bin[e.intValue()] = new LinkedList<E>();
}
bin[e.intValue()].add(e);
}
int i = 0;
for(List<E> l: bin){
作業領域を余分に必要とする
if(l != null){
for(E e: l){
array[i++] = e;
}
}
}
}
}
11
private final static Double[] test_data_double = {
47.0, 18.1, 8.2, 7.3, 2.4, 4.5, 9.6, 0.7, 72.8, 88.9, 2.0, 5.1, 9.2, 10.3,
};
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) {
StringBuffer sb = new StringBuffer();
Double[] data1 = test_data_double.clone();
sort(data1, 88);
for (Double e : data1) sb.append(e).append(", ");
sb.append('\n');
Integer[] data2 = test_data_int.clone();
sort(data2, 88);
ビンに仕分けて、取り出すだけ。
for (Integer e : data2) sb.append(e).append(", ");
時間計算量は良い。
sb.append('\n');
System.out.print(sb.toString());
空間計算量は良くない。
}
CountSortの結果
0.7, 2.0, 2.4, 4.5, 5.1, 7.3, 8.2, 9.2, 9.6, 10.3, 18.1, 47.0, 72.8, 88.9,
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
BinSortの結果
0.7, 2.4, 2.0, 4.5, 5.1, 7.3, 8.2, 9.6, 9.2, 10.3, 18.1, 47.0, 72.8, 88.9,
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
12
基底法（218ページ）
•辞書式順序によりソートするために使えるアルゴリズム
•辞書式順序で文字列xがyより小さいとは、
以下のいずれかの条件を満たす場合のこと。
x[0]  y[0]
x[0]  y[0] かつ x[1]  y[1]

x[0]  y[0] かつ x[1]  y[1] かつ x[k  2]  y[k  2] かつ x[k  1]  y[k  1]
（配列の添え字をJavaに合わせてみました。）
13
public class RadixSort {
public static <E extends CharSequence> void sort(E[] array, int k) {
List<E>[] bin = new List[Character.MAX_VALUE + 1];
}
｝
while(--k >= 0){
for(E e: array){
int index = 0;
if(k < e.length()){
index = e.charAt(k);
}
if(bin[index] == null){
bin[index] = new LinkedList<E>();
}
bin[index].add(e);
}
int i = 0;
for(List<E> l: bin){
if(l != null){
for(E e: l){
array[i++] = e;
}
l.clear();
}
}
}
余談：教科書の書かれた時代に、この
ような実装をすると怒られた。
当時のPCの主記憶は640KBしかなく、
要素数64Kの配列を確保するとは非常
識ということ。
今では常識的な大きさなので気にする
ことはない。
そもそもJavaがなかったし、C言語の
C89規格が決まったかどうかというくら
い昔の話。
もしかしてみなさん生まれてない？
14
private final static String[] test_data_prefecture = {
"北海道", "青森県", "岩手県", "宮城県", "秋田県", "山形県", "福島県", "茨城県",
"栃木県", "群馬県", "埼玉県", "千葉県", "東京都", "神奈川県", "新潟県", "富山県",
"石川県", "福井県", "山梨県", "長野県", "岐阜県", "静岡県", "愛知県", "三重県",
"滋賀県", "京都府", "大阪府", "兵庫県", "奈良県", "和歌山県", "鳥取県", "島根県",
"岡山県", "広島県", "山口県", "徳島県", "香川県", "愛媛県", "高知県", "福岡県",
"佐賀県", "長崎県", "熊本県", "大分県", "宮崎県", "鹿児島県", "沖縄県",
};
private final static String[] test_data_direction = {
"北", "北微東", "北北東", "北東微北", "北東", "北東微東", "東北東", "東微北",
"東", "東微南", "東南東", "南東微東", "南東", "南東微南", "南南東", "南微東",
"南", "南微西", "南南西", "南西微南", "南西", "南西微西", "西南西", "西微南",
"西", "西微北", "西北西", "北西微西", "北西", "北西微北", "北北西", "北微西",
};
public static void main(String[] args) {
StringBuffer sb = new StringBuffer();
String[] data;
data = test_data_prefecture.clone();
sort(data, 4); // 最初の4文字でソートする。
for (String e : data) sb.append(e).append(", ");
sb.append('\n');
data = test_data_direction.clone();
sort(data, 4); // 最初の4文字でソートする。
for (String e : data) sb.append(e).append(", ");
System.out.println(sb.toString());
}
15
RadixSortの結果
三重県, 京都府, 佐賀県, 兵庫県, 北海道, 千葉県, 和歌山県, 埼玉県,
大分県, 大阪府, 奈良県, 宮城県, 宮崎県, 富山県, 山口県, 山形県,
山梨県, 岐阜県, 岡山県, 岩手県, 島根県, 広島県, 徳島県, 愛媛県,
愛知県, 新潟県, 東京都, 栃木県, 沖縄県, 滋賀県, 熊本県, 石川県,
神奈川県, 福井県, 福岡県, 福島県, 秋田県, 群馬県, 茨城県, 長崎県,
長野県, 青森県, 静岡県, 香川県, 高知県, 鳥取県, 鹿児島県,
北, 北北東, 北北西, 北微東, 北微西, 北東, 北東微北, 北東微東,
北西, 北西微北, 北西微西, 南, 南南東, 南南西, 南微東, 南微西,
南東, 南東微南, 南東微東, 南西, 南西微南, 南西微西, 東, 東北東,
東南東, 東微北, 東微南, 西, 西北西, 西南西, 西微北, 西微南,
16
アルゴリズムとデータ構造演習
学生番号：
名前：
• 前提: 同じ値を持つデータをソートした場合に、
ソート結果にその入力順が保存されるアルゴリズムを
「安定なアルゴリズム」という。
• 現状: ところが、プログラム例のCountSortでは、
本来は安定なアルゴリズムにできるはずのところが、
そうなっていない。BinSortの結果と同じになるべき。
• 問題：安定なアルゴリズムを実装するように、
CountSortのプログラムリストを修正せよ。
解答はプログラムリストの該当箇所を二重線で消したり
追記したりすることで直接書き込むこと。
public class CountSort {
public static <E extends Number> void sort(E[] array, int max) {
int[] count = new int[max + 1];
E[]
original = array.clone();
for(E e: original){
count[e.intValue()]++; // 出現回数
}
for(int i = 1; i < count.length; i++){
count[i] += count[i-1]; // 順位付け
}
for(E e: original){
int
j = --count[e.intValue()];
array[j] = e;
}
}
}

Download Report