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]);
}
}
このように、関数の考え方を導入すると、
アルゴリズムが明確になり、ミスのないプログラムが作れる
他人が読んでもわかりやすいので、保守・改訂が容易になる
関数を部品として他のプログラムで再利用することができる
などのメリットがあります。
ソートのプログラムで最も単純なのはバブルソートです。バブルソートは、次の考え方によりソートします。このように、同じ問題でも多様なアルゴリズムが存在するのです。
a[1] と a[2] を比較し、a[1] のほうが小さければそのまま、a[2] のほうが小さければ、a[1] と a[2] をスワップすれば、大きいほうが a[2] になります。次に、a[2] と a[3] を比較し、a[2] のほうが小さければそのまま、a[3] のほうが小さければ、a[2] と a[3] をスワップすることにより、a[1] ~ a[3] のうち最も大きい要素が a[3] になります。これを繰り返すことにより、最大値をもつ要素が配列の末尾 a[n] になります。
次に、末尾を除いた a[1] ~ a[n-1] について、同じ操作を行えば、2番目に大きな要素が a[n-1] に入ります。これを繰り返すことによりソートが完成します。
選択ソートと比較して、要素の添字 k を知る必要がないので、プログラムが簡素になっています。
ア for (i=1; i<=n-1; i++) { ────┐
イ for (j=1; j<=n-i; j++) { ────┐ │
ウ if (a[j] > a[j+1]) { │ │
エ w = a[j]; ┐ │ │
オ a[j] = a[j+1]; ├スワップ ├最大値 ├ソート
カ a[j+1] = w; ┘ │を末尾に │
キ } │ │
ク } ────┘ │
ケ } ────┘
トレースすると次のようになります。水の中の泡(バブル)のように、軽い(値の小さい)要素が上(左)へ、重い(大きい)要素が下(右)に移動していることがわかります。
i j a[j] a[j+1] 比較 a[1] a[2] a[3] a[4] a[5]
30 20 50 10 40
1 1 30 20 > 20 30 ↓ ↓ ↓
2 30 50 < ↓ ↓ ↓ ↓ ↓
3 50 10 > ↓ ↓ 10 50 ↓
4 50 40 > ↓ ↓ ↓ 40 50
2 1 20 30 < ↓ ↓ ↓ ↓
2 30 10 > ↓ 10 30 ↓
3 30 40 < ↓ ↓ ↓ ↓
3 1 20 10 > 10 20 30
2 20 30 < ↓ ↓ ↓
4 1 10 20 < ↓ ↓
結果 10 20 30 40 50
a[2] を a[1] と比較して、a[1] < a[2] ならば、a[2] をa[1] の後におき(そのまま)、a[1] > a[2] ならば、a[2] をa[1] の前に挿入します。a[3] については、a[1] ~a[2] と比較して、適切な位置に挿入します。
このようなことを i-1回繰り返せば、a[1] ~ a[i-1] までは昇順にソートされています。
未ソートの最初の要素 a[i] と a[1] ~ a[i-1] を比較して、
a[j-1] < a[i] < a[j]
となる個所に a[i] を挿入します。
このとき、挿入させるために a[j] ~ a[i-1] の部分を一つずらす必要があります。
プログラムは、次のようになります。
ア for (i=2; i<=n; i++) {
イ x = a[i];
ウ if (x < a[i-1]) { ────既ソート部分末尾より大ならば何もしない
エ j = 1; ────┐
オ while ( (j <= i-1) │
カ && (x >= a[j]) ) { ├a[i] < a[j] となるjを探す
キ j = j+1; │
ク } ────┘
コ for (k=i-1; k>=j; k--) { ┐
サ a[k+1] = a[k]; ├挿入をするために1つ下げる
シ } ┘
ス a[j] = x; ────挿入する
セ }
ソ }
ウは、a[i-1] までがソートされており、その最大値を持つ要素が a[i-1] なので、 a[i-1] ≦ a[i] であれば、a[i] を含めてソートされていることになるため、何もする必要がないという意味です。
エ~クでは、a[i] を挿入する個所を調べ、その添字jを求めるプロセスです。もし、a[i] がそれまでの最小値 a[1] よりも小さいときは、j=1になります。
コ~シで、添字の大きいほうからずらしているのは、小さいほうから行うと、例えば、a[2] → a[3] の後で a[3] → a[4] を行うと、a[4] も a[2] と同じ値になってしまうからです。
挿入ソートでは、「挿入をするために1つ下げる」ために、要素の移動回数が多くなるのが特徴です。
配列aの順序は次のように変化します。
i a[1] a[2] a[3] a[4] a[5]
30 20 50 10 40
2 20 30
3 20 30 50
4 10 20 30 50
5 10 20 30 40 50
上記3つの方法でソートします。経過の状況も出力されます。