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.並び替えの流れ

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

①最小値を探す
②i番目と入れ替える

①最小値を探す

最小値がm_index番目にあるとして、その要素の隣(m_index + 1)から最後の配列の最大値の要素(UBound( 配列 ))まで他の要素と比較していきます。

j番目の要素がm_index番目より小さい場合はその要素が最小値となるため、最小値の場所が変わり、m_index = jとなります。

Dim j

m_index = i '# 最小値の場所（m_index番目を最小とみなす）
For j = i + 1 To UBound( arrNum )
    If arrNum( m_index ) > arrNum(j) Then
        m_index = j
    End If
Next

②i番目と入れ替える

①で最小値を見つけることができましたので、最小値とi番目と入れ替えていきます。

If m_index <> i Then
    tmp = arrNum(i)
    arrNum(i) = arrNum(m_index)
    arrNum(m_index) = tmp 
End If

今回は2つのものを入れ替えるために、3つ箱を用意して入れ替えているイメージです。

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, m_index

'# 選択ソート前
For i = 0 To UBound( arrNum )
    tmp = join(arrNum, ",")
Next

Response.Write tmp & "<br />" '# 3,4,2,...

For i = 0 To UBound( arrNum ) - 1
    '# m_index番目以降の最小値がどこにあるのかを探す
    m_index = i '# 最小値の場所（m_index番目を最小とみなす）
    For j = i + 1 To UBound( arrNum )
        If arrNum( m_index ) > arrNum(j) Then
            m_index = j
        End If
    Next
    
    If m_index <> i Then
        '# 配列のi番目とm_index番目を入れ替える
        tmp = arrNum(i)
        arrNum(i) = arrNum(m_index)
        arrNum(m_index) = tmp 
    End If
Next

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

5.まとめ

今回は選択ソート編としてVBScriptで並び替えを行いました。

「やりたいことを分解して、コードに落とし込む」ことを意識して進めていきたいと思います。

他の方法についても整理していく予定なので、合わせて読んで頂けると幸いです。

6.参考

7.最後に

間違いやご意見等ありましたらぜひ仰ってください。

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

【VBScript】ソート方法を整理する(選択ソート編)

目次