【VBScript】１次元配列を並び替える（選択ソート）

Windows PC
2021.04.09

こんにちは、ふみです。みなさんは VBScript で配列を並び替えようと思ったことはありますか？

私はプログラムで1次元配列を並び替えるときはクイックソート、2次元配列を並び替える時はマージソートと挿入ソートを組み合わせたものを使います。
クイックソートとマージソートは1万件を超えるような配列のデータでも、ソート（データの並び替え）が速いので便利です。

しかし、今回はソートがそれほど速くない「選択ソート」を使って1次元配列をソートする方法ついて紹介します。

ソートがとても速い記事はこちら：
【VBScript】１次元配列を短時間で並び替える（クイックソート）
【VBScript】２次元配列を短時間で並び替える（安定ソート）

選択ソートのしくみ

選択ソートの動作のしくみは次のとおりです。

１．
配列の全ての要素の中で一番小さい（大きい）要素と、添字0番の要素を交換すると、添字0番の要素が最小（最大）値として確定する。

２．
配列の0番を除く全ての要素の中で一番小さい（大きい）要素と、添字1番の要素を交換すると、添字1番の要素が2番目に小さい（大きい）値として確定する。

３．
配列の0番と1番を除く全ての要素の中で一番小さい（大きい）要素と、添字2番の要素を交換すると、添字2番の要素が3番目に小さい（大きい）値として確定する。
これを最後の添字の1つ前まで繰り返すと、配列要素の全ての順番が確定する。

４．
以降、同様の手順で最後の添字の1つ前まで順番の確定を繰り返すと、最後の添字の要素が最大（最小）値となり、配列要素の全ての順番が確定する。

この手順をプログラム用に効率化したものが選択ソートのプログラムです。

選択ソートはアルゴリズムが単純でバブルソートよりも処理が速いのですが、2000件を超える大きなデータの並び替えになると、並び替え処理にかかる時間が目立つようになります。
既存のプログラムで2000件を超えるデータの並び替えに選択ソートを使っているものがあった場合、ソートアルゴリズムをクイックソート等に交換することで処理時間を大幅に短縮することができます。

選択ソートは重複する値を含む（排他的でない）配列をソートした時に順番が入れ替わるソートです。（不安定ソート）
2次元配列のソートに選択ソートを使用した場合、重複データの順番が入れ替わる可能性があるので注意しましょう。

1次元配列を昇順に並び替える

1次元配列を昇順に並び替えるプログラムは次のとおりです。

サンプルコード

Option Explicit
Dim varArray, sngTime, lngN
ReDim varArray(1999)
For lngN = Lbound(varArray) To Ubound(varArray)
    varArray(lngN) = Int(Rnd * (UBound(varArray) + 1) * 10)
Next
sngTime = Timer
Call SelectionSort1D(varArray, Lbound(varArray), Ubound(varArray))
MsgBox ConfirmationTextForArray1D(varArray), , _
    "並び替え処理の時間（秒）：" & Round(Timer - sngTime, 3)
WScript.Quit
'******************************************************************************
'1次元配列varArray1DのlngLowerからlngUpperまでの範囲を選択ソート（昇順）
Sub SelectionSort1D(ByRef varArray1D, ByVal lngLower, ByVal lngUpper)
    Dim lngI, lngJ, varSwap, lngMin
    
    For lngI = lngLower To lngUpper - 1
        lngMin = lngI
        For lngJ = lngI + 1 To lngUpper
            If varArray1D(lngJ)  LBound(strArray1D) Then
            strTemp = strTemp & vbCrLf '改行の追加
        End If
        If c_intI >= 1 And intN >= c_intI + LBound(strArray1D) Then '上限超過時
            strTemp = strTemp & "他" & UBound(strArray1D) - (c_intI - 1)
            Exit For
        Else
            strTemp = strTemp & "配列(" & intN & ") = " & strArray1D(intN)
        End If
    Next
    ConfirmationTextForArray1D = strTemp
End Function

上記のコードを Windows 10 のアクセサリから開いたメモ帳へコピー＆ペースト後、文字コードを「ANSI」に設定し、適当なファイル名に拡張子「.vbs」をつけてデスクトップ等に保存すると、すぐに動作確認できます。
保存した vbsファイルをダブルクリックすると、要素数2,000の配列をランダムの整数値で作成後、選択ソートが行われ、昇順でソートされた配列データの若番10件と配列のソート時間（秒）がメッセージで表示されます。

解説

4～7行目は要素数2,000の配列を0～19,999の範囲のランダムの整数値で作成しています。

8行目は Timer関数でソート前の基準の秒数を取得しています。

9行目は15行目のアスタリスク(*)以下に記載しているプロシージャを使って配列varArray を昇順でソートしています。

10～11行目は30行目のアスタリスク(*)以下に記載している1次元配列のデータをメッセージ表示用の文字列で返すファンクションを使ってソート後の配列を表示すると同時に、Timer関数を使ってソート時間を表示しています。

17～29行目は選択ソートのプロシージャです。

20～28行目の For ～ Next は添字の最小値から最大値 – 1までループします。比較範囲の要素の最小値を代入する添字を決定します。

21行目の変数lngMin は要素の暫定の最小値の添字を代入します。

22～24行目の For ～ Next は最小値を代入する添字 + 1 から添字の最大値までループします。要素を比較する添字を決定します。

23行目は暫定の最小値より小さい要素を見つけた時、要素の暫定の最小値の添字を更新します。

25～27行目は比較範囲の要素の最小値を比較範囲の最小の添字の要素と交換します。

30行目のアスタリスク(*)以下に記載しているファンクションは【VBScript】プロシージャとファンクション（関数）の使い方で紹介したものを転用しています。

この選択ソートのプロシージャは Excel等の VBA でも動作します。

1次元配列を降順に並び替える

1次元配列を降順に並び替えるプログラムは次のとおりです。

サンプルコード

Option Explicit
Dim varArray, sngTime, lngN

ReDim varArray(1999)
For lngN = Lbound(varArray) To Ubound(varArray)
    varArray(lngN) = Int(Rnd * (UBound(varArray) + 1) * 10)
Next
sngTime = Timer
Call SelectionReverse1D(varArray, Lbound(varArray), Ubound(varArray))
MsgBox ConfirmationTextForArray1D(varArray), , _
    "並び替え処理の時間（秒）：" & Round(Timer - sngTime, 3)
WScript.Quit


'******************************************************************************
'1次元配列varArray1DのlngLowerからlngUpperまでの範囲を選択ソート（降順）
Sub SelectionReverse1D(ByRef varArray1D, ByVal lngLower, ByVal lngUpper)
    Dim lngI, lngJ, varSwap, lngMin
    
    For lngI = lngLower To lngUpper - 1
        lngMin = lngI
        For lngJ = lngI + 1 To lngUpper
            If varArray1D(lngJ) > varArray1D(lngMin) Then lngMin = lngJ
        Next
        varSwap = varArray1D(lngMin)
        varArray1D(lngMin) = varArray1D(lngI)
        varArray1D(lngI) = varSwap
    Next
End Sub
'******************************************************************************
'処　　理：1次元配列のデータをメッセージ表示用の文字列で返す
'
'戻 り 値：メッセージ表示用の文字列
'
'引　　数：strArray1D - 1次元配列
'
'備　　考：配列の要素数が表示させる個数の上限を超えた分は残りを省略
'
Function ConfirmationTextForArray1D(ByRef strArray1D)
    Dim intN, strTemp
    Const c_intI = 10 '表示させる個数の上限
    
    For intN = LBound(strArray1D) To UBound(strArray1D)
        If intN > LBound(strArray1D) Then
            strTemp = strTemp & vbCrLf '改行の追加
        End If
        If c_intI >= 1 And intN >= c_intI + LBound(strArray1D) Then '上限超過時
            strTemp = strTemp & "他" & UBound(strArray1D) - (c_intI - 1)
            Exit For
        Else
            strTemp = strTemp & "配列(" & intN & ") = " & strArray1D(intN)
        End If
    Next
    ConfirmationTextForArray1D = strTemp
End Function

上記のコードを Windows 10 のアクセサリから開いたメモ帳へコピー＆ペースト後、文字コードを「ANSI」に設定し、適当なファイル名に拡張子「.vbs」をつけてデスクトップ等に保存すると、すぐに動作確認できます。
保存した vbsファイルをダブルクリックすると、要素数2,000の配列をランダムの整数値で作成後、バブルソートが行われ、降順でソートされた配列データの若番10件と配列のソート時間（秒）がメッセージで表示されます。

解説

9行目は15行目のアスタリスク(*)以下に記載しているプロシージャを使って配列varArray を降順でソートしています。プロシージャの名前が昇順のときと変わっています。

23行目は不等号の向きが昇順ソートのときの逆になっています。

その他は昇順でソートするときと同じです。

まとめ

  • 選択ソートはクイックソートやマージソートに比べると速くない
  • 既存のプログラムが2000件を超えるデータの並び替えに選択ソートを使っていた場合、クイックソートに交換することで処理時間を大幅に短縮することができる
  • 2次元配列のソートに選択ソート（不安定ソート）を使用した場合、重複データの順番が入れ替わる可能性がある

ありがとうございました。

ソートがとても速い記事はこちら：
【VBScript】１次元配列を短時間で並び替える（クイックソート）
【VBScript】２次元配列を短時間で並び替える（安定ソート）

スポンサーリンク

コメント

タイトルとURLをコピーしました