| 目次 | 索引 |
|---|---|
h2 併合整列法 toc-merge-sort
h3 リストの併合 toc-list-merging
index 併合 merging へいこう
とは、
複数の整列済みの数列をまとめて、1 つの整列済みの数列を作ることです。
ここでは、特に 2 つの数列を 1 つにまとめることを考えます。
2 つの数列を併合するには、まず、双方の先頭要素を比較し、
小さい方を結果の先頭に移動します。
次に、残りの先頭要素を比較し、小さい方を結果の先頭の次に移動します。
この移動を繰り返し、もし一方の要素がなくなったら、
他方の残りをすべて結果の最後に移動します。
併合は、配列に対してもできますが、リストのほうが向いています。
ここで、リストのクラスは、前回と同じものを用います。
class IntList {
int first;
IntList rest;
IntList (int first, IntList rest) {
this.first = first;
this.rest = rest;
}
}
次のプログラムは、リスト [1, 3] と [2, 4] を併合して、
リスト [1, 2, 3, 4] を作るものです。
class ListMerge {
public static void main (String[] args) {
int DUMMY = 0;
IntList lst1, lst2, lst, head;
lst1 = new IntList(DUMMY, null);
lst1.rest = new IntList(1, null);
lst1.rest.rest = new IntList(3, null);
lst2 = new IntList(DUMMY, null);
lst2.rest = new IntList(2, null);
lst2.rest.rest = new IntList(4, null);
lst = lst1;
head = lst;
lst1 = lst1.rest;
lst2 = lst2.rest;
while (lst1 != null && lst2 != null) {
if (lst1.first <= lst2.first) {
lst.rest = lst1;
lst = lst.rest;
lst1 = lst1.rest;
} else {
lst.rest = lst2;
lst = lst.rest;
lst2 = lst2.rest;
}
}
if (lst1 == null) {
lst.rest = lst2;
} else {
lst.rest = lst1;
}
System.out.println(head.rest.first);
System.out.println(head.rest.rest.first);
System.out.println(head.rest.rest.rest.first);
System.out.println(head.rest.rest.rest.rest.first);
}
}
併合のイメージは次の通りです。
+-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | |
|dummy| *--+---->| 1 | *--+---------------------->| 3 |null |
+-----+-----+ +-----+-----+ +-----+-----+
+-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | |
|dummy| *--+---------------------->| 2 | *--+---------------------->| 4 |null |
+-----+-----+ +-----+-----+ +-----+-----+
+-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | |
|dummy| *--+---->| 1 | *--+--+ +->| 3 | *--+--+
+-----+-----+ +-----+-----+ | | +-----+-----+ |
| | |
+-----+-----+ | +-----+-----+ | | +-----+-----+
| | | +->| | | | | | | |
|dummy| *--+---------------------->| 2 | *--+--+ +->| 4 |null |
+-----+-----+ +-----+-----+ +-----+-----+
b04a001@AsiaA1:~/comp3b% java ListMerge
1
2
3
4
b04a001@AsiaA1:~/comp3b%
h3 併合整列法の考え方 toc-merge-sort-ideas
index 併合整列 merge sort へいこうせいれつ
とは、併合を段階的に行う整列法です。
併合整列のアルゴリズムは、
1. リストを半分に分ける。
2. 2 つのリストをそれぞれ併合整列する。
3. 整列された 2 つのリストを併合する。
となります。
ただし、リストの長さが 1 のときは何もしません。
2. で再帰が使われていることに注意してください。
今、数列 945271386 が与えられたとします。
この数列を半分に分けますと、9452 と 71386 になります。
また半分に分けますと、94, 52, 71, 386 になります。
最後には、数列はバラバラになります。
ここから、併合を開始します。
分けた順の逆順に併合が行われていきます。
すると、最後には、整列済みの数列 123456789 が得られます。
この様子を図で表しますと、次のトーナメント表のようになります。
ただし、上から下へと読んでください。
945271386
|
+---------------+----------------+
| |
9452 71386
| |
+-------+-------+ +--------+--------+
| | | |
94 52 71 386
| | | |
+---+---+ +---+---+ +---+---+ +-----+-----+
| | | | | | | |
| | | | | | | 86
| | | | | | | |
| | | | | | | +---+---+
| | | | | | | | |
9 4 5 2 7 1 3 8 6
| | | | | | | | |
| | | | | | | +---+---+
| | | | | | | |
| | | | | | | 68
| | | | | | | |
+---+---+ +---+---+ +---+---+ +-----+-----+
| | | |
49 25 17 368
| | | |
+-------+-------+ +--------+--------+
| |
2459 13678
| |
+---------------+----------------+
|
123456789
h3 併合整列法のプログラム toc-merge-sort-programs
プログラムは以下の通りです。
併合整列を行うのはメソッド msort です。
リストを半分に分けるため、参照 fast を用意し、
lst を fast の半分の速さで右に移動させます。
fast が右端に来たとき、lst の指すインスタンスを末尾にして、
リストを分割します。
なお、プログラムの前半では、配列要素をランダムに並び替え、
メソッド toList でその配列をリストに変換しています。
class MergeSort {
public static void main (String[] args) {
int[] a = new int[10];
IntList lst;
initial(a);
shuffle(a);
lst = toList(a);
print(lst);
lst = msort(lst);
print(lst);
}
static void initial (int[] a) {
int i;
a[0] = Integer.MIN_VALUE;
for (i = 1; i < a.length; i++) {
a[i] = i;
}
}
static void swap (int[] a, int x, int y) {
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
}
static void shuffle (int[] a) {
int i, rand;
for (i = 1; i < a.length; i++) {
rand = (int) (Math.random() * (a.length - 1)) + 1;
swap(a, i, rand);
}
}
static IntList toList (int[] a) {
int i, DUMMY = 0;
IntList lst, head;
lst = new IntList(DUMMY, null);
head = lst;
for (i = 1; i < a.length; i++) {
lst.rest = new IntList(a[i], null);
lst = lst.rest;
}
return head;
}
static void print (IntList lst) {
for (lst = lst.rest; lst != null; lst = lst.rest) {
System.out.print(" " + lst.first);
}
System.out.println();
}
static IntList merge (IntList lst1, IntList lst2) {
IntList lst, head;
lst = lst1;
head = lst;
lst1 = lst1.rest;
lst2 = lst2.rest;
while (lst1 != null && lst2 != null) {
if (lst1.first <= lst2.first) {
lst.rest = lst1;
lst = lst.rest;
lst1 = lst1.rest;
} else {
lst.rest = lst2;
lst = lst.rest;
lst2 = lst2.rest;
}
}
if (lst1 == null) {
lst.rest = lst2;
} else {
lst.rest = lst1;
}
return head;
}
static IntList msort (IntList lst) {
int DUMMY = 0;
IntList head, head1, head2, fast;
if (lst.rest.rest == null) {
return lst;
} else {
head1 = lst;
head2 = new IntList(DUMMY, null);
fast = lst.rest;
while (fast != null) {
fast = fast.rest;
if (fast != null) {
fast = fast.rest;
lst = lst.rest;
}
}
head2.rest = lst.rest;
lst.rest = null;
head = merge(msort(head1), msort(head2));
print(head);
return head;
}
}
}
b04a001@AsiaA1:~/comp3b% java MergeSort
9 4 5 2 7 1 3 8 6
4 9
2 5
2 4 5 9
1 7
6 8
3 6 8
1 3 6 7 8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
h2 演習 7 toc-exercises
リストの長さを利用した併合整列法のプログラムを作成してください。
上記の併合整列法のプログラムでは、
リストを半分に分ける方法が難解でした。
もし、リストの長さ len を求めておけば、参照を len / 2 回たどり、
そのインスタンスを末尾にすれば、リストの分割ができます。
上記のプログラムのメソッド msort を変更し、
リスト lst の長さ len を求めた後、
参照を len / 2 回たどるようにしてください。
今日の演習7の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（11月5日）を明記してください。