アルゴリズムとデータ構造 2010年7月15日酒居敬一([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2010/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; int left = aStart; for(; left < right; left++){ int right = anEnd; if(pivot <= anyTargetIntegers[left]){ while(true){ break; /* 入れ替える要素を探します */ } if(left < right){ } /* 要素を入れ替え、 for(; left < right; right--){ 基準値に従って分けます */ if(pivot >= anyTargetIntegers[right]){ }else{ break; 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 マージソート(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 logn) • クイックソートと並ぶオーダーで処理ができる