伊田生活ブログのロゴ
HOME  >  勉強
カテゴリー : 勉強 - プログラミング
•VBScript •バブルソート •配列



公開日:
最終更新日:

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


img_9

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


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

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

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


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

[前準備.vbs]
Call main()

Sub main()
  Dim arr(3) '要素数4の配列
  '配列に整数を格納する
  arr(0) = 13
  arr(1) = 32
  arr(2) = 1
  arr(3) = 6
   
  arrStr = ""  '配列の中身を見るための変数
  maxIndex = UBound(arr)
  For i = 0 To maxIndex
    arrStr = arrStr & "(" & arr(i) & ")"
  Next
  
  '配列の中身を表示する
  MsgBox(arrStr)
End Sub

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

[図.1]
img_1

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


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

[bubble_sort.vbs]
Call main()

Sub main()
  Dim arr(3) '要素数4の配列
  '配列に整数を格納する
  arr(0) = 13
  arr(1) = 32
  arr(2) = 1
  arr(3) = 6

  Call bubbleSort(arr)    'バブルソートを実行する

  arrStr = ""  '配列の中身を見るための変数
  maxIndex = UBound(arr)
  For i = 0 To maxIndex
    arrStr = arrStr & "(" & arr(i) & ")"
  Next
  
  '配列の中身を表示する
  MsgBox(arrStr)
End Sub


'バブルソートを実行するプロシージャ
Sub bubbleSort(Byref arr)
  maxIndex = UBound(arr)
  for i = 1 to maxIndex
    for j = 0 to (maxIndex - i)
      If arr(j) > arr(j + 1) Then
        tmp = arr(j)
        arr(j) = arr(j + 1)
        arr(j + 1) = tmp
      End If
    Next
  Next
End Sub

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

[図.2]
img_2

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


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

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

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

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

for i = 1 to maxIndex
    for j = 0 to (maxIndex - i)

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

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

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

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


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

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

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

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

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

[図.3]
img_3
①では、13と32を比較します。13の方が小さいので、入れ替えません。
②では、32と1を比較します。32の方が大きいので、入れ替えます。
③では、32と6を比較します。32の方が大きいので、入れ替えます。

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

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

[図.4]
img_4
[図.5]
img_5

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

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

[図.6]
img_6

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

[図.7]
img_7

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

[図.8]
img_8

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