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

クイックソート 基準値を決定 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 class QuickSort { public static <E extends Comparable<E>> int sort(E[] array) { return sort(array, 0, array.length - 1); } private static <T extends Comparable<T>> T getPivot(T[] array, int start, int end) { return array[start]; private static <T extends Comparable<T>> int sort(T[] array, int start, int end) { int n = 0; if ((end - start) < 1) return n; // データが1個以下のとき、ソート完了 T pivot = getPivot(array, start, end); int left = start; // start以上、left未満が仕分け済 int right = end; // rightより上、end以下が仕分け済 split: while (left <= right) { for (; left <= right; left++) { n++; if (pivot.compareTo(array[left]) > 0) continue; // pivot以上の値を探せた for (; left <= right; right--) { if (pivot.compareTo(array[right]) < 0) continue; // pivot以下の値を探せた if (left < right) { T temp = array[left]; array[left++] = array[right]; array[right--] = temp; continue split; } else break split; } } } n += sort(array, start, left - 1); n += sort(array, right + 1, end); return n; }}

兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 27 private final static String[] test_data_string = { "東京", "北海道", "高知", "兵庫", "鹿児島", "沖縄", "青森"}; private final static Integer[] test_data_int = { 47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10}; public static void main(String[] args) { int n; StringBuffer sb = new StringBuffer(); String[] data1 = test_data_string.clone(); n = sort(data1); for (String e : data1) { sb.append(e).append(", "); } sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n'); Integer[] data2 = test_data_int.clone(); n = sort(data2); for (Integer e : data2) { System.out.print(sb.toString()); 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 27 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 79

クイック ソート （最悪の 場合） 32 24 15 12 10 8 6 5 3 1 5 24 15 12 10 8 6 3 1 ＜ 32 5 15 12 10 8 6 3 1 ＜ 32 24 5 12 10 8 6 3 1 ＜ 15 32 24 5 10 8 6 3 1 ＜ 15 12 32 24 5 8 6 3 1 ＜ 10 15 32 12 24 5 6 3 1 ＜ 10 8 15 32 12 24 5 3 1 ＜ 10 8 15 32 12 6 24 3 1 ＜ 10 8 15 5 32 12 6 24 1 ＜ 10 8 3 15 5 32 12 6 24 10 1 8 3 15 5 32 12 6 24

再帰的アルゴリズム 再帰は重要なアルゴリズムの概念である． とくに参照型を用いた柔軟なデータ構造を扱う場合には，基本的に再帰的アルゴリズムを用いるしかない． ここでは，再帰的アルゴリズムを詳細に検討し，その動作の理解をする

漸化式からの計算 階乗 フィボナッチ数列 いずれも再帰的に関数を呼ぶ形に書ける 再帰呼び出しの場合 f(0)やf(1)といった 　　　　　数列の最初の値のところで停止

末尾再帰なので再帰呼び出しをループに変換することは容易 階乗を求めるプログラム public class Factorial { // 再帰版 public static int factorial(int aTarget) { System.out.println("factorial(" + aTarget + ")に入ります"); if(0 == aTarget){ System.out.println("factorial(0) から出ます: 1"); return 1; } int total = aTarget * Factorial.factorial(aTarget - 1); System.out.println("factorial(" + aTarget + ") から出ます: " + total); return total; // ループ版 public static int factorialWithoutRecursion(int aTarget) { int total = aTarget; for(int count = aTarget - 1; 0 < count; count--){ total *= count; 末尾再帰なので再帰呼び出しをループに変換することは容易

f(0)から順にたどれば結果を求めることができる フィボナッチ数を求めるプログラム public class Fibonatti { // 再帰版 public static int fibonatti(int aTarget) { System.out.println("fibonatti(" + aTarget + ") に入ります"); if((0 == aTarget) || (1 == aTarget)){ System.out.println("fibonatti(" + aTarget + ") から出ます: 1"); return 1; } int total = fibonatti(aTarget - 2) + fibonatti(aTarget - 1); System.out.println("fibonatti(" + aTarget + ") から出ます: " + total); return total; // ループ版 public static int fibonattiWithoutRecursion(int aTarget) { int old1 = 1, old2 = 1, total = 0; for(int count = 2; count <= aTarget; count++){ total = old1 + old2; old2 = old1; old1 = total; f(0)から順にたどれば結果を求めることができる f(x)に必要とされるのはf(x-1)とf(x-2)なので変数を2つ追加すれば足る

[sakai@star 13]$ java FactorialTest 720 factorial(6)に入ります factorial(5)に入ります factorial(4)に入ります factorial(3)に入ります factorial(2)に入ります factorial(1)に入ります factorial(0)に入ります factorial(0) から出ます: 1 factorial(1) から出ます: 1 factorial(2) から出ます: 2 factorial(3) から出ます: 6 factorial(4) から出ます: 24 factorial(5) から出ます: 120 factorial(6) から出ます: 720 [sakai@star 13]$ [sakai@star 13]$ java FibonattiTest 8 fibonatti(5) に入ります fibonatti(3) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) から出ます: 3 fibonatti(4) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) に入ります fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(3) から出ます: 3 fibonatti(4) から出ます: 5 fibonatti(5) から出ます: 8 [sakai@star 13]$

通りがけ順の走査 二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 親の頂点に戻る 二分探索木を走査すると 横倒しの木を表示できる 29 29 20 20 32 32 14 14 24 24 30 30 48 48 7 7 19 19 21 21 31 31

木の根が左にある、 左から右へ生えている木を表示するプログラム public void printTreeRecursive() { this.printTreeRecursive(this.root, 0); } private void printTreeRecursive(MyNode aLocalRootNode, int depth) { if(null == aLocalRootNode) return; this.printTreeRecursive(aLocalRootNode.getRight(), depth+1); for(int i=0; i < depth; i++){ System.out.print("\t"); System.out.println(aLocalRootNode.getData().toString()); this.printTreeRecursive(aLocalRootNode.getLeft(), depth+1); 再帰呼び出し 再帰呼び出し版 木の根が左にある、 左から右へ生えている木を表示するプログラム (29, "リンゴ") (20, "ミカン") (14, "サクランボ") (32, "バナナ") (30, "イチゴ") (24, "ブルーベリー") ( 7, "グレープフルーツ") (21, "レモン") (48, "メロン") (31, "スイカ") (19, "ナシ") (17, "モモ") (23, "マンゴー") (28, "ブドウ") (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ)

this.printTreeRecursive((17, "モモ"), 4); 右部分木探索中 (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ) this.printTreeRecursive((17, "モモ"), 4); 右部分木探索中 this.printTreeRecursive((23, “マンゴー”), 4); 左部分木探索中 this.printTreeRecursive((23, "マンゴー"), 4);出力 this.printTreeRecursive((23, "マンゴー"), 4); 右部分木探索中 this.printTreeRecursive((17, “モモ”), 4); 左部分木探索中 this.printTreeRecursive((17, "モモ"), 4);出力 this.printTreeRecursive((31, “スイカ”), 3); 左部分木探索中 this.printTreeRecursive((28, "ブドウ"), 3);出力 this.printTreeRecursive((31, "スイカ"), 3);出力 this.printTreeRecursive((19, "ナシ"), 3);出力 this.printTreeRecursive((31, "スイカ"), 3); 右部分木探索中 this.printTreeRecursive((19, “ナシ”), 3); 左部分木探索中 this.printTreeRecursive((28, "ブドウ"), 3); 右部分木探索中 this.printTreeRecursive((28, “ブドウ”), 3); 左部分木探索中 this.printTreeRecursive((19, "ナシ"), 3); 右部分木探索中 this.printTreeRecursive(( 7, "グレープフルーツ"), 3);出力 this.printTreeRecursive(( 7, "グレープフルーツ"), 3); 右部分木探索中 this.printTreeRecursive(( 7, “グレープフルーツ”), 3); 左部分木探索中 this.printTreeRecursive((21, “レモン”), 3); 左部分木探索中 this.printTreeRecursive((21, "レモン"), 3);出力 this.printTreeRecursive((21, "レモン"), 3); 右部分木探索中 this.printTreeRecursive((24, “ブルーベリー”), 2); 左部分木探索中 this.printTreeRecursive((48, "メロン"), 2); 右部分木探索中 this.printTreeRecursive((24, "ブルーベリー"), 2); 右部分木探索中 this.printTreeRecursive((14, "サクランボ"), 2); 右部分木探索中 this.printTreeRecursive((30, "イチゴ"), 2); 右部分木探索中 this.printTreeRecursive((14, “サクランボ”), 2); 左部分木探索中 this.printTreeRecursive((30, “イチゴ”), 2); 左部分木探索中 this.printTreeRecursive((24, "ブルーベリー"), 2);出力 this.printTreeRecursive((48, "メロン"), 2);出力 this.printTreeRecursive((30, "イチゴ"), 2);出力 this.printTreeRecursive((14, "サクランボ"), 2);出力 this.printTreeRecursive((48, “メロン”), 2); 左部分木探索中 this.printTreeRecursive((20, “ミカン”), 1); 左部分木探索中 this.printTreeRecursive((20, "ミカン"), 1); 右部分木探索中 this.printTreeRecursive((20, “ミカン”), 1); 出力 this.printTreeRecursive((32, “バナナ”), 1); 左部分木探索中 this.printTreeRecursive((32, "バナナ"), 1); 右部分木探索中 this.printTreeRecursive((32, “バナナ”), 1); 出力 this.printTreeRecursive((29, “リンゴ”), 0); 左部分木探索中 this.printTreeRecursive((29, "リンゴ"), 0);出力 this.printTreeRecursive((29, "リンゴ"), 0); 右部分木探索中

再帰呼び出しの除去 再帰呼び出しでは同じ関数を呼ぶ 一時変数は、名前が同じだけで、実体は別 最も最後に呼ばれた関数が最初に抜ける 実体は関数エントリ時に確保される 関数から抜けるときに開放される 最も最後に呼ばれた関数が最初に抜ける つまりLIFO、スタック 一時変数や途中経過を退避する領域が あればループにより実現できる

退避すべきデータ 部分木の根 今何をしているか？ ループに変換するにはこれをスタックに退避 再帰呼び出しでは、プログラムの流れとして 保持していた。つまりCPUのプログラムカウンタ 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る ループに変換するにはこれをスタックに退避 探索中の頂点の深さは計算できるので退避不要

木の根が左にある、 左から右へ生えている木を表示するプログラム public void printTreeLoop() { MyNode node, currentRootNode = this.root; int depth = 0, todo = 0; Stack stack = new Stack(); while(true){ switch(todo++){ case 0: node = currentRootNode.getRight(); if(node != null){ stack.push(currentRootNode); currentRootNode = node; stack.push(new Integer(todo)); todo = 0; depth++; } break; case 1: for(int i=0; i < depth; i++){ System.out.print("\t"); System.out.println(currentRootNode.getData().toString()); // 続く… ループ版 木の根が左にある、 左から右へ生えている木を表示するプログラム

一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る case 2: node = currentRootNode.getLeft(); if(node != null){ stack.push(currentRootNode); currentRootNode = node; stack.push(new Integer(todo)); todo = 0; depth++; } break; case 3: if(stack.empty()){ return; todo = ((Integer)stack.pop()).intValue(); currentRootNode = (MyNode)stack.pop(); depth--; 一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る

JDK5での拡張forループ 配列・リスト・Setといった集合を楽に扱うための拡張 for(要素型名 要素型変数: 集合型変数){ http://java.sun.com/j2se/1.5.0/ja/docs/ja/guide/language/index.html for(要素型名　要素型変数: 集合型変数){ for文本体; } ListやSetや配列を表す変数 public static void main(String[] args) { int n; StringBuffer sb = new StringBuffer(); String[] data1 = test_data_string.clone(); n = sort(data1); for (String e : data1) { sb.append(e).append(", "); } sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n'); System.out.print(sb.toString()); 総称型については、次回にでも…