アルゴリズムB 第2回


マージ(merge)操作

マージ

マージ (merge) ... 「整列済みの2個のデータ列を、整列済みの1個のデータ 列にまとめ上げる操作」のこと。

整列済みの列 a と b の先頭の要素を比較し、小さい方を元の列から取り除いて、 新しい列cの末尾に追加します。 どちらかの入力列が無くなったら、残っている方を一度に列cの末尾に追加します。

マージのアルゴリズム

    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 作業用配列が必要なことに注意

MergeSortArray.java
授業で配布するプリントを参照して下さい。
MergeSortArray.javaの実行例
% 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 

マージソートの性質


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

アルゴリズム計算量定数項メモリ使用量有利/不利
クイックソートO(n log n)小さいスタック O(log n)有利
マージソートO(n log n)大きい配列のコピー O(n)不利

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

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

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

外部整列

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

なので、データにはシーケンシャルにアクセスせざるを得ない。 その場合は、整列アルゴリズムとしてはマージソートを使う。

p.353 Fig.15.5 参照。



アルゴリズムB 演習


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

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

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

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

提出ファイルMergeSortArray.java
コメント欄:rand400k.txt, inc400k.txt, dec400k.txtそれぞれに対する計算時間
提出先: 「宿題提出Web:アルゴリズムB:課題2a」 http://nw.tsuda.ac.jp/class/algoB/local/handin/up.php?id=kadai2a

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

を処理するのに必要な時間をそれぞれ計測し、答えなさい。

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

提出ファイルMergeIterator.java と RunMergeIterator.java
コメント欄:小さい方から5000番目、160000番目、1234567番目のデータ
提出先: 「宿題提出Web:アルゴリズムB:課題2b」 http://nw.tsuda.ac.jp/class/algoB/local/handin/up.php?id=kadai2b

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

http://nw.tsuda.ac.jp/class/algoB/mergedata0.txt
http://nw.tsuda.ac.jp/class/algoB/mergedata1.txt
http://nw.tsuda.ac.jp/class/algoB/mergedata2.txt
http://nw.tsuda.ac.jp/class/algoB/mergedata3.txt
http://nw.tsuda.ac.jp/class/algoB/mergedata4.txt
http://nw.tsuda.ac.jp/class/algoB/mergedata5.txt
http://nw.tsuda.ac.jp/class/algoB/mergedata6.txt
http://nw.tsuda.ac.jp/class/algoB/mergedata7.txt
http://nw.tsuda.ac.jp/class/algoB/mergedata8.txt
mergedata0.txtの抜粋(最初から数行)
授業で配布するプリントを参照して下さい。
...(略)
mergedata1.txtの抜粋(最初から数行)
授業で配布するプリントを参照して下さい。
...(略)

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

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

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

NetIterator.java
授業で配布するプリントを参照して下さい。
MergeIterator.java
授業で配布するプリントを参照して下さい。
RunMergeIterator.java
授業で配布するプリントを参照して下さい。
RunMergeIterator.javaの実行例
% javac RunMergeIterator.java
$ java RunMergeIterator 50
54
$ java RunMergeIterator 10000
9918
$ java RunMergeIterator 200000
199718