図: まず前から処理する方法
ソフトウエア基礎
アルゴリズムとは、プログラムで特定の問題を解くための方法である。 例えば、いくつかのデータをある順番(大きい順、小さい順)に並べるソートには、 バブルソートや基本挿入法、シェルソート、ヒープソート、クイックソートなど数多くのアルゴリズムが考案されている。
アルゴリズムで特に特徴的なことは、一般にアルゴリズムはプログラミング言語に依存しないということである。一度あるアルゴリズムを理解すれば、将来他のプログラミング言語を勉強する際にも、 そのアルゴリズムが使える。アルゴリズムを知っておくと、「単にプログラムが書けるだけの人」に 対して大きく優位にたつことができる。ぜひマスターして欲しい。
ソート(整列)は、同じ種類のデータを順番に並べる方法である。 例えば、試験の答案であれば、得点の良い順番に並べる、学籍番号順に並べる。 また、各個人であれば、学籍番号順に並べる、身長順に並べる、といたことである。
並べる場合、当然ながら何らかの値の大小に注目する。上の例では、点数、学籍番号、身長のそれぞれの値である。並べる順番には二種類ある。
ソートができるデータは、数値だけとは限らない。大小関係が判別できるデータであれば、ソートできる。例えば、文字列は、それぞれの文字コードの値で大小関係が求まる。これにより、例えば辞書に載っている順番に文字列を並べることができる。
ここでは、ソート(並びかえ)のアルゴリズムとして、バブルソート(基本交換法)、 基本挿入法、クイックソートを紹介する。
バブルソートは以下の図の要領でソートを行う。
バブルソートでは、隣り合ったデータを比較し、その大小関係がおかしい場合は、データを交換する。 それを順にずらしながら行っていくと、最終的にソートがされる。 上の図は、昇順に並べる例である。 昇順に並べる場合、左側のデータは右側のデータより小さい値にする必要がある。 まず最初は１つめのデータ(10)と２つめのデータ(8)を比べる。 左側のデータのほうが大きいので大小関係がおかしい。そこで10と8を交換する。
次に１つ右側に寄って２つめのデータ(10)と３つめのデータ(15)を比べる。 大小関係は正しいので交換しない。このように徐々に右にずらしていく。 これを一番右まで行う(図の左下端)とデータのうち最大の値(21)が一番右に来る。 このように最大の値が一番右に移動するのである。
以上のことをまた繰り返す。ただし、最大の値(21)は既に一番右に移動したので、その場所は確定した。 したがって、今回は３つめと４つめのデータ比較まで行えば良い。 これを行うと、２番目に大きな値(15)が右から２番目の場所に移動している。 これで21と15の２つのデータの場所が確定した。
今度はデータの比較を２つめと３つめまで行えば良い。 これで３番目に大きな値(10)が右から３番目の場所に移動し確定した。 最後に１つめと２つめのデータを比較し交換したら全ての場所が確定し、ソートが完了する。
このように最大の値が徐々に右に寄っていく様子が泡が上っているようであるため、 バブルソートと呼ばれている。 バブルソートは簡単で理解しやすいアルゴリズムであるが、他の多くのアルゴリズムと比べ、処理時間が長くかかるのが弱点である。
以下のプログラムを元にバブルソートのプログラムを完成させよ。
public class BubbleSortTest {
static void bubble_sort(int[] d) {
for (int i = d.length-1; i > 0; i-- ) {
for (int j = 0; j < i; j++) {
System.out.println("i=" + i + ",j=" + j);
// この部分を修正する
}
}
}
// 配列内のデータ列を表示する
static void print_data(int[] d) {
for(int i = 0; i < d.length; i++) System.out.print(d[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int[] data = {5, 10, 3, 7, 8, 1, 9};
print_data(data);
bubble_sort(data);
print_data(data);
}
}
課題sort-1のプログラムを元にバブルソートにより「降順」にソートするプログラムを作成せよ。
基本挿入法は、まだソートしていない1個のデータを既にソートしてあるデータ列の 適切な場所に挿入する方法である。下図のようにソート済の範囲(オレンジ色)が徐々に増えていき、最終的に全てがソートされる。
基本挿入法では、新たなデータを挿入する処理をいかに高速に行なうかが重要である。 データを挿入する場合、まず思い付く処理は、
というものである。これを図にすると以下のようになる。
実は前からでなく後ろから比較していくと、もっと高速になる。 下図のように、後ろから比較していき、 挿入したいデータより小さな値に会うまでデータを1つ右に移動していけば良い。 上記の処理では配列の全てのデータにアクセスする必要があったが、この方法なら 挿入すべき場所の右側だけアクセスすれば良いので、高速になる。
以下のプログラムは、基本挿入法によるソートの例である。
これは、上記の「まず前から処理する方法」を使用している。
これを「後ろから処理する方法」で処理するように修正せよ。
※ insertion_sort1メソッドはそのままにし、「後ろから処理する方法」は insersion_sort2という名前のメソッドとせよ。当然mainメソッドからはinsertion_sort2を呼び出すようにせよ。
public class InsertionSortTest {
static void insertion_sort1(int[] d) {
int i,j,k;
for (i = 1; i < d.length; i++ ) {
// d[i]をd[0]〜d[i-1]の適切な位置に挿入する
// d[0]から順番に挿入すべき位置を探す
int tmp = d[i];
for (j = 0; j < i; j++) {
if (d[j] > tmp) break;
}
// 挿入すべき位置より右側のデータを右に1つずらす
for (k = i; k > j; k--) {
d[k] = d[k-1];
}
// 挿入すべき位置にd[i](だった値)を代入
d[j] = tmp;
}
}
// 配列内のデータ列を表示する
static void print_data(int[] d) {
for(int i = 0; i < d.length; i++) System.out.print(d[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int[] data = {5, 10, 3, 7, 8, 1, 9};
print_data(data);
insertion_sort1(data);
print_data(data);
}
}
課題sort-3で作成したプログラムを修正し、1000個のデータを乱数で作り、それを基本挿入法でソートするプログラムを作成せよ。なお、乱数の範囲は0〜9999とせよ。
ヒント:乱数の発生例(0〜49の範囲の乱数(整数値)を発生)
System.out.println((int)(Math.random() * 50));
課題sort-4で作成したプログラムを使い、 データ数が300,3000,30000の場合の実行時間をinsertion_sort1とinsertion_sort2の それぞれを使った場合について計測せよ。なお、print_dataメソッドを呼ばないようにして計測せよ。
% time java TestProgram 4.890u 0.020s 0:04.96 98.9% 0+0k 0+0io 1698pf+0w最初の数値がユーザ時間、次がシステム時間であり、単位は秒である。 今回の課題ではユーザ時間のみ報告すれば良いこととする。
ここで通常の条件の中では一番高速であると言われているクイックソートを紹介する。
クイックソートの基本的考え方は、「データ列を分割して、分割された中がソートされていれば、 全体もソートされることになる」ということである。このように問題を細かな問題に分割していき、 細かな問題を解き、最終的にまとめて問題を解決する手法を分割統治法(divide and conquer)という。 優れたアルゴリズムは分割統治法を使っているものが多い。
クイックソートで、データ列を分割する場所のデータをピボット(軸)という。 ピボットはデータ列の真中にするのが普通である。 分割をする場合に、ピボットより左にあるデータ列は、 ピボットより右にあるデータ列よりも必ず小さな値になっていなければならない。 これを行うには、データ列の左端と右端からそれぞれの値を比べ、 大小関係がおかしければ交換を行う。
分割の準備ができれば、分割した細かくなった部分について同様にクイックソートを行う。 つまりクイックソートは再帰的なアルゴリズムなのである。 詳しくは教科書を参照せよ。
クイックソートのプログラム例を以下に示す。
public class QuickSortTest {
// 配列dのleftからrightまでの間のデータ列をクイックソートする
static void quick_sort(int[] d, int left, int right) {
if (left>=right) {
return;
}
int p = d[(left+right)/2];
int l = left, r = right, tmp;
while(l<=r) {
while(d[l] < p) { l++; }
while(d[r] > p) { r--; }
if (l<=r) {
tmp = d[l]; d[l] = d[r]; d[r] = tmp;
l++; r--;
}
}
quick_sort(d, left, r); // ピボットより左側をクイックソート
quick_sort(d, l, right); // ピボットより右側をクイックソート
}
// 配列内のデータ列を表示する
static void print_data(int[] d) {
for(int i = 0; i < d.length; i++) System.out.print(d[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int[] data = {5, 10, 3, 7, 8, 1, 9};
print_data(data);
quick_sort(data, 0, data.length-1);
print_data(data);
}
}
quick_sortメソッドの中からquick_sortメソッドを呼び出している。つまり再帰呼び出しである。 quick_sortメソッド内のその上の部分は、分割の際にピボットの左側に小さなデータ、 右側に大きなデータとなるようにデータを移動する処理である。
1000個のデータを乱数で作り、それをバブルソートとクイックソートでそれぞれソートするプログラムを作成せよ。
※ 基本挿入法は課題sort-4で作成済。
課題sort-6で作成したプログラムを使い、 データ数が300,3000,30000の場合にクイックソートを行なった時の実行時間を計測せよ。なお、print_dataメソッドを呼ばないようにして計測せよ。そして、課題sort-5の結果と比較せよ。
課題sort-4,sort-6のそれぞれの方式においてデータの交換が何回発生するかをカウントし表示せよ。
データ列が10個の場合、100個の場合、1000個の場合、10000個の場合をそれぞれ求めよ。
※ 基本挿入法については、insertion_sort2メソッドを呼ぶ場合のみでよい。
また、データの代入の回数をカウントすれば良いものとする。
ソフトウエア基礎
ohmi@rsch.tuis.ac.jp
