データ構造とアルゴリズム 分割統治 ～ マージソート～
本日の内容 分割統治 マージソート
分割統治(divide-and-conquer) もとの問題を小規模な部分問題に分割した後に解き、部分問題の解を統合することで全体の解を得ようとする方法 分割の対象は、変数の集合や定義領域 再帰的に反復して実行される 例） クイックソート、マージソート
クイックソート 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 ソート終了
マージソート(merge sort)(p.120) マージ(併合)を利用してデータを整列 要素をシーケンシャルアクセスしながら整列可能 →連結リストや外部記憶上のデータの整列に利用可 （外部整列，外部ソート） 計算量 常にO (n log n) 整列済のデータ列ｘ, ｙをマージ 5 9 18 x 3 5 9 13 18 a 3 13 y
マージソートの原理 データ列を真ん中で2つの部分列ｘ, yに分割 部分列x, yをそれぞれ整列する 整列済みの部分列x, yをマージする 分割統治 データ列を真ん中で2つの部分列ｘ, yに分割 部分列x, yをそれぞれ整列する 整列済みの部分列x, yをマージする
マージソートの疑似コード void merge_sort(int a[], int l, int r) { int middle; if (要素が1つ以下) 終了; middle = (l + r) / 2; /*中央位置を算出*/ merge_sort(a, l, middle); /*前半を整列*/ merge_sort(a, middle + 1, r); /*後半を整列*/ 前半と後半をマージする; }
マージソートの概念図 55 13 3 45 74 87 46 30 分割 55 13 3 45 74 87 46 30 分割 55 13 3 45 74 87 46 30 分割 55 13 3 45 74 87 46 30 マージ 13 55 3 45 74 87 30 46 マージ 3 13 45 55 30 46 74 87 マージ 3 13 30 45 46 55 74 87
クイックソートとの比較 クイックソート O(n log n) 最悪でO(n2) マージソート O(n log n) 軸vより小さい部分と大きい部分になるように入れかえる 分割する 分割した部分に対して再帰的に処理を行う O(n log n) 最悪でO(n2) マージソート 分割する 分割した部分に対して再帰的に処理を行う マージする O(n log n) 配列で実装する場合，作業用のメモリ領域が余分に必要（教科書では配列Ａ１，Ａ２）
マージソートの問題点 配列を用いて実装する場合，作業用の領域として整列するデータと同じ大きさの領域が必要 作業用の配列にコピーする手間が無視できない a 5 9 18 3 13 20 コピー 作業用配列 A1 5 9 18 A2 3 13 20 マージ a 3 5 9 13 18 20
外部整列（外部ソート，external sort） ※ 外部記憶上のデータを整列すること 内部記憶 外部記憶 アクセス速度 高速 低速 容量 小 大 アクセス方式 ランダム シーケンシャル(磁気テープ) (磁気ディスク) 内部記憶 (メモリ) 外部記憶 (磁気テープなど) 整列したい データ ２ ５ １ ６ ７ １０ ４０ ３ ４ ３５ 入りきらない
マージソートを利用した外部整列※ 長さ２の連 (run)にまとめる テープ１： 28 3 93 10 54 65 30 テープ１： 28 3 93 10 54 65 30 テープ２： 31 5 96 40 85 9 テープ３： テープ４： 28 31 93 96 54 85 30 3 5 10 40 9 65 長さ４の連 (run)にまとめる テープ１： テープ２： 3 5 28 31 9 54 65 85 10 40 93 96 30
マージソートを利用した外部整列（続き） 長さ８の連 (run)にまとめる テープ３： テープ４： 3 5 10 28 31 40 93 96 30 54 65 85 長さ16の連 (run)にまとめる テープ１： テープ２： 3 5 9 10 28 30 31 40 54 65 85 93 96
整列アルゴリズムの分類 バブルソート O(n2) 挿入ソート 選択ソート クイックソート O(n log n) ヒープソート 名称 計算量 内部/外部 安定/不安定 備考 バブルソート O(n2) 内部 安定 挿入ソート 選択ソート 不安定 クイックソート O(n log n) 最悪O(n2) ヒープソート O(n log n) マージソート 外部 ビンソート O(n) データに制限有 基数ソート O(mn)