酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2005年7月15日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG2/005/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, left +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という計算量になる 比較を使う限りの性能上限

計算量を減らす 比較を用いたソーティングアルゴリズム 比較を用いないソーティング 大小といった情報は、比較することで得られる データの並びについては仮定をおかない そうするとO（n log2 n）は下回れない 比較を用いないソーティング 情報を得なければいけない点は変わらない データの性質に合ったアルゴリズムを使う バブルソートばかりを使うのはやめて、クイックソートのような性能の良いアルゴリズムを使いましょうという話は間違ってはいない。 ただし、データの性質をも考慮に入れてそれが最善かを考える必要はある。

比較を使わないソート ビンソート ビン（瓶ではない、bin = 箱）を使う データの持つ性質を利用する ビンをデータの取りうる範囲分確保する 例:情報の2年生の学生番号（範囲が限られる） ビンをデータの取りうる範囲分確保する データをビンに仕分ける 仕分け完了＝ソート完了なので出力

データは0から8までの範囲であるということが事前にわかっている場合 0から8までのビンを用意する 1 2 3 4 7 3 6 8 3 2 5 6 7 8 ビン

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]++; for(int i = 1; i < bin.length; 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]; int[] original = new int[anyTargetIntegers.length]; for(int i = 0; i < anyTargetIntegers.length; i++){ original[i] = anyTargetIntegers[i]; }

ビンに仕分けて、取り出すだけ。 時間計算量は良い。 空間計算量は良くない。 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]$ ビンに仕分けて、取り出すだけ。 時間計算量は良い。 空間計算量は良くない。

演習課題 キーをx、ハッシュ関数を hash(x)=x mod 7 としたとき、つぎの数値列の左から順にキーとして分離連鎖法によりハッシュした結果を図で示せ(途中経過は不要)。ハッシュテーブルの大きさは 7 とし、最後に入れたデータがハッシュテーブルから参照されるようにリストの先頭にデータを挿入するとする。 48 34 78 35 43 14 60 53 5 99 68 37 77 50 61 キーを x 、ハッシュ関数を hash(x)=x mod 19、以前のハッシュ値を h としたときの再ハッシュ関数をrehash(x)=(h + 5-(x mod 5)) mod 19 としたとき、次の数値列の左から順にキーとして開番地法によりハッシュした結果を示せ(途中経過は不要)。ハッシュテーブルの大きさは 19 とする。 48 34 78 35 43 14 60 53 5 99 68 37 77 50 61 次の文章を完成させよ。(1)～(5)はO記法、(a)～(h)は単語が入る。 2分探索木は(1)の計算量で探索ができる方法だが、挿入にも(2)の計算量を必要とする。つまり、挿入・探索・削除のすべてを行なうのに(3)の計算量が必要であるということになる。これは2分探索木では値の大小の(a)によって得られる情報をもとに挿入・探索・削除を行なうが、1回の(a)により木の(b)が1小さくなり、木の大きさが平均して(c)になることを表している。一方で、(a)によらないでデータを挿入・探索・削除する方法もある。そのひとつとしてハッシュ法が挙げられるが、これは(4)の計算量が期待できる方法である。また、データの整列に関して、(a)によるものとして(d)や(e)や(f)がある一方で、(a)によらないビンソートもある。(d)はO(n2)の計算量を必要とするが、(e)や(f)はO(n log n)の計算量ですむ。ビンソートは(5)の(g)計算量ですむが(h)計算量は良くない場合が多い。