【VBScript】ソート方法を整理する(バブルソート編)

目次

1. はじめに
2. 環境
3. 使用する配列
4. バブルソートとは
4-1. 並び替えの流れ
4-2. 最終的なコード
5. 参考
6. 最後に

1.はじめに

以前上司から「配列を”選択ソート” と”バブルソート”を使って並び替えてみて」という宿題が出たことがありました。

「ソート=IDを順番に並び替えるもの」 という印象だったので、ソートに種類があることと、処理速度の違いがあることに驚きました。

今回はその時のメモをベースに、バブルソートについて整理をしていきたいと思います。

▼選択ソート編はこちら

2.環境

• windows10 バージョン21H2
• Microsoft-IIS 10.0
• ASP 5.8（16384）

3.使用する配列

以下の配列を昇順(1,2,…,10)に並べ替えたいと思います。

▼コード

'# 配列と変数の宣言
Dim arrNum : arrNum = Array(3,4,2,8,7,5,9,6,10,1)
Dim i,tmp

'# バブルソート前の配列
For i = 0 To UBound( arrNum )
    tmp = join(arrNum, ",")
Next

'#カンマで結合した配列を出力
Response.Write tmp '# 3,4,2,...

UBound関数：配列のインデックスの最大値を取得できる

4.バブルソートとは

バブルソート（基本交換法）とはより引用

バブルソートとは、隣り合わせの値と比較して交換を繰り返していくシンプルな手法です。

バブルは「泡」のことですが、並べ替えられていく様子があたかも泡が水面に浮かび上がっていくように見えることから「バブルソート」と名前がつけられました。

4-1.並び替えの流れ

バブルソートを行うためにやることとしては、以下の3点です。
今回は昇順（小さい順）に並べていきます。

①先頭から隣り合わせの要素を比較し、条件に応じて交換を行う
②先頭に戻り、再び隣り合わせの要素を比較し、条件に応じて交換を行う
③②を繰り返してすべての比較を行う

バブルソートで調べてみると、

A:隣り合う2つの要素を比較する
B:2つの要素を比較する

と2つのパターンがありました。
今回はwikipediaを参考に隣り合う2つの要素を比較する方法をまとめます。

▼2つの要素を比較していた例

▼wikipedia

①先頭から隣り合わせの値を比較し、条件に応じて交換を行う

今回は昇順（小さい順）に並べたいので、隣り合わせの要素を比較して左の要素＞右の要素となった際に交換を行います。

常に右が大きくなるようにすることで、小さい順（昇順）に並べることができる

交換を行っていくと、配列の最後の要素は配列の中で一番大きい値となり、確定します。

②先頭に戻り、再び隣り合わせの要素を比較し、条件に応じて交換を行う

交換を行っていくと、配列の最後から2番目の要素が配列から2番目に大きい値となり、確定します。

'# 変数の宣言
Dim j

'#要素を比較して昇順になるように交換する
For i = 0 To UBound( arrNum ) - 1
    For j = i + 1 To UBound( arrNum )
        If arrNum(j) < arrNum(i) Then
            tmp = arrNum(j)
            arrNum(j) = arrNum(i)
            arrNum(i) = tmp
        End If 
    Next
Next

交換をする方法は選択ソートの時と同様です。
2つの配列の要素を入れ替えるために、空の変数tmpを宣言・用意します。

③②を繰り返してすべての比較を行う

繰り返すことですべての要素が確定します。

4-2.最終的なコード

最終的なコードはこちらになります。

<%@ Language = VBScript codepage = 65001 %>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<%
Dim arrNum : arrNum = Array(3,4,2,8,7,5,9,6,10,1)
Dim tmp
Dim i, j

'# バブルソート前
For i = 0 To UBound( arrNum )
    tmp = join(arrNum, ",")
Next
Response.Write tmp & "<br />" '# 3,4,2,...,1

'#要素を比較して昇順になるように交換する
For i = 0 To UBound( arrNum ) - 1
    For j = i + 1 To UBound( arrNum )
        If arrNum(j) < arrNum(i) Then
            tmp = arrNum(j)
            arrNum(j) = arrNum(i)
            arrNum(i) = tmp
        End If 
    Next
Next

'# バブルソート後
For i = 0 To UBound( arrNum )
    tmp = join(arrNum, ",")
Next
Response.Write tmp & "<br />" '# 1,2,3,...,10
%>

5.参考

6.最後に

今回はバブルソート編としてVBScriptで並び替えを行いました。並び替えにかかる時間はデータ数の2乗にほぼ比例するとのことで、時間を要する方法となります。

短時間での並び替え方法についても整理していこうと思うので、合わせて読んで頂けると幸いです。
間違いやご意見等ありましたらぜひ仰ってください。

読んでいただき、ありがとうございました。