第11回 整列 ~ シェルソート,クイックソート ~

Slides:



Advertisements
Similar presentations
4.3 マージソート.
Advertisements

プログラムのパタン演習 解説.
離散システム特論 整列(sorting)アルゴリズム 2.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
ヒープソートの演習 第13回.
アルゴリズムイントロダクション第2章 主にソートに関して
4.ソート 4-1.ソート問題について 4-2.簡単なソートアルゴリズム 4-3.高度なソートアルゴリズム
アルゴリズムとデータ構造 2012年6月27日
第12回 ソート(3): シェルソート、クイックソート
高速ソートと 安定結婚問題 平成24年12月14日.
アルゴリズムとデータ構造 第8回 ソート(3).
第10回 整列 ~ バブルソート,挿入ソート,選択ソート~
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
2009/10/30 整列アルゴリズム (2) 第5講: 平成21年10月30日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
4-3:高度なソートアルゴリズム① (分割統治法にもとづくソート)
アルゴリズムとデータ構造 第6回演習解答 2015/11/18実施 アルゴリズムとデータ構造 2015.
4.整列のアルゴリズム.
第10回 ソート(1):単純なソートアルゴリズム
情報工学概論 (アルゴリズムとデータ構造)
情報処理Ⅱ 2005年12月9日(金).
担当:青木義満 情報工学科 3年生対象 専門科目 システムプログラミング システムプログラミング プロセス間通信(パイプ) 担当:青木義満
データ構造とアルゴリズム 分割統治 ~ マージソート~.
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
ヒープソートの復習.
第11回 整列 ~ シェルソート,クイックソート ~
算法数理工学 第1回 定兼 邦彦.
2009/11/6 整列アルゴリズムの復習 第6講: 平成21年11月6日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造1 2006年6月16日
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造1 2005年7月15日
ソートアルゴリズムの種類 選択ソート (selection sort) バブルソート (bubble sort)
情報工学概論 (アルゴリズムとデータ構造)
講義では、Cプログラミングの基本を学び 演習では、やや実践的なプログラミングを通して学ぶ
わんくま同盟茶藝部顧問 Microsoft MVP for VC episthmh
データ構造とアルゴリズム論 第6章 整列(ソート)のアルゴリズム
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2005年7月1日
クイックソート.
大岩 元 慶応大学環境情報学部 再帰 データ構造とプログラミング(8) 大岩 元 慶応大学環境情報学部
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
アルゴリズムとプログラミング (Algorithms and Programming)
先進的計算基盤システムシンポジウム SACSIS2007併設企画 マルチコアプログラミングコンテスト 「Cellスピードチャレンジ2007」
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング 4 整列アルゴリズム.
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング 4 探索と計算量.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング 4 木構造とヒープ.
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
プログラミング演習Ⅲ- Sorting Quick Sort and Merge Sort
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとプログラミング (Algorithms and Programming)
バブルソート,バケツソート,クイックソート
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
ヒープソートの復習 第12回.
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 2013年7月2日
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
アルゴリズムとデータ構造 2012年6月25日
ヒープソート.
参考:大きい要素の処理.
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

第11回 整列 ~ シェルソート,クイックソート ~ データ構造とアルゴリズム 第11回 整列 ~ シェルソート,クイックソート ~

問1 解答例1 (抽象的な説明例) 4 7 5 6 B [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 4 問1 解答例1 (抽象的な説明例) 4 7 5 6 A [0] [1] [2] [3] [4] 5個の整数が配列Aに格納 されているものとする バケットBにデータを格納する B [0] [1] [2] [3] [4] A[0] A[2] A[3] A[1] A[4] [5] [6] [7] [8] [9] バケットの先頭から順に 取り出し、配列Aに戻す 4 5 6 7 A’ [0] [1] [2] [3] [4]

問1 解答例2 (ポインタを用いた実装を想定した例) 問1 解答例2 (ポインタを用いた実装を想定した例) バケットBにデータを格納する 4 7 5 6 A [0] [1] [2] [3] [4] B [0] [1] [2] [3] [4] A[0] [5] A[2] [6] A[3] バケットの先頭から順に取り出し、配列Aに戻す [7] A[4] A[1] 4 5 6 7 A’ [0] [1] [2] [3] [4] [8] [9]

問2 解答 問1:94.3%, 問2:95.8% 1回目 2回目 3回目 K I D F A N A N Y F A N K I D B U T B U T A N Y F A N A N Y B U T K I D 問1:94.3%, 問2:95.8%

復習1 O(n2)のソート 配列の後ろから先頭に向かってスキャンし,隣り合う2つの要素の大小関係が逆であったら入れかえる 未ソート 配列の後ろから先頭に向かってスキャンし,隣り合う2つの要素の大小関係が逆であったら入れかえる 現在処理対象となっているデータを,整列済みのデータ列内の適切な位置に挿入する 整列されていない部分から最小要素を選び,先頭と入れかえる処理を繰り返す 1 3 5 9 10 7 20 17 6 3 5 8 10 11 7 ソート済 未ソート 1 3 5 9 10 7 20 17 18 入れかえ 最小値

復習2   A[2] A[0] A[4] A[1] A[3] 1 4 6 2 配列 A バケットB [1] [2] [3] [4] [0] [5] [6]            O(n) 値kの要素を入れる箱(バケットB[k]、ただし、kは0≦k≦m-1)を準備し、各要素A[i]をB[A[i]]に入れたあと、バケットの中身を連結する            O(n) 整列対象となるキーを,いくつかのサブキーに分割し,下位から上位の順に,サブキーをもとに安定な整列を行う            O(n log n) ヒープを用いてデータの整列を行う B U T K I D A N Y F A N F A N B U T A N Y K I D 2 4 7 13

本日の内容 シェルソート クイックソート

シェルソート (p.109)

シェルソート(Shell sort) 1959年に D. L. Shellが発表したアルゴリズム 挿入ソートを変形 安定ではない

シェルソートの原理 55 74 3 45 13 87 46 30 離れたデータの組を挿入ソートで整列し,順次,要素間の距離を減らして整列を繰り返す 4つずつ離れたデータの組 13 74 3 30 55 87 46 45 右の例は4, 2, 1と間隔を減らしている 2つずつ離れたデータの組 …,121,40, 13, 4, 1ならばO(n1.25) 3 30 13 45 46 74 55 87 (3k−1)/2 k=1,2,3・・・  (Knuthの解析実験) 1つずつ離れたデータの組 …,15, 7, 3, 1ではO(n1.5) 3 13 30 45 46 55 74 87 2k−1 k=1,2,3・・・ 整列終了

練習問題 以下のデータをシェルソートで昇順に整列しなさい 整列の間隔は4、2、1の順で減らすこと。 10, 5 , 4, 27, 2, 6, 3, 20, 1, 0, 8, 9, 7, 23, 13, 42

解答    10 5 4 27 2 6 3 20 1 0 8 9 7 23 13 42 4ずつ離れたものをソートした結果 1 0 3 9 2 5 4 20 7 6 8 27 10 23 13 42 1 0 3 9 2 5 4 20 7 6 8 27 10 23 13 42 2ずつ離れたものをソートした結果 1 0 2 5 3 6 4 9 7 20 8 23 10 27 13 42 1ずつ離れたものをソートした結果 0 1 2 3 4 5 6 7 8 9 10 13 20 23 27 42

クイックソート (p.96~)

(quick sort) 1962年に C. A. R. Hoareが発表したアルゴリズム 内部整列アルゴリズムの中で最速 不安定な整列アルゴリズム ただし,最悪の場合O (n2)

クイックソートの原理 ソートする範囲のデータから適当な軸要素(枢軸、pivot)νを選ぶ。 クイックソートの原理  ソートする範囲のデータから適当な軸要素(枢軸、pivot)νを選ぶ。 要素をひとつずつ調べて、νより小さいグループと大きいグループに     する。 小グループと大グループ各々に上記1.と2.を適用する。 各々のグループが分割できなくなるまで分割を繰り返す。 大きな問題を小さな問題に分けて解決していく ⇒ 分割統治(divide and conquer)

クイックソートの疑似コード void quicksort(int l, int r, int A[]) { int k; /* 枢軸より大きい部分の開始位置 */ 軸要素を決める; if (キーがすべて同じ) 終了; vより小さい部分と大きい部分に分割し, 大きい部分の先頭の位置kを返す; quicksort(l, k – 1,A); /* 小さい部分を整列 */ quicksort(k, r, A); /* 大きい部分を整列 */ }

軸要素(pivot)の選び方 方法1) データの中からランダムに一つ選ぶ。 方法2) ランダムに3要素選びその中央値をとる。 方法1) データの中からランダムに一つ選ぶ。 方法2) ランダムに3要素選びその中央値をとる。 方法3) 左からみて最初に得られた二つの異なる値        の大きい方をとる。 ポイント: 小さい部分と大きい部分の要素数が                        .

partition()のループ変数 i, j がl~rの範囲を超えないことが保証される pivot 軸要素の位置を返す関数  int pivot(int i, int j, int A[ ]) { int pv, k; k = i + 1; while(A[i] == A[k] && k <= j) k++; if (k > j) pv = -1; /* キーが全て同じ */ else if (A[i] >= A[k]) pv = i;   else pv = k; return(pv); } i k → j A 4 6 5 3 枢軸未満のキー 枢軸以上のキー が必ずそれぞれ1つ以上ある ↓ partition()のループ変数 i, j がl~rの範囲を超えないことが保証される

分割の手順 要素が軸要素 v より小さい限り l を右へ、 要素が v 以上である限り r を左へ動かす A l, r : カーソル 分割の手順  要素が軸要素 v より小さい限り l を右へ、   要素が v 以上である限り r を左へ動かす i l r j A l, r : カーソル v : 枢軸

分割の手順(続き) l <= r なら 1.に戻る A l > r なら分割終了 A i j l r i j l r キー<ν 分割の手順(続き)  l <= r なら                   1.に戻る l > r なら分割終了 キー>ν キー<ν i j l r A i j l r A それぞれの部分に対して 再帰的に処理をくりかえす

分割手順の疑似コード int partition(int i, int j, int v, int A[]) { int l = i, r = j, k; for(;;){ while (A[l] < v) l++; while (A[r] >= v) r--; if(l <= r){ A[l]とA[r]を交換;lとrを1つ移動; } else ループから抜ける; k = l; return k;

v = 3の場合 l→ ←r 3 1 4 5 9 2 6 Start (1) 2 1 4 5 9 3 6 (2) A[0] A[1]

各々のグループをさらに分割 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 2 1 4 5 9 3 6 レベル2 v=2 1 2 v=5 4 3 9 6 5 1 2 終了 4 3 9 6 5 レベル3 v=4 3 4 v=9 5 6 9 キーが 全て同じ 3 4 終了 5 6 9 終了 レベル4 v=6 5 6 5 6 終了 レベル5 ソート終了

クイックソートの計算時間

最悪の場合 比較回数 7 6 5 4 3 2 1 → O ( n 2 )

まとめ バブルソート O(n2) 挿入ソート 選択ソート クイックソート O(n log n) ヒープソート O(n log n) 名称 計算量 内部/外部 安定/不安定 備考 バブルソート O(n2) 内部 安定 挿入ソート 選択ソート 不安定 クイックソート O(n log n)  最悪O(n2) ヒープソート O(n log n) マージソート 外部 ビンソート O(n) データに制限有 基数ソート O(mn)

今後の予定 7/23 ヒープソートの演習(2階電算室に集合) 7/30 期末試験(掲示をよく見ること)     10:30〜12:00 場所は921

本日の問題 (問1) i=0, j=9, 軸要素v = 4の場合、関数partitionを実行すると配列の中身がどのように変化していくかを書け。また、分割終了時の l と r は各々いくつか。 1 2 3 4 5 6 7 8 9 3 1 4 5 9 2 6 Start (1) (2) (3)