VBScriptでバブルソートを復習する

ソートの基本とされるバブルソートの流れを、VBScriptのコードで考えてみます。VBScriptはWindowsなら特別なソフトをインストールしなくても動かせるので便利です。

バブルソートは、ソートの中で最も基本的なものの一つ とされているようです。

僕は、大学のC言語の授業でバブルソートを習った記憶がありますが、あまり理解できませんでした。そのまま、理解することがないまま、使うこともないまま、15年ほど経ってしまいました。僕の今後の職業人生においてバブルソートを使うことはないでしょう。

しかし、プログラミングの基本とされているバブルソートについて、復習してみます。

この記事では、13、32、1、6 という 4つの数字 を昇順(小さい順)に並べ替えるコードを検討します。その準備として、数字を格納した配列を用意します。次のコードは、4つの数字を配列に格納したあと、中身を表示するプログラムです。

結果は図.1のようになります。

次に、これらの要素をバブルソートで昇順に並べ替えます。並べ替えた後は ”(1) (6) (13) (32)” という並びになるはずです。

#前準備.vbsに、バブルソートを実行するための関数を追加します。

黄色く塗った個所は、#前準備.vbsに追加した、バブルソートのための処理です。とりあえず実行してみます。結果は次のようになります(図.2)。

期待通りの結果になりました。

ソートの基本とされるバブルソートですが、難しいと感じる人は多いようです。難しいと感じるのは、次のような理由があると思います。

• ループが2重になっている
• ループの部分の記述がややこしい（書く人によって書き方がバラバラ）

#bubble_sort.vbsでは、変数iのループの内側に、変数jのループがあります。for文だけでも難しいのに、それが2重になるとさらに難しく感じます。

#bubble_sort.vbsでは、変数iとjのforの部分を次のように書いています。

この部分の記述方法は、いろんなバブルソートのコードの例を見ればわかるように、いろんなパターンがあります。書く人によって書き方がバラバラです。このことが、バブルソートが難しいと感じる一番の理由な気がします。僕も長い間バブルソートは難しいと思っていました。しかし、人が書いたバブルソートのコードを読むにあたって、以下の点を意識して読むことで、バブルソートの流れを理解できるようになりました。

• ループを左から実行するか、右から実行するか（ループの方向）
• ループを何回実行するか（ループの回数）
• どこからどこまでループするか（ループの範囲）

逆にいえば、以前は上述の点をあいまいにしたまま読んでいたので、コードが実態以上に難解なものに見えていたのだと思います。

ループの処理の書き方にはいろんなパターンがありますが、そのすべてを理解する必要はなく、自分が理解しやすいと思う書き方で書かれたコードを一つだけ理解できれば、まずは十分だと思います。

これ以降、変数iによる外側のループを「外側ループ」、変数jによる内側のループを「内側ループ」といいます。

#bubble_sort.vbsのバブルソートの処理の流れをざっくりと説明すると、以下のようになります。

• 左から右に見ていく。
• 内側ループでは左右の大きさを一つずつ比較し、大きいほうを右に移動する。
• 1回目の外側ループで、1番右側が確定する。
• 1番右側には最も大きい数値が来る。
• 2回目の外側ループでは、1番右側は1番大きい数値として確定しているので、比較の対象外とする。
• 2回目の外側ループで、右から2番目が確定する。
• 3回目の外側ループで、右から3番目が確定する。

この記事の例では、変数iが外側ループの現在の回数を、変数jが内側ループの現在の回数を意味します。

外側ループ1回目の流れを図.3に示します。

以上で1回目のループが完了です。1番右側が確定しました。

外側ループ2回目～3回目の流れを図.4、図.5に示します。処理の流れは外側ループ1回目(#図.3)と同じです。

外側ループを3回実行し、バブルソートが完了しました。

この記事では、並べ替える数字の数は4つです。一番左の数字から見て、自分よりも右側の3つの数字を確定させればよいので、外側ループは3回実行すればよいことになります(図.6)。

内側ループの回数は、「外側ループが今何回目なのか」によって変わります。どういうことなのか、図.7に示します。

内側ループの変数jは、ループの回数だけでなく、左と右の比較にも関わる変数です(図.8)。したがって、変数jは変数iに比べて手ごわいです。

VBScriptで、バブルソートを復習してみました。ソートを理解するにあたっては、抽象的な概念から理解しようとすると難しく感じるので、まず具体例で考えるのがいいと思います。今回の例では、13、32、1、6 という4つの数字を、具体例として使いました。