Web教材一覧>
アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)
実務でよく用いられるデータ処理にソート(整列)があります。ここでは、選択ソートを例にして、アルゴリズムの理解を高めることを目的とします。
アルゴリズム、ソート、スワップ、最小値、選択ソート、関数
配列aのサイズnが5で、その要素が、
a[1] a[2] a[3] a[4] a[5]
30 20 50 10 40
であるとき、これを昇順(小さい順)に並べ変えること、すなわち
a[1] a[2] a[3] a[4] a[5]
10 20 30 40 50
にすることを例にします。
選択ソートのアルゴリズムを検討することをとおして、プログラムの作成では、複雑な問題を単純な操作に分解し、それを組み立てることが有効であることを説明します。
選択ソートでは、まず全体のうち最小値をもつ要素を探して先頭にもっていき(最小値をもつ要素と先頭の要素を入れ替えて)、次に2番目以降の最小値要素と2番目の要素を差し替えるという操作を繰り返せば、全体がソートされるという考え方です。わかりやすい考え方です。
しかし、ソートをすることが目的ならば、a[1] と最小値である要素をスワップする必要があるため、最小値である要素の添字(要素番号)k を知る必要があります。
それで、プログラムを次のように変更します。
ア k = 1;
イ amin = a[1];
ウ for (j=2; j<=n; j++) {
エ if (a[j] < amin) {
オ amin = a[j];
カ k = j;
キ }
ク }
ケ if (k != 1) {
コ w = a[k]; /* */
サ a[k] = a[1]; /* スワップ */
シ a[1] = w; /* */
ス }
(コ~シにおいて、a[k] の値は amin なので、あえて w にせずに、
a[k] = a[1];
a[1] = amin;
とすることができます。)
実際の数値で確かめましょう(このように、ヒューマンコンピュータの作業のことをトレースといいます)。
ア:k = 1、イ:amin = a[1] = 30
ウ:j = 2
エ:a[j]=a[2]=(=20) < amin(=30) なのでオへ
オ:amin = 20、カ:k = j = 2
キ・クからウに戻り、j = 3
エ:a[j]=a[3]=(=50) > amin(=20) なのでオ・カは行われない
キ・クからウに戻り、j = 4
エ:a[j]=a[4]=(=10) < amin(=20) なのでオへ
オ:amin = 10、カ:k = j = 4
キ・クからウに戻り、j = 5
エ:a[j]=a[5]=(=40) > amin(=10) なのでオ・カは行われない
キ・クからウに戻ろうとするが、ウの j<=n の条件により
繰り返しが完了するのでケへ
ケ:ここまでで、a[k]=a[4]=amin=10 が最小値であることが判明
k≠1 なので、コ~シで、a[1]⇔a[4] を行う。
この結果、
a[1] a[2] a[3] a[4] a[5]
10 20 50 30 40
になります。
トレースをするのに、このような散文調ではわかりにくいので、次のような表にするのが適切です(プログラムに慣れると、表を作成する必要すらなくなるのですが)。
a[j] k a[k] エの比較 amin 新k
初期値 1 30
j=2 20 1 30 < 20 2
3 50 2 20 >
4 10 2 20 < 10 4
5 40 4 10 >
これから、k=4、最小値=a[4]=10であることがわかります。
トレースした結果を示します。
a[1] a[2] a[3] a[4] a[5]
初期値 30 20 50 10 40
最小値=a[4]=10:a[1]⇔a[4] 10 20 50 30 40
最小値=a[2]=20:変化なし 10 20 50 30 40
最小値=a[4]=30:a[3]⇔a[4] 10 20 30 50 40
最小値=a[5]=40:a[4]⇔a[5] 10 20 30 40 50
ソート結果 10 20 30 40 50
関数(function)とは、プログラムを構成する部品のようなものです。
スワップ処理を一般化して
function swap(x, y) {
w = x;
x = y;
y = w;
}
という関数を作成しておきます。
そうすれば、a[3]⇔a[4] を行いたいときは、
swap(a[3], a[4])
と記述すればよいのです。
配列a[i]~a[n]のなかで最小値の添字 k を求める関数 findamin は次のようになります。
(配列aとnは外部変数で定義されているものとします。)
function findamin(i,k) {
k = i;
amin = a[i];
for (j=i+1; j<=n; j++) {
if (a[j] < amin) {
amin = a[j];
k = j;
}
}
}
そして、ソートのプログラムは、次のようになります。
function sort();
for (i=1; i<=n-1; i++) {
findamin(i,k);
if (i != k) swap(a[i], a[k]);
}
}
このように、関数の考え方を導入すると、
アルゴリズムが明確になり、ミスのないプログラムが作れる
他人が読んでもわかりやすいので、保守・改訂が容易になる
関数を部品として他のプログラムで再利用することができる
などのメリットがあります。
ソートの方法には、多様な方法があります(→参照:「ソートの種類」)。選択ソートに類似した有名な方法にバブルソートや挿入ソート(→参照:「基本的なソート方法」)、高速なソート方法では、クイックソートやシェルソートなど(→参照:「高速ソート」)があります。