スライドタイトルなし

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

Download Report