| 目次 | 索引 |
|---|---|
クイックソート （ quicksort ）
分割統治法 （ divide-and-conquer ）
h2 クイックソート toc-quicksort
h3 整列 toc-sorting
与えられた数列を小さい順に並べ替えることを
index 整列 sorting せいれつ
と言います。
数列を大きい順に並び替えることや、
文字列の列を辞書の順序に並べ替えることも、整列に含めます。
また、例えば会員番号と氏名からなるレコードを、
会員番号順に並べ替えることも整列です。
この場合は、レコードの会員番号の部分を数列と見なします。
整列はよく利用されますので、
色々な高速アルゴリズムが提案されています。
整列アルゴリズムは、内部整列と外部整列に分類されます。
index 内部整列 internal sorting ないふせいれつ
とは、メモリにすべての数列が格納する場合の整列法です。
メモリにすべての数列が収まらないときは、
ハード・ディスクなどに数列をファイルとして保存しながら整列します。
この場合の整列法が、
index 外部整列 external sorting かいふせいれつ
です。
内部整列と外部整列とでは、適したアルゴリズムは異なります。
今日は、内部整列について考えます。
内部整列では、最初に配列に数列を格納します。
このとき、番人を配列の端に追加します。
index 番人 sentinel はんにん
とは、配列の端を表す特別な要素のことです。
番人を置きますと、整列アルゴリズムによっては、
要素を比較することと、配列の範囲内か確認することが、
一本化できるのです。
具体的には、a[0] に負の無限大に相当するものを格納し、
整列する数列は a[1] から格納します。
h3 選択整列 toc-selection-sort
最初に紹介するのは選択整列です。
index 選択整列 selection sort せんたくせいれつ
のアルゴリズムは次の通りです。
まず、a[1] 以降で最も小さい数を探し、これと a[1] を交換します。
次に、a[2] 以降で最も小さい数を探し、これと a[2] を交換します。
その次に、a[3] 以降で最も小さい数を探し、これと a[3] を交換します。
この手続きを、a[a.length - 2] まで繰り返します。
選択整列は分かりやすいですが、あまり速くはありません。
プログラムは以下の通りです。
ここで、選択整列を行うのはメソッド ssort です。
メソッド initial で a[1] = 1, ..., a[9] = 9 とし、
メソッド shuffle でこれをランダムに並べ替えています。
class SelectionSort {
public static void main (String[] args) {
int[] a = new int[10];
initial(a);
shuffle(a);
print(a);
ssort(a);
print(a);
}
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 void print (int[] a) {
int i;
for (i = 1; i < a.length; i++) {
System.out.print(" " + a[i]);
}
System.out.println();
}
static void ssort (int[] a) {
int i, j, min;
for (i = 1; i < a.length - 1; i++) {
min = i;
for (j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
swap(a, i, min);
print(a);
}
}
}
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
1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
h3 挿入整列 toc-insertion-sort
次に紹介するのが挿入整列です。
index 挿入整列 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 以下ならば速いことが知られています。
プログラムは以下の通りです。
要素を左に移動する際、最小要素でも番人の直前で停止しますので、
配列からはみ出すことはありません。
class InsertionSort {
public static void main (String[] args) {
int[] a = new int[10];
initial(a);
shuffle(a);
print(a);
isort(a);
print(a);
}
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 void print (int[] a) {
int i;
for (i = 1; i < a.length; i++) {
System.out.print(" " + a[i]);
}
System.out.println();
}
static void isort (int[] a) {
int i, j, key;
for (i = 2; i < a.length; i++) {
key = a[i];
j = i;
while (a[j - 1] > key) {
a[j] = a[j - 1];
j--;
}
a[j] = key;
print(a);
}
}
}
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
1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
h3 クイックソートの考え方 toc-quicksort-ideas
最後に紹介するのがクイックソートです。
index クイックソート quicksort くいつくそおと
の考え方は次のようなものです。
まず、いくつかの要素を交換し、
・a[1] から a[k - 1] までの要素は a[k] 以下
・a[k + 1] から a[a.length - 1] までの要素は a[k] 以上
という状態にします。
(このことを、配列の分割と呼びます。)
そして、a[1] から a[k - 1] までと、
a[k + 1] から a[a.length - 1] までに対して、
再帰的にクイックソートを行います。
配列の分割では、まず、右端の要素を比較基準とします。
次に、配列を左端から右に見ていき、
比較基準より大きい要素 a[l] を探します。
また、配列を右端から左に見ていき、
比較基準より小さい要素 a[r] を探します。
そして、a[l] と a[r] を交換します。
この手続きを、l と r が交差するまで続けます。
最後に、比較基準と a[l] を交換します。
クイックソートは分かりにくいですが、
最高速のアルゴリズムとして知られています。
現実のシステムでは、クイックソートの改良版が使われています。
h3 クイックソートのプログラム toc-quicksort-programs
クイックソートのプログラムは以下の通りです。
要素を左に見ていくときは a[0] が、
右に見ていくときは自分自身が、番人の役割を果たします。
class Quicksort {
public static void main (String[] args) {
int[] a = new int[10];
initial(a);
shuffle(a);
print(a);
qsort(a, 1, a.length - 1);
print(a);
}
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 void print (int[] a) {
int i;
for (i = 1; i < a.length; i++) {
System.out.print(" " + a[i]);
}
System.out.println();
}
static void qsort (int[] a, int left, int right) {
int key, l, r;
if (left < right) {
key = a[right];
l = left;
r = right - 1;
while (a[l] < key) {
l++;
}
while (a[r] > key) {
r--;
}
while (l < r) {
swap(a, l, r);
l++;
r--;
while (a[l] < key) {
l++;
}
while (a[r] > key) {
r--;
}
}
swap(a, l, right);
print(a);
qsort(a, left, l - 1);
qsort(a, l + 1, right);
}
}
}
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
1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
h2 演習
配列要素の中央値を求めるプログラムを作成してください。
ここで、中央値とは、整列すると中央に来る値です。
中央値は、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 番目に小さい値を求めるアルゴリズムは、
index 選択アルゴリズム 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%