酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2006年7月11日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html

バブルソート ＞ 8 3 ＞ 10 8 ＞ 10 3 ＜ 8 10 ＞ 10 5 ＜ 10 15 ＞ 15 5 ＜ 10 15 ＞ 15 12 ＜ 15 32 ＞ 15 1 ＞ 32 12 ＞ 32 1 ＞ 15 6 ＞ 32 6 ＜ 15 24 ＞ 32 24 整列済み 10 1 8 3 15 5 32 12 6 24 10 8 8 3 10 3 10 5 15 5 15 12 15 1 32 12 32 1 15 6 32 6 24 32 24 入れ替え 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替えない 入れ替え 入れ替え 入れ替え 入れ替え 入れ替え 入れ替えない 入れ替え 入れ替え 残りも同様に整列させると… 10 1 8 3 15 5 32 12 6 24

配列要素どおしの入れ替えが無くなれば終了 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; 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, 2, 5, 9, 10 18, 8, 7, 2, 4, 9, 0, 47, 72, 2, 5, 9, 10, 88 8, 7, 2, 4, 9, 0, 18, 47, 2, 5, 9, 10, 72, 88 7, 2, 4, 8, 0, 9, 18, 2, 5, 9, 10, 47, 72, 88 2, 4, 7, 0, 8, 9, 2, 5, 9, 10, 18, 47, 72, 88 2, 4, 0, 7, 8, 2, 5, 9, 9, 10, 18, 47, 72, 88 2, 0, 4, 7, 2, 5, 8, 9, 9, 10, 18, 47, 72, 88 0, 2, 4, 2, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88 [sakai@star 11]$

クイックソート 基準値を決定 10 1 8 3 15 5 32 12 6 24 基準値を決定 10 8 3 5 1 6 15 32 12 24 ＜ 10 整列済み 基準値を決定 5 15 ＜ 3 1 8 6 12 32 24 10 5 15 ＜ 3 1 8 6 12 32 24 10 10 1 8 3 15 5 32 12 6 24

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)){ if((left < right) && (right < middle)){ return right; if((left > right) && (right > middle)){ if((right < left) && (left < middle)){ 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; int left = aStart; int right = anEnd; while(true){ /* 入れ替える要素を探します */ if(left < right){ /* 要素を入れ替え、 基準値に従って分けます */ }else{ break; QuickSort.sort(anyTargetIntegers, aStart, left -1); QuickSort.sort(anyTargetIntegers, right +1, anEnd); QuickSort.print(anyTargetIntegers); for(; left < right; left++){ if(pivot <= anyTargetIntegers[left]){ break; } for(; left < right; right--){ if(pivot >= anyTargetIntegers[right]){

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; }else if(1 == range){ /* 要素数が2の場合は比較して入れ替え */ if(anyTargetIntegers[aStart] > anyTargetIntegers[anEnd]){ anyTargetIntegers[aStart] = anyTargetIntegers[anEnd]; 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{ anyTargetIntegers[right] = temp; } 基準値が左側に含まれる場合 基準値を右へ １つ移動 基準値が右側に含まれる場合 基準値を左へ １つ移動 基準値がどちらにも含まれない場合 単純に入れ替え

[sakai@star 11]$ java QuickSortTest 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, 9, 0, 72, 88, 2, 5, 9, 10 Pivot = 10 9, 5, 8, 7, 2, 4, 9, 0, 2, 10, 88, 72, 18, 47 Pivot = 9 2, 5, 8, 7, 2, 4, 9, 0, 9, 10, 88, 72, 18, 47 Pivot = 2 0, 2, 2, 7, 8, 4, 9, 5, 9, 10, 88, 72, 18, 47 0, 2, 2, 7, 8, 4, 9, 5, 9, 10, 88, 72, 18, 47 Pivot = 5 0, 2, 2, 4, 5, 8, 9, 7, 9, 10, 88, 72, 18, 47 0, 2, 2, 4, 5, 8, 9, 7, 9, 10, 88, 72, 18, 47 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 88, 72, 18, 47 Pivot = 72 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 47, 18, 72, 88 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88 [sakai@star 11]$

ソートの計算量 n個のデータの並びは n! とおり存在する 1回の比較で並びの可能性が1/2にできる 並びの可能性が1以下にできればソート完了 そのときの比較回数をkとすれば、 すなわち Stirlingの公式から およそ n log nという計算量になる 比較を使う限りの性能上限

分割統治法(162ページ) 元の問題をサイズの小さいいくつかの部分問題に分割 個々の部分問題を何らかの方法で解決 それらの解を統合することで元の問題の解を得る

マージソート(198ページ) 手続きf(p) 問題pを半分にする それぞれの部分問題に対して次の処理 半分にした問題をマージする 部分問題の要素数が2個 小さい順に並び替える→次の処理へ 部分問題の要素数が1個 並び替える必要が無い→次の処理へ 部分問題の要素数が2個より多い 手続きfを部分問題を引数に呼ぶ 半分にした問題をマージする 部分問題列の先頭から、小さい順に取り出す

69 11 84 63 76 91 53 97 41 2 28 31 58 19 12 88 53 69 69 11 84 84 63 97 97 76 91 91 12 53 41 84 2 28 28 31 63 58 97 19 88 88 41 69 11 58 91 76 12 53 2 31 88 19 41 76 28 63 12 58 11 31 2 19 2 11 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ステップで終了

69 11 84 63 76 91 53 97 41 2 28 31 58 19 12 88 53 69 69 11 84 84 63 97 97 76 91 91 12 53 41 84 2 28 28 31 63 58 97 19 88 88 41 69 11 58 91 76 12 53 2 31 88 19 41 76 28 63 12 58 11 31 2 19 2 11 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ステップで終了