アルゴリズムとデータ構造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; 1つ移動 left++; }else if(pivot == anyTargetIntegers[right]){ 基準値が右側に temp = anyTargetIntegers[right]; anyTargetIntegers[right] = anyTargetIntegers[left]; 含まれる場合 anyTargetIntegers[left] = anyTargetIntegers[right-1]; anyTargetIntegers[right-1] = temp; 基準値を左へ right--; 1つ移動 }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 • ステップ数は (2 log2n + n-2) つまりO(n)である • 例では、n=16 なので22ステップで終了
© Copyright 2024 ExpyDoc