スライド 1

アルゴリズムとデータ構造
補足資料8-2
「マージソートmerge.c」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：ストリーム：先頭から順に読む。（現在地を読み出せる）
最後尾に書く。（末尾に書き足せる）
入力列A
65 86 90 92
入力列B
63 70 85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：ストリーム：先頭から順に読む。（現在地を読み出せる）
最後尾に書く。（末尾に書き足せる）
入力列A
65 86 90 92
入力列B
63 70 85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：ストリーム：先頭から順に読む。（現在地を読み出せる）
最後尾に書く。（末尾に書き足せる）
出力列
入力列A
65 86 90 92
入力列B
70 85 85
63
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
出力列
入力列A
65 86 90 92
入力列B
70 85 85
63
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
86 90 92
63 65
入力列B
70 85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
86 90 92
63 65
入力列B
70 85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
86 90 92
63 65 70
入力列B
85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
86 90 92
63 65 70
入力列B
85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
86 90 92
63 65 70 85
入力列B
85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
86 90 92
63 65 70 85
入力列B
85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
86 90 92
63 65 70 85 85
入力列B
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
90 92
63 65 70 85 85 86
入力列B
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
90 92
63 65 70 85 85 86
入力列B
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
92
63 65 70 85 85 86 90
入力列B
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
92
63 65 70 85 85 86 90
入力列B
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
入力列A
出力列
63 65 70 85 85 86 90 92
入力列B
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
補足：入力のストリーム：先頭から順に読む。（現在地を読み出せる）
出力のストリーム：最後尾に書く。（末尾に書き足せる）
「マージ」の本質：
先頭から読んで（小さい方を）、末尾にくっつける
とりあえず、これでいいです。
が、
「ディスク」のように「順アクセス」は得意だが「ランダムアクセス」にはちと時間がかかる
デバイスで、順アクセスだけを使ってソートするには。。。
→サンプルプログラム
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
8件のデータ
65 90 85 70 86 92 63 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
8件のデータ
65 90 85 70 86 92 63 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
65 90 85 70
86 92 63 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
65 90 85 70
86 92 63 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
90 85 70
92 63 85
65 86
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
90 85 70
92 63 85
65 86
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
85 70
63 85
65 86
90 92
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
85 70
63 85
65 86
90 92
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
70
85
65 86
90 92
63 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
70
85
65 86
90 92
63 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
1個ずつのストリームとしてマージ！
65 86
63 85
90 92
70 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
できたストリームを
次の入力ストリームとする
65 86
63 85
90 92
70 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
65 86
63 85
90 92
70 85
2個ずつのストリームとしてマージ！
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
65 86
63 85
90 92
70 85
2個ずつのストリームとしてマージ！
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
65 86
63 85
90 92
70 85
2個ずつのストリームとしてマージ！
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
86
63 85
90 92
70 85
2個ずつのストリームとしてマージ！
65
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
63 85
2個ずつのストリームとしてマージ！
90 92
65 86
70 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
63 85
2個ずつのストリームとしてマージ！
92
65 86 90
70 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
63 85
2個ずつのストリームとしてマージ！
70 85
65 86 90 92
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
63 85
2個ずつのストリームとしてマージ！
70 85
65 86 90 92
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
85
2個ずつのストリームとしてマージ！
70 85
65 86 90 92
63
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
85
2個ずつのストリームとしてマージ！
85
65 86 90 92
63 70
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
2個ずつのストリームとしてマージ！
85
65 86 90 92
63 70 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
2個ずつのストリームとしてマージ！
65 86 90 92
63 70 85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
65 86 90 92
できたストリームを
次の入力ストリームとする
63 70 85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
65 86 90 92
4個ずつのストリームとしてマージ！
63 70 85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
65 86 90 92
4個ずつのストリームとしてマージ！
70 85 85
63
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
86 90 92
4個ずつのストリームとしてマージ！
70 85 85
63 65
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
86 90 92
4個ずつのストリームとしてマージ！
85 85
63 65 70
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
86 90 92
4個ずつのストリームとしてマージ！
85
63 65 70 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
86 90 92
4個ずつのストリームとしてマージ！
63 65 70 85 85
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
90 92
4個ずつのストリームとしてマージ！
63 65 70 85 85 86
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
92
4個ずつのストリームとしてマージ！
63 65 70 85 85 86 90
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
4個ずつのストリームとしてマージ！
63 65 70 85 85 86 90 92
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
マージソート
解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。
（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）
n件のデータ
未整列
未整列
未整列
log2 n
整列済
O(n x log n)

Download Report