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



# 目次

[1. はじめに](#1はじめに)
[2. 環境](#2環境)
[3. 使用する配列](#3使用する配列)
[4. 選択ソートとは](#4選択ソートとは)
[4-1. 並び替えの流れ](#4-1並び替えの流れ)
[4-2. 最終的なコード](#4-2最終的なコード)
[5. まとめ](#5まとめ)
[6. 参考](#6参考)
[7. 最後に](#7最後に)


# 1.はじめに

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

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

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


# 2.環境

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


# 3.使用する配列

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

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/689555/4916cfd4-39b0-eda0-9d70-ba6a3dd5206f.png" width=80%>

▼コード

```vb
'# 配列と変数の宣言
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,...
```

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


# 4.選択ソートとは

[選択ソート（基本選択法）](https://medium-company.com/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88/)とはより引用

>選択ソートとは対象となるデータの中から最小値（もしくは最大値）を探し先頭の値と交換、この作業を繰り返すことで全体を整列させていく手法です。

これを最後の要素の一つ手前まで行うと、最後の要素が確定して全体が整列します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/689555/8ca9c555-73d4-c164-10d2-4a5a3dc050ec.png" width=80%>


## 4-1.並び替えの流れ

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

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

①最小値を探す

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

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

```vb
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番目と入れ替えていきます。

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

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

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/689555/f9163451-660d-bf4e-cc9a-d4982e8df5fc.png" width=80%>


## 4-2.最終的なコード

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

```vb
<%@ 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.参考

https://www3.cuc.ac.jp/~miyata/classes/prg1/11/selsort.html

https://fcf.tokyo/windows-pc/vbs16/

https://www.youtube.com/watch?v=vY1g_CdSwh4


# 7.最後に

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

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