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

アルゴリズムとデータ構造1
2006年7月14日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html
期末試験
• 教室: Ｃ101
• 日時: 2006年7月24日 14時50分～16時20分
– 入室限度: 15時20分まで
– 退出可能: 15時3０分より
• 持ち込み可
– 教科書・資料(自筆・コピー問わず)は持ち込み可
– 人間・パソコン・携帯電話・PHSなど持ち込み不可
• 学生証必携
– 持っていない場合は教務で発行してもらうこと
線形なデータ構造における整列
(ソート)
• 比較によるもの
– バブルソート
– クイックソート
– マージソート
• 比較によらないもの
– ビンソート
計算量を減らす
• 比較を用いたソーティングアルゴリズム
– 大小といった情報は、比較することで得られる
– データの並びについては仮定をおかない
– そうするとO（n log2 n）は下回れない
• 比較を用いないソーティング
– 情報を得なければいけない点は変わらない
– データの性質に合ったアルゴリズムを使う
バブルソートばかりを使うのはやめて、クイッ
クソートのような性能の良いアルゴリズムを
使いましょうという話は間違ってはいない。
ただし、データの性質をも考慮に入れ
てそれが最善かを考える必要はある。
比較を使わないソート
ビンソート
•
•
ビン（瓶ではない、bin = 箱）を使う
データの持つ性質を利用する
–
例:情報の2年生の学生番号（範囲が限られる）
1. ビンをデータの取りうる範囲分確保する
2. データをビンに仕分ける
3. 仕分け完了＝ソート完了なので出力
データは0から8までの範囲であると
いうことが事前にわかっている場合
0から8までのビンを用意する
0
1
2
3
4
5
6
7
8
ビン
7
3
6
0
8
3
2
public final class BinSort
{
public static void sort(int[] anyTargetIntegers, int aMin, int aMax)
{
if(null == anyTargetIntegers){
throw new NullPointerException();
}
BinSort.print(anyTargetIntegers);
int[] bin = new int[aMax - aMin + 1];
for(int i = 0; i < bin.length; i ++){
bin[i] = 0;
}
int[] original = (int [])anyTargetIntegers.clone();
for(int i = 0; i < original.length; i++){
bin[original[i] - aMin]++;
int[] original = new int[anyTargetIntegers.length];
}
for(int i = 0; i < anyTargetIntegers.length; i++){
for(int i = 1; i < bin.length; i ++){
original[i] = anyTargetIntegers[i];
bin[i] += bin[i-1];
}
}
}
}
for(int i = original.length-1; i >= 0; i--){
int j = --bin[original[i] - aMin];
anyTargetIntegers[j] = original[i];
}
BinSort.print(anyTargetIntegers);
public static void print(int[] anyTargetIntegers)
{
int limit = anyTargetIntegers.length - 1;
for(int count = 0; count < limit; count++){
if(10 > anyTargetIntegers[count]){
System.out.print(" ");
}
System.out.print(anyTargetIntegers[count] + ", ");
}
System.out.println(anyTargetIntegers[limit]);
}
[sakai@star 11]$ java BinSortTest
47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10
0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88
[sakai@star 11]$
ビンに仕分けて、取り出すだけ。
時間計算量は良い。
空間計算量は良くない。
ハッシュと探索
ソート
比較だけを使用
バブルソート
クイックソート
マージソート
比較以外の方法を使用
ビンソート
探索
比較だけを使用
線形探索
二分探索
 あらかじめソートが必要
比較以外の方法を使用
ハッシュ法
ハッシュ
テーブル
連結リスト
0
7
161
245
1
148
71
106
2
72
44
163
3
234
164
206
4
4
81
5
103
180
47
6
62
132
20
19
150
5
127
112
1
32
202
196
139
125
28
88
117
43
98
78
176
154
99
34
180
103
163
170
50
81
89
100
186
244
53という値を持つ葉を追加せよ。
1という値を持つ葉を追加せよ。
38という値を持つ葉を削除せよ。
45という値を持つ葉を削除せよ。

Download Report