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

Slides:



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

4.3 マージソート.
ヒープソートの演習 第13回.
アルゴリズムとデータ構造 2012年6月27日
アルゴリズムとデータ構造1 2008年7月22日
アルゴリズムとデータ構造 第8回 ソート(3).
第11回 整列 ~ シェルソート,クイックソート ~
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
第9回 並び替えアルゴリズム ~さまざまなアルゴリズムを比較しよう~.
アルゴリズムとデータ構造 2012年7月23日
アルゴリズムとデータ構造 2012年6月14日
アルゴリズムとデータ構造 2011年6月13日
アルゴリズムとデータ構造 2011年7月14日
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
ヒープソートの復習.
アルゴリズムとデータ構造 2012年7月5日
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
二分探索木によるサーチ.
アルゴリズムとデータ構造 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日
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
アルゴリズムとデータ構造1 2005年7月1日
大岩 元 慶応大学環境情報学部 再帰 データ構造とプログラミング(8) 大岩 元 慶応大学環境情報学部
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング 4 整列アルゴリズム.
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
プログラミング 4 木構造とヒープ.
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
アルゴリズムとプログラミング (Algorithms and Programming)
AVL木.
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2011年6月16日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
ヒープソートの復習 第12回.
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月8日
平面走査法を使った 一般線分の 交点列挙アルゴリズム
アルゴリズムとデータ構造 2012年6月25日
ヒープソート.
ヒープソート.
アルゴリズムとデータ構造 2013年6月20日
アルゴリズムとデータ構造 2012年6月21日
参考:大きい要素の処理.
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

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

ヒープソート(185ページ) ソート前 ソート済み i length-1 挿入法では、ソート未完了の列から線形探索により i length-1 挿入法では、ソート未完了の列から線形探索により 次の挿入対象を探していた。 配列[i]の位置に、配列[0]から配列[i]までの間の 最大値を置くことを、配列末端から繰り返せばソートできる。 ただし、線形探索を毎回繰り返すのは効率が悪い。 比較回数の合計がおおむね

部分順序付き木(186ページ) 挿入法におけるソート前データ列から探索しやすいように データの置き方を工夫する。これまでの探索木のような順序木ではなく、 部分順序付き木というものにデータを置く。 データを置くルールは、親の値が子の値より小さくないこと。 そうすると、根には最大値が来る。 23 21 19 17 15 11 7 9 13 5 3 1 二分探索木ではないので、 このような配置でも問題ない

部分順序付き木の組み替え1 (原理的•187ページ) c a b d a c b d a f b e b a f e

ソートのための部分順序付き木 ソートのために特別なデータ構造を定義し使用することは非効率。 これを配列に置くことを考える。 木の高さがバランスしていないとソート途中の探索も非効率。 配列上のデータの並びから、一律に木の形を定義する。 配列[i]の子は、根を配列[0]とすると、配列[2*i+1]配列[2*i+2]になる。 教科書と違うことに注意。 23 21 19 1 2 17 15 11 7 3 4 5 6 9 3 13 5 1 7 8 9 10 11

配列に木を表現したことにする(188ページ) 13 21 19 9 5 11 7 17 3 15 23 1 根 2段目 3段目 4段目 根   2段目    3段目     4段目 木にバランスよくデータを置くには 配列上にあるデータ列を区切って 木に対応付けるとよい。 でも、部分順序付き木ですらない。 (このページの現状では…) 13 21 19 9 5 11 7 17 3 15 23 1

部分順序付き木の組み替え2 (ソート目的•190ページ) 木のバランスを崩さないように 頂点fを根に動かした。 根を取り除いた。 f e c a b d e c a f b d 根は配列[0]、fは配列の最後にある。 aとfを入れ替え e c d a b f e c f a b d dとfを入れ替え

(189ページから191ページ、手続きdownheap) 17 9 11 21 23 5 7 3 19 1 13 15 最初のヒープを作る (189ページから191ページ、手続きdownheap) 17 9 21 23 13 11 5 7 3 19 1 15 13 23 21 23 21 13 17 9 23 5 13 15 配列にデータを置いているので、 葉とその親の位置は計算で 一意に求まる。 そこで、葉に近いところから、 部分順序付き木のルールに 従ってデータをそろえていく。 (192ページ) 17 9 21 23 13 11 5 7 3 19 1 15 9 17 21 5 23 11 13 7 3 19 1 15 9 17 13 5 23 11 21 7 3 19 1 15 9 17 21 5 23 11 15 7 3 19 1 13 9 17 23 5 21 3 15 9 17 3 5 23 15

探しながら挿入法のようにソート(192・193ページ) 最大値を部分順序付き木から 探しながら挿入法のようにソート(192・193ページ) 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 最大値をソート済み列に加える。 未ソートデータ列の最後のデータを根に置く。 部分順序付き木になるようにデータを移動する。

lengthが奇数なら、2*x+2=length-1, x=(length-3)/2 public class HeapSort { private final static <E extends Comparable<E>> int downheap(E[] array, int root, int last){ int n = 0; E v = array[root]; while(true){ int j = 2*root+1; // 左の子 if(j > last) break; // 左の子がない(もちろん、右にも子がない)場合は終了 if(j != last){ // 両方の子がある n++; if(array[j+1].compareTo(array[j]) > 0) j++; // 右の子 > 左の子、大きいほうを選ぶ } if(v.compareTo(array[j]) >= 0) break; array[root] = array[j]; root = j; // 上→下 array[root] = v; return n; public static <E extends Comparable<E>> int sort(E[] array) { for(int i = array.length/2 - 1; i >= 0; i--) n += downheap(array, i, array.length - 1); //下→上 for(int i = array.length - 1; i > 0; i--){ E temp = array[0]; array[0] = array[i]; array[i] = temp; n += downheap(array, 0, i-1); }} xの子は2*x+1と2*x+2にあるので、 lengthが奇数なら、2*x+2=length-1, x=(length-3)/2 lengthが偶数なら、2*x+1=length-1, x=(length-2)/2

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

ヒープソートの計算量(193ページ) 完全2分木とすると、downheapで調べる 段数は、部分木の範囲ごとに次のようになる。 全体では、 全体では、                         とすると              だったので、 初期操作にはO(n)必要。 1段 n/4からn/2 2段 n/8からn/4 3段 n/16からn/8 4段 n/32からn/16

ヒープソートの計算量(つづき) 最大値を一つづつ取り出して、ソートする 作業では、 最大値を取り出す作業が 回  最大値を取り出す作業が  回  その後で木を作り替える作業が     回  つまり        になる。     

問題: 部分順序付き木を作り替える過程を記入しなさい。 アルゴリズムとデータ構造 演習 学生番号:           名前:                問題: 部分順序付き木を作り替える過程を記入しなさい。 23 21 19 1 17 15 11 7 21 19 9 3 13 5 1 17 15 11 7 1. 最初期のヒープ 9 3 13 5 23 2. 最大値を取り出し、未ソート配列より   値を取り出し、根に置く。 23 3. 途中経過

6. データ1個のソートが終わり、木の再構成も終わった状態。 23 4. 途中経過 23 21 5. 途中経過 17 19 9 15 11 7 1 3 13 5 23 6. データ1個のソートが終わり、木の再構成も終わった状態。

5 17 19 9 15 11 7 1 3 13 21 23 7. 2個目のデータのソート開始。 21 23 途中経過(必要に応じて使うこと) 21 23 途中経過(必要に応じて使うこと)

データ2個のソートが終わり、木の再構成も終わった状態。 21 23 途中経過(必要に応じて使うこと) 21 23 途中経過(必要に応じて使うこと) 21 23 データ2個のソートが終わり、木の再構成も終わった状態。