Revised: Aug./4th/2003
ここまでで、Javaコア・パッケージで提供されているデータ構造について一通り紹介しました。C/C++やJavaのようなライブラリ指向の言語では、実証されたライブラリ提供のコードを組み合わせて使うべきであり、濫りに自分でアルゴリズムを考案したり実装することは厳重に慎むべきです。しかしながら、そこで実装されているアルゴリズム／データ構造の動作特性をコードレベルで理解していないと、適材適所に活用することはままなりません。ここでは、データ構造に特異なアルゴリズムとして、並べ替え（ソート）と探索（サーチ）について紹介します。
要素を並べ替えるアルゴリズムには多くのものがあり、代表的なものには挿入ソート(Insertion Sort)、櫛ソート(Comb Sort)、シェルソート(Shell Sort)、バブルソート(Bubble Sort)、クイックソート(Quick Sort)、マージソート(Merge Sort)、ヒープソート(Heap Sort)などが挙げれれます。ここでは、最も基本的なアルゴリズムとしての挿入ソートと、コア・パッケージでも実装している高級なアルゴリズムとしてのマージソートを紹介します。
極めて簡単なソート方法で、実行時間は要素の個数の二乗に比例します。例えば、{1,7,8,5,9,2}という配列があるとき、先頭から逐次的に評価して、前のものよりも小さい要素である5を取り除き、5より大きな要素を後ろにまわして{1,5,7,8,9,2}とします。同じく、2を取り除き、{1,2,5,7,8,9}として並べ替えが完了します。要素がオブジェクトである場合は、当該オブジェクトは、インタフェースjava.lang.Comparableを実装して、「自然順序付け(natural ordering)」と呼ばれる順序をサポートしている必要があります。コア・パッケージの多くのクラスはComparableを実装していますが、自分で作ったクラスの場合は、Comparableを明示的に実装する必要があるかもしれません。
class InsertionSortDemo {
public static void main(String[] args) {
int[] src = {1,9,8,6,5,3};
for (int i = 0; i < src.length; i++) {
int j, w = src[i];
for (j = i; j > 0 && src[j - 1] > w; j--) {
src[j] = src[j - 1];
}
src[j] = w;
for (int k = 0; k < src.length; k++) {
System.out.print(src[k] + " ");
}
System.out.println("");
}
}
}
要素数が10個未満程度の並べ替えであれば、挿入ソートで十分だといえます。特に、a[j - 1] > wによる繰り返しの回数に着目すると、順序が逆転している場所が少ない場合は極めて高速であることが分かります。要素数3つの場合は極めて直感的なのですが、そこまでブレーク・ダウンする前に挿入ソートのアルゴリズムの利用が検討できるはずです。
>javac InsertionSortDemo.java >java InsertionSortDemo 1 9 8 6 5 3 1 9 8 6 5 3 1 8 9 6 5 3 1 6 8 9 5 3 1 5 6 8 9 3 1 3 5 6 8 9
挿入ソートは、殆ど整列したリスト型データ構造の場合は極めて高速であり、後続で紹介するマージソート、クイックソートと組み合わせることで、パフォーマンスの劇的な向上が期待できます。
マージソートでは、整列すべき配列を中央で二つに分けて、更に半分に分けて要素一つになるまで分割していくことで並べ替えを実施して、各々を併合するときに並べ替えます。つまり、並べ替えたい配列鋳型のデータ構造に対して、前半部分と後半部分を別々に並べ替えて、最後に各々を順番を保持するように併合するアルゴリズムとなります。
例えば、要素が一つならば、何もしません。二つならば、二つのに分けて、小さい方を前に、大きい方を後ろに置くことで並べ替えられます。三つであれば、一つと二つの前半と後半に分割して、要素が二つの方を、先ほどと同じく並べ替え、一つの方には何もしません。並び替えられた二つの要素からなる配列に対して、適切な順序にもう一方の一つの要素を挿入します。四つの要素の場合は、前半と後半の二つずつの要素に分割して、各々を並べ替え、最後に適切な順序にマージ（併合）します。五つの場合は三つと二つに分割してソートすることになるので、それ以上要素数の場合も同様のアルゴリズムで並べ替えが可能ということになります。帰納法的には、要素数が二つの場合の並べ替えを定義して、三つの場合の併合方法を定義できれば、四つ以上の分割方法は、それらの再帰的な繰り返しになるため、任意の要素数の配列型データ構造の要素をソートできるようになります。
コア・パッケージでは、配列に対する高級な操作を提供するクラスjava.util.Arraysで実装しているstaticメソッドsort(Object[] a)や、コレクション・クラスのユーティリティ・クラスであるjava.util.Collectionsが実装するsort(List list)で利用されています。
マージソートのロジックの例を挙げると、次のリストのようになります。
public static void mergeSort(Object src[], Object dest[],
int low, int high) {
int length = high - low;
// 要素が2個以下になったら並べ替え
// ここでは二つの要素の大小を比較して入れ替えているが、
// 実際には10未満程度の十分小さな要素数になったら挿入ソートなどで並べ替えることで高速になる
if (length <= 2) {
for (int i=low; ilow &&
((Comparable)dest[j-1]).compareTo((Comparable)dest[j])>0; j--) {
Object t = dest[j];
dest[j] = dest[j-1];
dest[j-1] = t;
}
}
return;
}
// midは「中央」又は「中央-1」の索引番号
int mid = (low + high) / 2;
// 再帰的に分割
mergeSort(dest, src, low, mid);
mergeSort(dest, src, mid, high);
// 上下に並べ替えられた要素二つずつ以下が格納されたsrcと、
// 同じのサイズのdestが得られている
// 半分ずつ並べ替えられたsrcをdestにマージする
// 後半の最初の値が前半の最後の値以上であれば何もしないでreturnすれば高速になる
// dest[low]からlow[high - 1]まで繰り返す
for(int i = low, l = low, m = mid; i < high; i++) {
if (m>=high || l= src[m]ならばdest[i]にはsrc[l]を代入してlに1加算
dest[i] = src[l++];
} else {
// src[l] > src[m]ならばdest[i]にはsrc[m]を代入してmに1加算
dest[i] = src[m++];
}
}
}
データ構造に密接に関係するアルゴリズムとして、ソートのほかに探索（サーチ）が挙げられます。探索とは、要素の集団の中から、指定した要素を探し出すことです。最も単純な方法は、要素を一つずつ取り出して、指定した条件に一致するかどうか評価する方法が挙げられます。これを逐次探索法(Sequential Search)と呼びます。ここでは、より現実的なアルゴリズムとして、二分探索法(Binary Search)と自己組織化探索法(Self-organizing Sequential Search)を紹介します。他にも、補間探索法(Interpolation Search)、ハッシュ法(Hashing)、二分木探索法(Binary tree search)、B-treeなど、低級なものから高級なものまで膨大に挙げられます。
二分探索法は、ソートされた一次元のリスト型データ構造を高速に探索する方法です。要素が何らかの順番でソートされたリスト構造は頻繁に利用されるので、いたるところで実装されているアルゴリズムです。コア・パッケージでは、クラスArraysのbinarySearch()、クラスCollectionsのbinarySearch()などで実装されています。
まず、中央の値との大小を比較して、大きければ後半の中央値と比較します。小さければ前半の中央値と比較します。これを繰り返して、目的の値を探索する方法です。アルゴリズムの香りのするものでは、最も単純なものの一つです。
public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length-1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] < key) { // キーよりも中央値が小さければ
low = mid + 1; // 上半分を探索
} else if (a[mid] > key) { // キーよりも中央値が大きければ
high = mid - 1; // 下半分を探索
} else { // キーと中央値が等しければ
return mid; // 発見した要素の索引番号を返す
}
}
return -(low + 1); // 見つからなければ負値を返す
}
要素数がそれほど多くない、順序が不定のリストであれあば、先頭から順番に評価して探し出す、逐次探索（線形探索）が便利です。しかし、先頭から順番に要素を探していくので、後ろにあるものほど時間が掛かることになります。自己組織化探索法は、自分自身の要素の並び順を探索試行毎に入れ替えて、より頻繁に探索されるものほど先頭に置かれるようにします。
複数の要素が無作為に保持されているリスト構造の場合は、頻繁に探索されるものと、稀にしか探索されないものがあるものです。頻繁に探索される要素をできるだけ高速に探索するためには、探索された要素はその都度先頭に配置することが最適です。しかし、一度探索されただけで先頭に置かれてしまうので、稀にしか探索されない要素がたった一度探索されただけで一等地の先頭に移動してしまいます。このようなことがたまたま繰り返されると、頻繁に探索される要素が順次後ろ送りになって、期待したパフォーマンスが一時的に阻害されることになるかもしれません。これを避けるために、探索される毎に一つ前に移動するという方法も考えられます。ここで、前者の、先頭に送る方法は先頭移動法(move-to-front method)と呼び、後者の、一つ前の要素と入れ替える方法は置換法(transpose method)と呼ばれます。
ここでは先頭移動法のコード例を紹介します。先頭移動法では先頭に要素を挿入することになるので、Javaのデータ構造では、配列やクラスArrayLisyよりも、クラスLinkedListを使った方が高速です。
public static LinkedList organizingSearch(LinkedList list, Object key) {
int i = 0;
int max = list.size() - 1;
list.add(key); // リストの最後にキーと同じ要素を番人を追加
while (!list.get(i).equals(key)) { // キーと同じ要素に遭遇するまで全要素を比較
i++;
}
list.remove(max + 1); // 番人を削除
if (i > max) { // 番人であれば
return null; // null を返す
} else if (i != 0) { // 先頭でなければ
list.addFirst(list.remove(i));
return list; // 要素を入れ替えてリストを返す
} else {
return list; // 先頭であればそのままリストを返す
}
}