酒居敬一(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.

Slides:



Advertisements
Similar presentations
山元進.  for 文  while 文  do ~ while 文  文のネスト  break 文  continue 文.
Advertisements

4.ソート 4-1.ソート問題について 4-2.簡単なソートアルゴリズム 4-3.高度なソートアルゴリズム
アルゴリズムとデータ構造 2012年6月27日
第12回 ソート(3): シェルソート、クイックソート
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造1 2008年7月22日
第10回 整列 ~ バブルソート,挿入ソート,選択ソート~
第11回 整列 ~ シェルソート,クイックソート ~
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
第9回 並び替えアルゴリズム ~さまざまなアルゴリズムを比較しよう~.
第10回 ソート(1):単純なソートアルゴリズム
アルゴリズムとデータ構造 2012年7月23日
アルゴリズムとデータ構造 2012年6月14日
アルゴリズムとデータ構造 2011年6月13日
データ構造とアルゴリズム 分割統治 ~ マージソート~.
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
アルゴリズムとデータ構造 2011年7月14日
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2012年7月5日
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
アルゴリズム入門.
第11回 整列 ~ シェルソート,クイックソート ~
アルゴリズムとデータ構造 2011年6月30日
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
オブジェクト指向 プログラミング 第十一回 知能情報学部 新田直也.
オブジェクト指向 プログラミング 第十三回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
アルゴリズムとデータ構造1 2005年7月15日
アルゴリズムとプログラミング (Algorithms and Programming)
わんくま同盟茶藝部顧問 Microsoft MVP for VC episthmh
アルゴリズムとデータ構造1 2005年7月1日
大岩 元 慶応大学環境情報学部 再帰 データ構造とプログラミング(8) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2012年7月17日
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとプログラミング (Algorithms and Programming)
復習+α JBuilderの使い方を思い出す。 配列とGUI 再帰とマージソート 木と二分木の探索
プログラミング 4 整列アルゴリズム.
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造 2010年7月26日
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
アルゴリズムとデータ構造 2012年6月25日
アルゴリズムとデータ構造 2012年6月21日
参考:大きい要素の処理.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

酒居敬一(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());

単純な整列アルゴリズム (147ページ) 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, 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; 単純な整列アルゴリズム (147ページ) 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 21 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 91

選択法 (149ページ) 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, 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; 選択法 (149ページ) 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 21 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 91

バブルソート (149ページ) > 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

挿入法 (150ページ) 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

シェルソート (156ページ) 以上で整列おわり!… 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