ソートの基本とされるバブルソートの流れを、VBScriptのコードで考えてみます。VBScriptはWindowsなら特別なソフトをインストールしなくても動かせるので便利です。
バブルソートは、ソートの中で最も基本的なものの一つ とされているようです。
僕は、大学のC言語の授業でバブルソートを習った記憶がありますが、あまり理解できませんでした。そのまま、理解することがないまま、使うこともないまま、15年ほど経ってしまいました。僕の今後の職業人生においてバブルソートを使うことはないでしょう。
しかし、プログラミングの基本とされているバブルソートについて、復習してみます。
この記事では、13、32、1、6 という 4つの数字 を昇順(小さい順)に並べ替えるコードを検討します。その準備として、数字を格納した配列を用意します。次のコードは、4つの数字を配列に格納したあと、中身を表示するプログラムです。
[前準備.vbs]結果は図.1のようになります。
[図.1]
次に、これらの要素をバブルソートで昇順に並べ替えます。並べ替えた後は ”(1) (6) (13) (32)” という並びになるはずです。
#前準備.vbsに、バブルソートを実行するための関数を追加します。
[bubble_sort.vbs]黄色く塗った個所は、#前準備.vbsに追加した、バブルソートのための処理です。とりあえず実行してみます。結果は次のようになります(図.2)。
[図.2]
期待通りの結果になりました。
ソートの基本とされるバブルソートですが、難しいと感じる人は多いようです。難しいと感じるのは、次のような理由があると思います。
#bubble_sort.vbsでは、変数iのループの内側に、変数jのループがあります。for文だけでも難しいのに、それが2重になるとさらに難しく感じます。
#bubble_sort.vbsでは、変数iとjのforの部分を次のように書いています。
この部分の記述方法は、いろんなバブルソートのコードの例を見ればわかるように、いろんなパターンがあります。書く人によって書き方がバラバラです。このことが、バブルソートが難しいと感じる一番の理由な気がします。僕も長い間バブルソートは難しいと思っていました。しかし、人が書いたバブルソートのコードを読むにあたって、以下の点を意識して読むことで、バブルソートの流れを理解できるようになりました。
逆にいえば、以前は上述の点をあいまいにしたまま読んでいたので、コードが実態以上に難解なものに見えていたのだと思います。
ループの処理の書き方にはいろんなパターンがありますが、そのすべてを理解する必要はなく、自分が理解しやすいと思う書き方で書かれたコードを一つだけ理解できれば、まずは十分だと思います。
これ以降、変数iによる外側のループを「外側ループ」、変数jによる内側のループを「内側ループ」といいます。
#bubble_sort.vbsのバブルソートの処理の流れをざっくりと説明すると、以下のようになります。
この記事の例では、変数iが外側ループの現在の回数を、変数jが内側ループの現在の回数を意味します。
外側ループ1回目の流れを図.3に示します。
[図.3]
以上で1回目のループが完了です。1番右側が確定しました。
この記事では、並べ替える数字の数は4つです。一番左の数字から見て、自分よりも右側の3つの数字を確定させればよいので、外側ループは3回実行すればよいことになります(図.6)。
[図.6]
内側ループの回数は、「外側ループが今何回目なのか」によって変わります。どういうことなのか、図.7に示します。
[図.7]
内側ループの変数jは、ループの回数だけでなく、左と右の比較にも関わる変数です(図.8)。したがって、変数jは変数iに比べて手ごわいです。
VBScriptで、バブルソートを復習してみました。ソートを理解するにあたっては、抽象的な概念から理解しようとすると難しく感じるので、まず具体例で考えるのがいいと思います。今回の例では、13、32、1、6 という4つの数字を、具体例として使いました。
