基本情報技術概論 I (第６回) アルゴリズム と データ構造 埼玉大学 理工学研究科 堀山 貴史 1 ソート アルゴリズム 計算量 基礎的なもの バブルソート (隣と交換) 選択ソート (最小値 or 最大値 を選択) 挿入ソート (未ソートの値を1つずつ挿入) 少し高速なもの 高速なもの O(n2) 単純な実装 O(n2) シェルソート (挿入ソートの改良版) もう少し速くできる クイックソート (交換で、基準値より 小さい値/大きい値に分ける) ヒープソート マージソート (ソート済リストをマージ） 最悪 O(n2) 平均 O(n log n) O(n log n) 2 基礎的なソートアルゴリズム 3 バブルソート (隣接交換法) 隣り合う値を見比べて、大小関係が逆なら交換 小 大 小 が バ ラ 大 バ ラ 20 30 5 10 1 20 30 5 見比べて 1 交換 10 1 20 30 5 10 1 20 5 30 10 20 30 1 5 10 1 確定 20 バ 30 ラ バ 5 ラ 10 20 1 30 5 10 1 5 確定 20 バ ラ 30 バ 10 ラ … 4 バブルソート n個 比較回数 n (n – 1) / 2 交換回数 最悪 n (n – 1) / 2 (隣接交換法) 計算量 1 20 30 5 10 確定 1 5 20 30 10 1 確定 5 10 20 30 １個目を確定させるのに ２個目 比較が n – 1 回 n–2回 確定 … 1 5 10 20 30 ３個目 … n - 1 個目 n–3回 … 1回 全部で O( n2 ) 5 バブルソート 開始 n→k (隣接交換法) 繰返し 1 20 30 5 10 k≦1 確定 1→i T( i+1) → w T( i ) → T( i+1) w → T( i ) 交 換 i=k > T(i), T(i+1) を交換 T(i)：T(i+1) ≦ i+1→i 1 5 20 30 10 確定 交 換 k-1→k 繰返し 終了 6 比較回数 n (n – 1) / 2 交換回数 最悪 n - 1 選択ソート 小 ソ ー ト 範 囲 大 ソ ー ト 範 囲 最小値 (or 最大値) を選択し、ソート範囲の先頭へ 20 30 5 10 1 最小値 の候補 比較 1 確定 最小値 30 の候補 5 10 20 20 30 5 10 1 1 30 5 10 20 最小値 の候補 最小値 の候補 20 30 5 10 1 20 30 5 10 1 交換 最小値 交換 最小値 7 比較回数 最悪 n (n – 1) / 2 交換回数 最悪 n (n – 1) / 2 挿入ソート 小 大 未 ソ ー ト 未ソートの値を挿入 20 30 5 10 1 5 20 30 10 1 挿入 10 挿入 20 30 5 10 1 5 20 30 1 5 挿入 10 挿入 20 30 10 1 5 10 20 30 1 5 挿入 1 挿入 8 高速なソートアルゴリズム 9 マージソート ソートされた２つの列 → １つにマージ（併合）するのは簡単 （各列の先頭を見比べながら、小さい方を取っていく） 5 20 25 50 (併合ソート） 1 10 30 40 １回のマージの実行時間は、要素数に比例 10 マージソート (併合ソート） 5 25 50 20 30 40 10 1 5 25 50 20 5 25 5 25 5 25 30 40 10 1 50 20 50 20 20 50 30 40 30 40 30 40 分割 10 1 10 log n 段 1 1 10 マージ log n 段 1 段に O( n ) 時間 → 全部で O( n log n ) 時間 クイックソート 5 25 50 20 30 40 10 1 基準値 は 20 (基準値の決め方は色々) 5 25 50 20 30 40 10 1 基準値 以上 5 基準値 以下 基準値 以上の値を左から 以下の値を右から 探して、交換 1 50 20 30 40 10 25 基準値 以上 5 交換 真ん中の位置の 値が基準値 交換 基準値 以下 1 10 20 30 40 50 25 基準値 以上 基準値 以下 12 クイックソート 基準値以下 5 基準値以上 1 10 20 30 40 50 25 基準値 以上 クイックソート 再帰的に クイックソート 基準値 以下 クイックソート ※ 基準値以上、基準値以下が、半分ずつの大きさに 分かれる保証は無い (大きさが偏ることもある) 13 シェルソート k = n/2 離れた要素の部分列を挿入ソート 5 25 50 20 30 40 10 1 5 25 50 20 30 40 10 1 5 25 50 20 30 40 10 1 5 25 10 20 30 40 50 1 5 25 10 1 30 40 50 20 14 シェルソート k = n/4 離れた要素の部分列を挿入ソート 5 25 10 1 30 40 50 20 5 25 10 1 30 40 50 20 5 1 10 20 30 25 50 40 ※ 25, 40 や 1, 20 はソートされているので、 25, 1, 40, 20 の挿入ソートは、 要素数４の一般の挿入ソートよりも 最悪の比較・交換回数が少なくて済む 15 シェルソート k = n/8 離れた要素の部分列を挿入ソート 5 1 10 20 30 25 50 40 1 5 10 20 25 30 40 50 ある間隔で要素を取り出した部分列をソートし、 さらに間隔をつめた部分列を取り出してソートする 16 前回の復習： ヒープソート ヒープの最大値の取り出し、ヒープの維持を繰り返す 7 1 6 5 6 3 2 4 1 最大値の取り出し 5 6 3 2 4 1 7 最後の葉の移動 3 7 2 4 ヒープの維持 4 6 3 5 5 7 1 2 4 最大値の取り出し 3 5 67 1 2 4 最後の葉の移動 3 1 5 67 2 ヒープの維持 17 前回の復習： ヒープソート ヒープの最大値の取り出し、ヒープの維持を繰り返す 7 6 1 5 6 3 2 4 1 最大値の取り出し 計算量 O( 1 ) 3 5 7 2 4 ヒープの維持 計算量 O( log n ) n 回 繰り返し … トータルの計算量 O( n log n ) 18 19 20 選択ソート 20 30 5 10 1 最大値 の候補 比較 (演習 2-02) 20 30 5 10 1 最大値を選択して、 大きい順にソートする 開始 交換 i = 1, 2, ..., n-1 最大値 の候補 i→k 最大値 j = i+1, i+2, ..., n > j→k X(j)：X(k) ≦ 最大値 X(k), X(j) を交換 交 換 終了 21 22 23 この教材のご利用について この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を 求めることなく、無償で自由にご利用いただけます。講義、自主学習は もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許 諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著 作者に帰属します。この教材、または翻訳や改変等を加えたもの を公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施 してください。なお、この教材に改変等を加えたものの著作権は、 次ページ以降に示す著作者および改変等を加えた方に帰属しま す。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する 場合には、頒布・再頒布の形態を問わず、このページの利用条件24 この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ この powerpoint ファイルの著作者 堀山 貴史 2007-2011 [email protected] 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 4, 8 クリップアート : Microsoft Office Online / クリップアート その他 堀山 貴史 25
© Copyright 2024 ExpyDoc
