目次
1. はじめに
2. 環境
3. 使用する配列
4. 選択ソートとは
4-1. 並び替えの流れ
4-2. 最終的なコード
5. まとめ
6. 参考
7. 最後に
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.最後に
間違いやご意見等ありましたらぜひ仰ってください。
読んでいただき、ありがとうございました。