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

アルゴリズムとデータ構造1
2006年7月11日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html
バブルソート
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
整列済み
public final class BubbleSort
{
public static void sort(int[] anyTargetIntegers)
{
if(null == anyTargetIntegers){
throw new NullPointerException();
}
BubbleSort.print(anyTargetIntegers);
boolean isChanged = false;
int limit = anyTargetIntegers.length - 1;
while(true){
isChanged = false;
for(int count = 0; count < limit; count++){
if(anyTargetIntegers[count] > anyTargetIntegers[count+1]){
int temp = anyTargetIntegers[count];
anyTargetIntegers[count] = anyTargetIntegers[count+1];
anyTargetIntegers[count+1] = temp;
isChanged = true;
}
}
--limit;
BubbleSort.print(anyTargetIntegers);
if(!isChanged){
配列要素どおしの入れ替えが無くなれば終了
break;
}
}
}
}
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]);
}
public class BubbleSortTest
// テスト用プログラム
{
public static void main(String[] anyArguments)
{
int[] intArray = {47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10};
BubbleSort.sort(intArray);
[sakai@star 11]$ java BubbleSortTest
}
47, 18, 8, 7, 2, 4, 9, 0, 72, 88,
}
18, 8, 7, 2, 4, 9, 0, 47, 72, 2,
8, 7, 2, 4, 9, 0, 18, 47, 2, 5,
7, 2, 4, 8, 0, 9, 18, 2, 5, 9,
2, 4, 7, 0, 8, 9, 2, 5, 9, 10,
2, 4, 0, 7, 8, 2, 5, 9, 9, 10,
2, 0, 4, 7, 2, 5, 8, 9, 9, 10,
0, 2, 4, 2, 5, 7, 8, 9, 9, 10,
0, 2, 2, 4, 5, 7, 8, 9, 9, 10,
0, 2, 2, 4, 5, 7, 8, 9, 9, 10,
[sakai@star 11]$
2,
5,
9,
10,
18,
18,
18,
18,
18,
18,
5,
9,
10,
47,
47,
47,
47,
47,
47,
47,
9,
10,
72,
72,
72,
72,
72,
72,
72,
72,
10
88
88
88
88
88
88
88
88
88
クイックソート
基準値を決定
10 8
3 15 5 32 12 1 6 24
基準値を決定
8
3
基準値を決定
基準値を決定
1 6 ＜ 10 ＜ 15 32 12 24
5
基準値を決定
基準値を決定
基準値を決定
整列済み
3
1 ＜ 5 ＜ 8
1 ＜ 3
6
6 ＜ 8
5
1
3
5
6
10
12 ＜ 15 ＜ 32 24
10
12
15
8 10 12 15 24 32
24 ＜ 32
public final class QuickSort
{
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]);
}
public static void sort(int[] anyTargetIntegers)
{
if(null == anyTargetIntegers){
throw new NullPointerException();
}
QuickSort.sort(anyTargetIntegers, 0, anyTargetIntegers.length -1);
}
}
private static int getPivot(int[] anyTargetIntegers, int aStart, int anEnd)
{
int left = anyTargetIntegers[aStart];
int middle = anyTargetIntegers[aStart + ((anEnd - aStart)/2)];
int right = anyTargetIntegers[anEnd];
if((left < middle) && (middle < right)){
return middle;
}
if((left > middle) && (middle > right)){
return middle;
}
if((left < right) && (right < middle)){
return right;
}
if((left > right) && (right > middle)){
return right;
}
if((right < left) && (left < middle)){
return left;
}
return left;
}
できれば、最大値や最小値を避けたい。
そこで、候補として左端・中央・右端を選択し、実際にどれを基準値にするか？
このとき、3個のデータの並び(6通り)を考えて、3個のデータの中央値をとる。
private static void sort(int[] anyTargetIntegers, int aStart, int anEnd)
{
int range = anEnd - aStart;
if(3 > range){
/* 要素数が少ないとき(要素数3以下）、別の方法でソート */
}
int pivot = QuickSort.getPivot(anyTargetIntegers, aStart, anEnd);
int temp = 0;
for(; left < right; left++){
int left = aStart;
if(pivot <= anyTargetIntegers[left]){
int right = anEnd;
break;
while(true){
}
/* 入れ替える要素を探します */
}
if(left < right){
for(; left < right; right--){
/* 要素を入れ替え、
if(pivot >= anyTargetIntegers[right]){
基準値に従って分けます */
break;
}else{
}
break;
}
}
}
QuickSort.sort(anyTargetIntegers, aStart, left -1);
QuickSort.sort(anyTargetIntegers, right +1, anEnd);
QuickSort.print(anyTargetIntegers);
}
if(2 == range){
/* 要素数が3の場合はバブルソート */
if(anyTargetIntegers[aStart] > anyTargetIntegers[aStart+1]){
int temp = anyTargetIntegers[aStart];
anyTargetIntegers[aStart] = anyTargetIntegers[aStart+1];
anyTargetIntegers[aStart+1] = temp;
}
if(anyTargetIntegers[aStart+1] > anyTargetIntegers[anEnd]){
int temp = anyTargetIntegers[aStart+1];
anyTargetIntegers[aStart+1] = anyTargetIntegers[anEnd];
anyTargetIntegers[anEnd] = temp;
}
if(anyTargetIntegers[aStart] > anyTargetIntegers[aStart+1]){
int temp = anyTargetIntegers[aStart];
anyTargetIntegers[aStart] = anyTargetIntegers[aStart+1];
anyTargetIntegers[aStart+1] = temp;
}
}else if(1 == range){
/* 要素数が2の場合は比較して入れ替え */
if(anyTargetIntegers[aStart] > anyTargetIntegers[anEnd]){
int temp = anyTargetIntegers[aStart];
anyTargetIntegers[aStart] = anyTargetIntegers[anEnd];
anyTargetIntegers[anEnd] = temp;
}
}
QuickSort.print(anyTargetIntegers);
return;
if(pivot == anyTargetIntegers[left]){
temp = anyTargetIntegers[left];
anyTargetIntegers[left] = anyTargetIntegers[right];
anyTargetIntegers[right] = anyTargetIntegers[left+1];
基準値を右へ
anyTargetIntegers[left+1] = temp;
１つ移動
left++;
}else if(pivot == anyTargetIntegers[right]){
基準値が右側に
temp = anyTargetIntegers[right];
anyTargetIntegers[right] = anyTargetIntegers[left];
含まれる場合
anyTargetIntegers[left] = anyTargetIntegers[right-1];
anyTargetIntegers[right-1] = temp;
基準値を左へ
right--;
１つ移動
}else{
temp = anyTargetIntegers[left];
anyTargetIntegers[left] = anyTargetIntegers[right];
基準値がどちらにも
anyTargetIntegers[right] = temp;
含まれない場合
left++;
right--;
単純に入れ替え
}
基準値が左側に
含まれる場合
public class QuickSortTest
{
public static void main(String[] anyArguments)
{
int[] intArray = {47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10};
QuickSort.sort(intArray);
}
}
[sakai@star 11]$ java QuickSortTest
47, 18, 8, 7, 2, 4,
Pivot = 10
9, 5, 8, 7, 2, 4,
Pivot = 9 2, 5, 8, 7, 2, 4,
Pivot = 2
0, 2, 2, 7, 8, 4,
0, 2, 2, 7, 8, 4,
Pivot = 5
0, 2, 2, 4, 5, 8,
0, 2, 2, 4, 5, 8,
0, 2, 2, 4, 5, 7,
0, 2, 2, 4, 5, 7,
Pivot = 72
0, 2, 2, 4, 5, 7,
0, 2, 2, 4, 5, 7,
0, 2, 2, 4, 5, 7,
[sakai@star 11]$
9,
9,
9,
9,
9,
9,
9,
8,
8,
8,
8,
8,
0,
0,
0,
5,
5,
7,
7,
9,
9,
9,
9,
9,
72,
2,
9,
9,
9,
9,
9,
9,
9,
9,
9,
9,
88,
10,
10,
10,
10,
10,
10,
10,
10,
10,
10,
10,
2,
88,
88,
88,
88,
88,
88,
88,
88,
47,
18,
18,
5,
72,
72,
72,
72,
72,
72,
72,
72,
18,
47,
47,
9,
18,
18,
18,
18,
18,
18,
18,
18,
72,
72,
72,
10
47
47
47
47
47
47
47
47
88
88
88
ソートの計算量
n個のデータの並びは n! とおり存在する
ソートとは、n! の並びのどれであるかを特定すること
1回の比較で並びの可能性が1/2にできる
並びの可能性が1以下にできればソート完了
そのときの比較回数をkとすれば、
すなわち
Stirlingの公式から
およそ n log nという計算量になる
比較を使う限りの性能上限
分割統治法(162ページ)
• 元の問題をサイズの小さいいくつかの部
分問題に分割
• 個々の部分問題を何らかの方法で解決
• それらの解を統合することで元の問題の
解を得る
マージソート(198ページ)
手続きf(p)
• 問題pを半分にする
それぞれの部分問題に対して次の処理
– 部分問題の要素数が2個
• 小さい順に並び替える→次の処理へ
– 部分問題の要素数が1個
• 並び替える必要が無い→次の処理へ
– 部分問題の要素数が2個より多い
• 手続きfを部分問題を引数に呼ぶ
• 半分にした問題をマージする
– 部分問題列の先頭から、小さい順に取り出す
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
マージソート
(逐次処理, 201ページ)
• データの分割にかかる時間(2要素に分解)
n/2
• ソートにかかる時間(段数log2n, データ数n)
n log2n
• ステップ数は n/2 + n log2n
つまり O(n log2n)
•
クイックソートと並ぶオーダーで処理ができる
マージソート
(並列処理)
• データの分割にかかる時間(2要素に分解)
log2n - 1
• ソートにかかる時間
2n - 1
• ステップ数は (log2n + 2n – 2)
つまり O(n)
•
例ではn=16なので34ステップで終了
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
パイプラインマージソート
• データの分割にかかる時間(図には書いてない）
log2n - 1
• 最初のデータがソートされる時間
log2n
• 引き続くn-1個のデータがソートされる時間
n-1
• ステップ数は (２ log2n + n-2)
つまりO(n)である
•
例では、n=16 なので22ステップで終了

Download Report