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

整列（ソート） 配列を使用するソートアルゴリズム 空間計算量はいずれも 挿入法 バブルソート シェルソート クイックソート 時間計算量 時間計算量は最悪でも 空間計算量はいずれも

テストデータとテスト用メソッド 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());

単純な整列アルゴリズム （１４７ページ） 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, public class SimpleSort { public static <E extends Comparable<E>> int sort(E[] array) { int n = 0; for(int i = 0; i < (array.length - 1); i++){ for(int j = i+1; j < array.length; j++){ n++; if(array[j].compareTo(array[i]) < 0){ E tmp = array[j]; array[j] = array[i]; array[i] = tmp; } return n; 単純な整列アルゴリズム （１４７ページ） 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 21 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 91

選択法 （１４９ページ） 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 21 public class SelectionSort { public static <E extends Comparable<E>> int sort(E[] array) { int n = 0; for(int i = 0; i < (array.length - 1); i++){ int minpos = i; for(int j = i+1; j < array.length; j++){ n++; if(array[j].compareTo(array[minpos]) < 0){ minpos = j; } E tmp = array[minpos]; array[minpos] = array[i]; array[i] = tmp; return n; 選択法 （１４９ページ） 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 21 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 91

バブルソート （１４９ページ） ＞ 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

兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 18 public class BubbleSort { public static <E extends Comparable<E>> int sort(E[] array) { int n = 0; boolean isChanged = false; int limit = array.length - 1; while (true) { isChanged = false; for (int count = 0; count < limit; count++) { if (array[count].compareTo(array[count + 1]) > 0) { E temp = array[count]; array[count] = array[count + 1]; array[count + 1] = temp; isChanged = true; } n++; limit--; if (!isChanged) break; return n; 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 18 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 81

挿入法 （１５０ページ） 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 24 12 1 6 32 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 32 12 1 6 24 以上で整列おわり！… 10 1 8 3 15 5 32 12 6 24

兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 14 public class InsertionSort { public static <E extends Comparable<E>> int sort(E[] array) { int n = 0; for(int i = 1; i < array.length; i++){ E w = array[i]; int j = i - 1; while((j >= 0) && w.compareTo(array[j]) < 0){ array[j+1] = array[j]; j--; n++; } array[j+1] = w; return n; 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 14 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 59

シェルソート （１５６ページ） 以上で整列おわり！… 10 1 8 3 15 5 32 12 6 24 10 8 3 15 5 32 12

兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 17 public class ShellSort { public static <E extends Comparable<E>> int sort(E[] array) { int n = 0; int h; for(h = 1; h < array.length; h = h*3 + 1); // nより小さい範囲で最大のhを求める while(h > 1){ h /= 3; for(int i = h; i < array.length; i++){ E w = array[i]; int j = i - h; n++; while((j >= 0) && w.compareTo(array[j]) < 0){ array[j+h] = array[j]; j -= h; } array[j+h] = w; return n; 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 17 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 53

シェルソートの計算量 を とすると最悪時間計算量が になる。 をうまく選ぶと 最悪時間計算量 になる。 　　を とすると最悪時間計算量が　　　　　　になる。 　　をうまく選ぶと 最悪時間計算量　　　　　　になる。 　　を とすると平均時間計算量が　　　　　　　になる。

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

線形なデータ構造における整列(ソート) 比較によるもの バブルソート クイックソート マージソート 比較によらないもの ビンソート

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

アルゴリズムとデータ構造 演習 学生番号： 名前： 元のデータ 0-4-8をソート 1-5-9をソート (2-6をソート、)3-7をソート アルゴリズムとデータ構造　演習 学生番号：　　　　　　　　　　　　　　　　 　　　名前：　　　　　　　　　　　　　　　　 元のデータ 10 8 3 15 5 32 12 1 6 24 0-4-8をソート 10 8 3 1 5 32 12 15 6 24 1-5-9をソート 10 8 3 1 5 32 12 15 6 24 (2-6をソート、)3-7をソート 6 8 3 15 5 24 12 1 10 32 挿入法でソート 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 32 12 1 6 24 問題：　元のデータがシェルソートで h=7, 3, 1 で順にソートされてゆくとき、 その途中経過を書きなさい。 10 8 3 15 5 32 12 1 6 24 10 8 3 15 5 32 12 1 6 24 ソート完了 10 8 3 15 5 32 12 1 6 24

10 8 3 15 5 32 12 1 6 24