与えられた数列を小さい順に並べ替えることを、 整列 （ 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; /* 4*/ int[] a = {-9999, 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*/ }
b04a001@AsiaA1:~/comp3b% 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 b04a001@AsiaA1:~/comp3b%
次に紹介するのが挿入整列です。
挿入整列 （ 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; /* 4*/ int[] a = {-9999, 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*/ }
b04a001@AsiaA1:~/comp3b% 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 b04a001@AsiaA1:~/comp3b%
最後に紹介するのがクイックソートです。
クイックソート （ quicksort ） の考え方は次のようなものです。 まず、いくつかの要素を交換し、
という状態にします。 （このことを、配列の分割と言います。） そして、 a [1] から a [ k - 1] までと、 a [ k + 1] から a [ a .length - 1] までに対して、再帰的にクイックソートを行います。
配列の分割では、まず、右端の要素を比較基準とします。 次に、配列を左端から右へ見ていき、基準以上の要素 a [ l ] を探します。 また、配列を右端（比較基準）の左隣から左へ見ていき、基準以下の要素 a [ r ] を探します。 そして、 a [ l ] と a [ r ] を交換します。 この手続きを、 l と r が衝突するまで続けます。 最後に、比較基準と a [ l ] を交換します。
クイックソートは分かりにくいですが、最高速のアルゴリズムとして知られています。 現実のシステムでは、クイックソートの改良版が使われています。
クイックソートのプログラムは以下の通りです。 要素を左に見ていくときは a [0] が、右に見ていくときは自分自身が、番兵の役割を果たします。
/* 1*/ class Quicksort { /* 2*/ public static void main (String[] args) { /* 3*/ int i; /* 4*/ int[] a = {-9999, 5, 2, 1, 8, 4, 7, 3, 9, 6}; /* 5*/ for (i = 1; i < a.length; i++) { /* 6*/ System.out.print(" " + a[i]); /* 7*/ } /* 8*/ System.out.println(); /* 9*/ qsort(a, 1, a.length - 1); /* 10*/ } /* 11*/ static void qsort (int[] a, int left, int right) { /* 12*/ int i, l, r, t, v; /* 13*/ if (left < right) { /* 14*/ v = a[right]; /* 15*/ l = left; /* 16*/ r = right - 1; /* 17*/ while (true) { /* 18*/ while (a[l] < v) { /* 19*/ l++; /* 20*/ } /* 21*/ while (a[r] > v) { /* 22*/ r--; /* 23*/ } /* 24*/ if (l >= r) { /* 25*/ break; /* 26*/ } /* 27*/ t = a[l]; /* 28*/ a[l] = a[r]; /* 29*/ a[r] = t; /* 30*/ } /* 31*/ a[right] = a[l]; /* 32*/ a[l] = v; /* 33*/ for (i = 1; i < a.length; i++) { /* 34*/ System.out.print(" " + a[i]); /* 35*/ } /* 36*/ System.out.println(); /* 37*/ qsort(a, left, l - 1); /* 38*/ qsort(a, l + 1, right); /* 39*/ } /* 40*/ } /* 41*/ }
b04a001@AsiaA1:~/comp3b% java Quicksort 5 2 1 8 4 7 3 9 6 5 2 1 3 4 6 8 9 7 3 2 1 4 5 6 8 9 7 1 2 3 4 5 6 8 9 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 b04a001@AsiaA1:~/comp3b%
配列要素の中央値を求めるプログラムを作成してください。 ここで、中央値とは、整列すると中央に来る値です。
中央値は、 a [1] から a [ a .length - 1] までを整列してしまえば、 a [ a .length / 2] の値です。 しかし、クイックソートのアルゴリズムを改造しますと、完全に整列しなくても中央値が求められます。
クイックソートの呼び出し qsort ( a , left , right ) は、配列を分割し、 a [ left ] から a [ l - 1] までの要素は a [ l ] 以下、 a [ l + 1] から a [ right ] までの要素は a [ l ] 以上とします。 このとき、もし l が a .length / 2 より大きいならば左側のみを整列し、 l が a .length / 2 より小さいならば右側のみを整列すればよいのです。 l と a .length / 2 が等しい場合は何もする必要はありません。
プログラムは、上記のクイックソートのプログラムを変更して作成してください。
なお、配列要素の k 番目に小さい値を求めるアルゴリズムは、 選択アルゴリズム （ selection algorithm ） と呼ばれます。 中央値を求める方法は、選択アルゴリズムの特殊な場合に当たります。
b04a001@AsiaA1:~/comp3b% java QuickMedian 9 6 1 8 4 2 5 7 3 2 1 3 8 4 9 5 7 6 2 1 3 5 4 6 8 7 9 2 1 3 4 5 6 8 7 9 The median is 5 b04a001@AsiaA1:~/comp3b%
今日の演習4の答案（Javaプログラム）をメールで提出してください。 メールの差出人は学内のアドレス（b04a001@twcu.ac.jpなど）とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（10月21日）を明記してください。