与えられた数列を小さい順に並べ替えることを、 整列 （ sorting ） と言います。 数列を大きい順に並び替えることや、文字列の列を辞書の順序に並べ替えることも、整列に含めます。 また、例えば会員番号と氏名からなるレコードを、会員番号順に並べ替えることも整列です。 この場合は、レコードの会員番号の部分を数列と見なします。
整列はよく利用されますので、色々な高速アルゴリズムが提案されています。
整列アルゴリズムは、内部整列と外部整列に分類されます。 内部整列 （ internal sorting ） とは、メモリにすべての数列が格納される場合の整列法です。 一方、メモリにすべての数列が収まらないときは、ハード・ディスクなどに数列をファイルとして保存しながら整列します。 この場合の整列法が、 外部整列 （ external sorting ） です。 内部整列と外部整列とでは、適したアルゴリズムは異なります。 今日は、内部整列について考えます。
内部整列では、まず、数列を配列に格納します。 このとき、番兵を配列の端に追加することがあります。 番兵 （ sentinel ） とは、配列の端を表す特別な要素のことです。 番兵を置きますと、整列アルゴリズムによっては、要素を比較することと、配列の範囲内か確認することが、一本化できるのです。 ここでは、 a [0] に負の大きな数を格納し、整列する数列は a [1] から格納します。
最初に紹介するのは選択整列です。
選択整列 （ selection sort ） のアルゴリズムは次の通りです。 まず、 a [1] 以降で最も小さい数を探し、それと a [1] を交換します。 次に、 a [2] 以降で最も小さい数を探し、それと a [2] を交換します。 その次に、 a [3] 以降で最も小さい数を探し、それと a [3] を交換します。 この手続きを、 a [ a .length - 2] まで繰り返します。
選択整列は分かりやすいですが、あまり速くはありません。
プログラムは以下の通りです。
/* 1*/ class SelectionSort { /* 2*/ public static void main (String[] args) { /* 3*/ int i, j, min, t, SENTINEL = -9999; /* 4*/ int[] a = {SENTINEL, 3, 6, 5, 4, 9, 1, 8, 2, 7}; /* 5*/ for (i = 1; i < a.length; i++) { /* 6*/ System.out.print(" " + a[i]); /* 7*/ } /* 8*/ System.out.println(); /* 9*/ for (i = 1; i < a.length - 1; i++) { /* 10*/ min = i; /* 11*/ for (j = i + 1; j < a.length; j++) { /* 12*/ if (a[j] < a[min]) { /* 13*/ min = j; /* 14*/ } /* 15*/ } /* 16*/ t = a[min]; /* 17*/ a[min] = a[i]; /* 18*/ a[i] = t; /* 19*/ for (j = 1; j < a.length; j++) { /* 20*/ System.out.print(" " + a[j]); /* 21*/ } /* 22*/ System.out.println(); /* 23*/ } /* 24*/ } /* 25*/ }
asiaa1:~/comp3b b08a001$ java SelectionSort 3 6 5 4 9 1 8 2 7 1 6 5 4 9 3 8 2 7 1 2 5 4 9 3 8 6 7 1 2 3 4 9 5 8 6 7 1 2 3 4 9 5 8 6 7 1 2 3 4 5 9 8 6 7 1 2 3 4 5 6 8 9 7 1 2 3 4 5 6 7 9 8 1 2 3 4 5 6 7 8 9 asiaa1:~/comp3b b08a001$
次に紹介するのが挿入整列です。
挿入整列 （ insertion sort ） のアルゴリズムは次の通りです。 まず、 a [2] を左に移動して、 a [1] から a [2] までを整列済みにします。 次に、 a [3] を左に移動して、 a [1] から a [3] までを整列済みにします。 その次に、 a [4] を左に移動して、 a [1] から a [4] までを整列済みにします。 この手続きを、 a [ a .length - 1] まで繰り返します。
挿入整列も分かりやすいですが、あまり速くはありません。 ただし、データ数が 10 以下ならば速いことが知られています。
プログラムは以下の通りです。 要素を左に移動する際、最小要素でも番兵の直前で停止しますので、配列からはみ出すことはありません。
/* 1*/ class InsertionSort { /* 2*/ public static void main (String[] args) { /* 3*/ int i, j, v, SENTINEL = -9999; /* 4*/ int[] a = {SENTINEL, 6, 4, 1, 5, 9, 8, 2, 3, 7}; /* 5*/ for (i = 1; i < a.length; i++) { /* 6*/ System.out.print(" " + a[i]); /* 7*/ } /* 8*/ System.out.println(); /* 9*/ for (i = 2; i < a.length; i++) { /* 10*/ v = a[i]; /* 11*/ j = i; /* 12*/ while (a[j - 1] > v) { /* 13*/ a[j] = a[j - 1]; /* 14*/ j--; /* 15*/ } /* 16*/ a[j] = v; /* 17*/ for (j = 1; j < a.length; j++) { /* 18*/ System.out.print(" " + a[j]); /* 19*/ } /* 20*/ System.out.println(); /* 21*/ } /* 22*/ } /* 23*/ }
asiaa1:~/comp3b b08a001$ java InsertionSort 6 4 1 5 9 8 2 3 7 4 6 1 5 9 8 2 3 7 1 4 6 5 9 8 2 3 7 1 4 5 6 9 8 2 3 7 1 4 5 6 9 8 2 3 7 1 4 5 6 8 9 2 3 7 1 2 4 5 6 8 9 3 7 1 2 3 4 5 6 8 9 7 1 2 3 4 5 6 7 8 9 asiaa1:~/comp3b b08a001$
ここで、データを整列する理由について考えます。 一般的に、データが整列済みであれば、データの処理は高速化できます。 つまり、いろいろな処理を行うデータに関しては、あらかじめ整列しておけば、最終的に短時間で処理が終わるのです。
例えば、配列
から要素5を探索することを考えます。 配列が整列されていなければ、探索するには、配列要素を一つ一つ調べるしかありません。 「見つかりません」という結論を得るには、すべての要素を確認することになります。
プログラムは以下の通りです。 なお、配列の最後に番兵（探索要素自身）を配置して、配列の外に出ないようにするチェックを省略しています。
/* 1*/ class ArraySearch { /* 2*/ public static void main (String[] args) { /* 3*/ int i = 0, search = 5; /* 4*/ int SENTINEL = search; /* 5*/ int[] a = {2, 6, 4, 2, 8, 4, 2, 6, 4, 2, SENTINEL}; /* 6*/ boolean found = false; /* 7*/ while (true) { /* 8*/ if (a[i] == search) { /* 9*/ if (i < a.length - 1) { /* 10*/ found = true; /* 11*/ } /* 12*/ break; /* 13*/ } /* 14*/ i++; /* 15*/ } /* 16*/ if (found) { /* 17*/ System.out.println("見つかりました"); /* 18*/ } else { /* 19*/ System.out.println("見つかりません"); /* 20*/ } /* 21*/ } /* 22*/ }
asiaa1:~/comp3b b08a001$ java ArraySearch 見つかりません asiaa1:~/comp3b b08a001$
もし、配列が
と整列済みであれば、5を探索するのに、すべての要素を調べる必要がなくなります。 一つずつ要素を確認し、6を見た段階で、「見つかりません」と結論が出せるのです。
プログラムは以下の通りです。 なお、配列の最後に番兵（巨大な数）を配置して、配列の外に出ないようにするチェックを省略しています。
/* 1*/ class SortSearch { /* 2*/ public static void main (String[] args) { /* 3*/ int i = 0, search = 5, SENTINEL = 9999; /* 4*/ int[] a = {2, 2, 2, 2, 4, 4, 4, 6, 6, 8, SENTINEL}; /* 5*/ boolean found = false; /* 6*/ while (true) { /* 7*/ if (a[i] >= search) { /* 8*/ if (a[i] == search && a[i] != SENTINEL) { /* 9*/ found = true; /* 10*/ } /* 11*/ break; /* 12*/ } /* 13*/ i++; /* 14*/ } /* 15*/ if (found) { /* 16*/ System.out.println("見つかりました"); /* 17*/ } else { /* 18*/ System.out.println("見つかりません"); /* 19*/ } /* 20*/ } /* 21*/ }
asiaa1:~/comp3b b08a001$ java SortSearch 見つかりません asiaa1:~/comp3b b08a001$
整列済みの配列の探索については、左から一つ一つ調べるのではなく、まず中央を調べ、そして左半分か右半分を調べ…とすると、より高速な探索が可能です。
もう一つ、整列しておくと高速処理ができる例を紹介します。
配列
の要素を、重複を除いて出力することを考えます。 これは、「自分より左に自分と同じ要素がなければ出力する」という方針でやればできます。 しかし、自分より左にある要素を確認すると、a[1]については最大1回、a[2]については最大2回、a[3]については最大3回…と、どんどん確認回数が増えてしまいます。
プログラムは以下の通りです。
/* 1*/ class ArrayUnique { /* 2*/ public static void main (String[] args) { /* 3*/ int i, j; /* 4*/ int[] a = {2, 6, 4, 2, 8, 4, 2, 6, 4, 2}; /* 5*/ boolean found; /* 6*/ for (i = 0; i < a.length; i++) { /* 7*/ found = false; /* 8*/ j = 0; /* 9*/ while (true) { /* 10*/ if (a[j] == a[i]) { /* 11*/ if (j < i) { /* 12*/ found = true; /* 13*/ } /* 14*/ break; /* 15*/ } /* 16*/ j++; /* 17*/ } /* 18*/ if (!found) { /* 19*/ System.out.println(a[i]); /* 20*/ } /* 21*/ } /* 22*/ } /* 23*/ }
asiaa1:~/comp3b b08a001$ java ArrayUnique 2 4 6 8 asiaa1:~/comp3b b08a001$
もし、配列が
と整列済みであれば、重複を除いて出力するのに、たくさんの要素を調べる必要がなくなります。 a[1]についてもa[2]についても、要素が変化したかどうか、1回だけ確認すればよいのです。
プログラムは以下の通りです。
/* 1*/ class SortUnique { /* 2*/ public static void main (String[] args) { /* 3*/ int i, val = 0, SENTINEL = 9999; /* 4*/ int[] a = {2, 2, 2, 2, 4, 4, 4, 6, 6, 8, SENTINEL}; /* 5*/ if (a.length > 1) { /* 6*/ val = a[0]; /* 7*/ System.out.println(val); /* 8*/ } /* 9*/ i = 1; /* 10*/ while (true) { /* 11*/ if (a[i] != val) { /* 12*/ if (a[i] == SENTINEL) { /* 13*/ break; /* 14*/ } /* 15*/ val = a[i]; /* 16*/ System.out.println(val); /* 17*/ } /* 18*/ i++; /* 19*/ } /* 20*/ } /* 21*/ }
asiaa1:~/comp3b b08a001$ java SortUnique 2 4 6 8 asiaa1:~/comp3b b08a001$
集合としての配列については、前回説明しました。 集合は、要素の重複がないことを思い出してください。
集合としての配列が整列済みであれば、集合演算もまた、高速化できます。 例えば、集合 A = {10, 20, 30, 40, 50} と B = {10, 30, 50, 70, 90} の和集合を出力するには、a[i] と b[j] を比較して小さい方を出力し、もし等しいならまとめて出力する、という方法でできます。 整列済みでないときは、何度も探索して和集合を求めたのですが、整列済みであれば、そんなことをしなくてよいのです。
プログラムは以下の通りです。 なお、配列の最後に番兵（巨大な数）を配置して、配列の外に出ないようにするチェックを省略しています。
/* 1*/ class SortUnion { /* 2*/ public static void main (String[] args) { /* 3*/ int i = 0, j = 0, SENTINEL = 9999; /* 4*/ int[] a = {10, 20, 30, 40, 50, SENTINEL}; /* 5*/ int[] b = {10, 30, 50, 70, 90, SENTINEL}; /* 6*/ while (true) { /* 7*/ if (a[i] < b[j]) { /* 8*/ System.out.println(a[i]); /* 9*/ i++; /* 10*/ } else if (a[i] > b[j]) { /* 11*/ System.out.println(b[j]); /* 12*/ j++; /* 13*/ } else if (a[i] == SENTINEL) { /* 14*/ break; /* 15*/ } else { // a[i] == b[j] /* 16*/ System.out.println(a[i]); /* 17*/ i++; /* 18*/ j++; /* 19*/ } /* 20*/ } /* 21*/ } /* 22*/ }
asiaa1:~/comp3b b08a001$ java SortUnion 10 20 30 40 50 70 90 asiaa1:~/comp3b b08a001$
集合としての配列が整列済みと仮定して、集合 A = {10, 20, 30, 40, 50} と B = {10, 30, 50, 70, 90} の共通部分を出力するプログラムを作成してください。 番兵については、和集合のときと同じでよいです。
asiaa1:~/comp3b b08a001$ java SortIntersection 10 30 50 asiaa1:~/comp3b b08a001$
今日の演習4の答案（Javaプログラム）をメールで提出してください。 差出人は学内のメール・アドレス（b08a001@cis.twcu.ac.jpなど）とし、宛先はkonishi@cis.twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（10月17日）を明記してください。