アルゴリズムb 第6回

マージ(merge)操作

マージのアルゴリズム

    a ←マージの対象となるデータ列
    b ←マージの対象となるデータ列
    c ←マージの結果として得られるデータ列
    while (aが空でない && bが空でない) {
      if (aの先頭の要素 <= bの先頭の要素) {
        aの先頭の要素を取り除いてcの最後に追加する
      } else {
        bの先頭の要素を取り除いてcの最後に追加する
      }
    }
    if (aが空でない) {
      aの残りの要素を全てその順番のままcの最後に追加していく
    } else if (bが空でない) {
      bの残りの要素を全てその順番のままcの最後に追加していく
    }

マージ操作の例

a:{30,50,80}, b:{10,20,70}という2つのデータ列から マージ操作によって新しいデータ列cをつくり出すときの 動作を以下の図に示します。

マージソート

計算量は O(n log n) でクイックソートと同じですが、 定数係数が大きいためクイックソートより遅くなります。

ただし、 要素をシーケンシャルに（前から後ろに順番通りに）アクセスするので、 連結リストや外部記憶上のデータを整列するのに適しています。

[1] データ列を真中で2つの部分列aとbに分割する。
[2] 部分列 a と b をそれぞれ整列する。
[3] 整列済みになった部分列 a と b をマージする。

配列によるマージソート

プログラム例 p.338 List.15.3 作業用配列が必要なことに注意

% javac MergeSortArray.java   
% java MergeSortArray -d   
データの個数を入力して下さい  8   
5 2 7 4  8 1 6 3   
low=0, high=1, mid=0: 2 5 7 4 8 1 6 3 
low=2, high=3, mid=2: 2 5 4 7 8 1 6 3 
low=0, high=3, mid=1: 2 4 5 7 8 1 6 3 
low=4, high=5, mid=4: 2 4 5 7 1 8 6 3 
low=6, high=7, mid=6: 2 4 5 7 1 8 3 6 
low=4, high=7, mid=5: 2 4 5 7 1 3 6 8 
low=0, high=7, mid=3: 1 2 3 4 5 6 7 8 
1 2 3 4 5 6 7 8 

マージソートの性質

• 分割(1)〜(4)
$\log_2 n$ 回の分割。毎回長さが半分になる。 $1$ 回の分割に必要な計算量は $O(1)$ 〜 $O(n)$。
• マージ(4)〜(7)
$\log_2 n$ 回のマージ。毎回長さが倍になる。 $1$ 回のマージに必要な計算量は $O(n)$。

したがって、マージソートの計算量は $O(n \log n )$ である。

マージの際に値が等しい要素について、最初の位置関係を保つようにすれば、 安定なソートとなる。

連結リストによるマージソート

リンクのつなぎ変えでいいので、要素のコピーが必要なくなる。 p.346 List 15.4, List 15.5

外部整列

データが(ハードディスクやCDなどの)２次記憶上にある (すなわち、メモリ上に無い)場合、

• アクセス時間が遅い
• 入出力はブロック単位
• ランダムアクセスはできない(or 非常に遲い)

p.353 Fig.15.5 参照。

アルゴリズムB 演習

作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。

提出した後は、正しく提出されていることを http://ynitta.com/class/algoB/local/handin/ で必ず確認しておいて下さい。

提出〆切は次回の講義の開始時刻です。

課題6a: MergeSortArrayのプログラムを動かしてみよう

MergeSortArray.java が、 課題1で使った http://ynitta.com/class/algoB/sortdata/の下の 3種類のデータ

• rand400k.txt -- 400000個のデータがランダムに並んでいる
• inc400k.txt -- 400000個のデータが昇べきの順に並んでいる
• dec400k.txt -- 400000個のデータが降べきの順に並んでいる

課題6b: ネット経由のマージ

行毎に整数値を保持する9個のファイルがあり、それぞれのファイルの中では 整数値は小さい順にソートされているものとします。 (注: 大きいファイルなのでダウンロードする必要はありません。)

https://ynitta.com/class/algoB/mergedata0.txt
https://ynitta.com/class/algoB/mergedata1.txt
https://ynitta.com/class/algoB/mergedata2.txt
https://ynitta.com/class/algoB/mergedata3.txt
https://ynitta.com/class/algoB/mergedata4.txt
https://ynitta.com/class/algoB/mergedata5.txt
https://ynitta.com/class/algoB/mergedata6.txt
https://ynitta.com/class/algoB/mergedata7.txt
https://ynitta.com/class/algoB/mergedata8.txt

2
2
7
7
7
...

5
19
26
28
30
...

これら全体を通して小さい方からn番目のデータを表示する プログラム RunMergeIterator.java, MergeIterator.java, NetIterator.java を考えます。

MergeIterator.javaの中の欠けている部分のコードを自分で書いて下さい。

(注意) この問題では「1番目のデータ」という用語が「最初のデータ」を 表すものとします。すなわち、0番から数えるわけではありません。

% javac RunMergeIterator.java   
$ java RunMergeIterator 50   
54
$ java RunMergeIterator 10000   
9918
$ java RunMergeIterator 200000   
199718