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

アルゴリズムとデータ構造
2011年6月23日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html
1
整列（ソート）
• 配列を使用するソートアルゴリズム
– 挿入法
– 時間計算量
O(n2 )
– バブルソート
– 時間計算量
– シェルソート
– 時間計算量
O(n2 )
O(n2 )
– クイックソート
– 時間計算量 O( n log n)
– 時間計算量は最悪でも O(n 2 )
• 空間計算量はいずれも O (n)
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());
}
3
public class SimpleSort {
public static <E extends Comparable<E>> int sort(E[] array) {
int n = 0;
for(int i = 0; i < (array.length - 1); i++){
単純な整列アルゴリズム
for(int j = i+1; j < array.length; j++){
（１４７ページ）
n++;
if(array[j].compareTo(array[i]) < 0){
E tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
}
return n;
}
}
兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島,
compareTo()を呼んだ回数 21
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
compareTo()を呼んだ回数 91
4
public class SelectionSort {
public static <E extends Comparable<E>> int sort(E[] array) {
int n = 0;
for(int i = 0; i < (array.length - 1); i++){
int minpos = i;
for(int j = i+1; j < array.length; j++){
n++;
if(array[j].compareTo(array[minpos]) < 0){
minpos = j;
}
}
E tmp = array[minpos];
array[minpos] = array[i];
array[i] = tmp;
}
return n;
}
}
選択法
（１４９ページ）
兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島,
compareTo()を呼んだ回数 21
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
compareTo()を呼んだ回数 91
5
バブルソート
（１４９ページ）
10
8 10
8 10
15
10
3 15
15
5 15
32
15
5 15
32
3215
12
32
12
1 32
24
6 24
＞
＞38 10
＜
＜
＞
＞
＜
＜
＞
＞
＞
＞16 ＞
＜
10
38 10
83 10
53 10
15
5 15
12
5 15
32
12
1 15
12
32
61 15
32
61 32
24
6 32
24
整列済み
入れ替え
入れ替えない
入れ替え
入れ替えない
入れ替え
入れ替えない
入れ替え
入れ替えない
入れ替え
入れ替え
入れ替え
入れ替えない
入れ替え
入れ替え
残りも同様に整列させると…
1
3
5
6
8 10 12 15 24 32
6
public class BubbleSort {
public static <E extends Comparable<E>> int sort(E[] array) {
int n = 0;
boolean isChanged = false;
int limit = array.length - 1;
while (true) {
isChanged = false;
for (int count = 0; count < limit; count++) {
if (array[count].compareTo(array[count + 1]) > 0) {
E temp = array[count];
array[count] = array[count + 1];
array[count + 1] = temp;
isChanged = true;
}
n++;
}
limit--;
if (!isChanged) break;
}
return n;
}
兵庫, 北海道, 東京, 沖縄,
}
青森, 高知, 鹿児島,
compareTo()を呼んだ回数 18
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
compareTo()を呼んだ回数 81
7
挿入法
（１５０ページ）
10
8
3
1 10
8 10
5
3
3 10
8
5
15
8 10
6
15
12
5 32
8
10
15 32
12
15 32
12
15
1 24
32
6 32
24
以上で整列おわり！…
1
3
5
6
8 10 12 15 24 32
8
public class InsertionSort {
public static <E extends Comparable<E>> int sort(E[] array) {
int n = 0;
for(int i = 1; i < array.length; i++){
E w = array[i];
int j = i - 1;
while((j >= 0) && w.compareTo(array[j]) < 0){
array[j+1] = array[j];
j--;
n++;
}
n++;
array[j+1] = w;
}
return n;
}
}
兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島,
compareTo()を呼んだ回数 14
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
compareTo()を呼んだ回数 59
9
シェルソート
（１５６ページ）
h  14
10
5
3
1
8
5
3
3
8
5
15
8
6
1 10
5 24
6
8
32
10
12 24
15 24
12
15
1 24
10
6 32
24
以上で整列おわり！…
1
3
5
6
8 10 12 15 24 32
10
public class ShellSort {
public static <E extends Comparable<E>> int sort(E[] array) {
int n = 0;
int h;
for(h = 1; h < array.length; h = h*3 + 1); // nより小さい範囲で最大のhを求める
while(h > 1){
h /= 3;
for(int i = h; i < array.length; i++){
E w = array[i];
int j = i - h;
n++;
while((j >= 0) && w.compareTo(array[j]) < 0){
array[j+h] = array[j];
j -= h;
n++;
}
array[j+h] = w;
}
}
return n;
兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島,
}
}
compareTo()を呼んだ回数 17
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88,
compareTo()を呼んだ回数 53
11
シェルソートの計算量
•
h を 1, 3, 7, 15, ..., 2 1
32
とすると最悪時間計算量が O(n ) になる。
•
h をうまく選ぶと
最悪時間計算量 O(n4 3 ) になる。
•
h を 1, 4, 13, 40, 121, ..., 3hk 1  1
1.25
とすると平均時間計算量が O(n ) になる。
k
12
ソートの計算量
n個のデータの並びは n! とおり存在する
ソートとは、n! の並びのどれであるかを特定すること
1回の比較で並びの可能性が1/2にできる
並びの可能性が1以下にできればソート完了
そのときの比較回数をkとすれば、
すなわち
Stirlingの公式から
およそ n log nという計算量になる
比較を使う限りの性能上限
13
線形なデータ構造における整列
(ソート)
• 比較によるもの
– バブルソート
– クイックソート
– マージソート
• 比較によらないもの
– ビンソート
14
計算量を減らす
• 比較を用いたソーティングアルゴリズム
– 大小といった情報は、比較することで得られる
– データの並びについては仮定をおかない
– そうするとO（n log2 n）は下回れない
• 比較を用いないソーティング
– 情報を得なければいけない点は変わらない
– データの性質に合ったアルゴリズムを使う
バブルソートばかりを使うのはやめて、クイックソートの
ような性能の良いアルゴリズムを使いましょうという話は
間違ってはいない。
ただし、
データの性質をも考慮に入れてそれが最善か
を考える必要はある。
15
アルゴリズムとデータ構造演習
学生番号：
名前：
10
8
3
15
5 32 12
1
6 24
0-4-8をソート
5
8
3
15
6 32 12
1
10 24
1-5-9をソート
5
8
3
15
6 24 12
1
10 32
5
8
3
1
6 24 12 15 10 32
3
5
8
1
6 24 12 15 10 32
1
3
5
8
6 24 12 15 10 32
1
3
5
6
8 24 12 15 10 32
1
3
5
6
8
12 24 15 10 32
1
3
5
6
8
12 15 24 10 32
元のデータ
h4
(2-6をソート、)3-7をソート
h  1 挿入法でソート
問題：元のデータがシェルソートで
h=7, 3, 1 で順にソートされてゆくとき、
その途中経過を書きなさい。
ソート完了
1
3
5
6
8
10 12 15 24 32
16
17

Download Report