【VBScript】2次元配列を短時間で並び替える(安定ソート)

Windows PC

こんにちは、ふみです。みなさんは VBScript で2次元配列を並び替えに時間がかかりすぎると思ったことはありますか?

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

今回はマージソートと挿入ソートを組み合わせたものを使って2次元配列をソートする方法ついて紹介します。

2次元配列の並べ替えについて

重複データは安定ソートを使う

2次元配列の並べ替えで注意しなければならない点は、並べ替えの対象における重複データの有無です。

例えば、2次元配列の要素に120円のりんごと100円のりんごがあるときに、値段で並び替えた後に商品名で並び替えるとします。

並び替えの方法が安定ソートの場合、りんご100円、りんご120円の順番になります。しかし、不安定ソートの場合は重複データのある商品名で並び替えた時に、りんご120円、りんご100円と、値段の順番が崩れてしまう可能性があります

よって、並べ替えの対象に重複データがある場合、並び替えのアルゴリズムは安定ソートを使う必要があります。2次元配列の並び替えは安定ソート推奨と覚えておきましょう。

重複データが無い(排他的の)場合の並び替えはクイックソート等の不安定なソートでも問題ありません。

並び替える前の添字(INDEX)の配列をつくる

2次元配列では要素の並び替えの時に他の項目も同時に連動して要素の入れ替えをした場合、配列の項目の数に比例して要素を入れ替える回数が増えます。

これは2次元配列を Microsoft Excel のワークシートに例えると、2列の配列を縦方向に選択範囲を拡張して並び替える場合に比べて、20列の配列を縦方向に選択範囲を拡張して並び替えると要素の入れ替え回数が 20÷2=10倍に増える状態です。

そこで、要素の入れ替え回数を減らす(ソート時間を短縮する)為に、並び替える要素以外の全ての要素を並び替える前の添字(ソート以前のINDEX)に置き換える方法を使います。

まず、並び替える要素以外の全ての要素を一つの添字(ソート以前のINDEX)に置き換えます。
次に、要素の並び替えの時、ソート以前のINDEXも同時に並び替えます。
最後に、ソート以前のINDEXを参照して2次元配列の要素をまとめて入れ替えます。

この方法は、2次元配列でソートしない方向の要素数が3以上のときに、入れ替え回数を減らす(ソート時間を短縮する)効果があります

ソートのしくみ

マージソート

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

1.
配列の添字0番と1番を比較して2つの要素を順番に並べる。添字2番と3番を比較して2つの要素を順番に並べる。添字4番と5番を比較…
これを最後の添字まで繰り返す。

2.
添字0番と1番の配列と2番と3番の配列の若番を比較して4つの要素を順番に並べる。添字4番と5番の配列と6番と7番の配列の若番を比較…
これを最後の添字まで繰り返す。

3.
添字0~3番の配列と4~7番の配列の若番を比較し8つの要素を順番に並べる。添字8~11番の配列と12~15番の配列の若番を比較…
これを最後の添字まで繰り返す。

4.
以降、同様の手順で配列要素の全てが順番につながるまで続ける

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

マージソートは大きなデータにおいて短時間で並び替えができるのが特徴です。
マージソートは重複する値を含む(排他的でない)配列をソートした時に順番が入れ替わらないソートです。(安定ソート)

挿入ソート

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

1.
配列の添字の若番(0番)の要素と次(1番)の要素を比較し、入れ替える。

2.
その次(2番)の要素と、左側の配列(0~1番)の要素を比較し、順番になる位置に要素を挿入する。さらに次(3番)の要素と、左側の配列(0~2番)の要素を比較…
これを配列の最後になるまで、要素の比較と挿入を繰り返す。

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

挿入ソートは少ないデータにおいて短時間で並び替えができるのが特徴です。
挿入ソートもマージソートと同様に、重複する値を含む(排他的でない)配列をソートした時に順番が入れ替わらないソートです。(安定ソート)

マージソートと挿入ソートの組み合わせ

マージソートと挿入ソートの長所を生かして、配列のデータが多いときはマージソートを使い、マージソートの配列の分割でデータが少なくなったときに挿入ソートへ切り替えると、短時間で並び替える安定ソートを実現することができます。動作のしくみは次のとおりです。

1.
配列の要素の数を確認し、閾値(しきいち)以下の時は挿入ソートで配列を並べ替えて終了。閾値より多い時は配列を左右に分割した各配列を1.からの順序でやり直す(再帰処理)。

2.
1.で左右に分割した各配列の並び替えが完了しているので、左右の配列を若番から順に値を比較して、新しい配列に並べ替える。

この手順をプログラム用に効率化したものが今回紹介する、マージソートと挿入ソートを組みわせたプログラムです。配列の分割で少なくなった並び替えを挿入ソートに切り替えることにより、マージソートよりも短時間で並び替えることができます。

2次元配列を2番目の次元の範囲で昇順に並び替える(安定ソート)

2次元配列を2番目の次元の範囲(Microsoft Excel のワークシートの配列では横方向)で昇順に並び替えるプログラムは次のとおりです。

サンプルコード

Option Explicit
Dim varArray, sngTime, lngN1, lngN2

ReDim varArray(2, 16383)
For lngN1 = LBound(varArray, 1) To UBound(varArray, 1)
    For lngN2 = LBound(varArray, 2) To UBound(varArray, 2)
        varArray(lngN1, lngN2) = Int(Rnd * ((UBound(varArray, 1) + 1) _
            * (UBound(varArray, 2) + 1) + 1))
    Next
Next
sngTime = Timer
Call MergeSort2D(varArray, 0, 16383, 2, 2)
Call MergeSort2D(varArray, 0, 16383, 2, 1)
Call MergeSort2D(varArray, 0, 16383, 2, 0)
MsgBox ConfirmationTextForArray2D(varArray, False, True), , _
    "並び替え処理の時間(秒):" & Round(Timer - sngTime, 3)
WScript.Quit


'******************************************************************************
'処  理:2次元配列のデータを昇順に並び替える(マージソート、挿入ソート)
'
'引  数:varArray2D - 2次元配列
'          lngLower - 並び替え範囲下限の添字(INDEX)
'          lngUpper - 並び替え範囲上限の添字
'          intDimension - 並び替え範囲の添字の次元
'          lngTgtIndex - 並び替えの基準となる添字(intDimensionでない次元)
'
'備  考:関数 MergeSortedArray2D、InsertionSortedArray2D を使用
'
Sub MergeSort2D(ByRef varArray2D, ByVal lngLower, ByVal lngUpper _
        , ByVal intDimension, ByVal lngTgtIndex)
    Dim lngRange, lngI, lngJ, lngN1, lngN2
    Dim varTgtArray, varSortedArray, varNewArray2D
    
    lngRange = lngUpper - lngLower
    If lngRange = 0 Then Exit Sub 'ソート不要
    
    ReDim varTgtArray(1, lngRange) '並べ替える要素とソートする前の添字の配列
    Select Case intDimension
    Case 1
        For lngN1 = lngLower To lngUpper
            lngI = lngN1 - lngLower
            varTgtArray(0, lngI) = varArray2D(lngN1, lngTgtIndex)
            varTgtArray(1, lngI) = lngN1 'ソートする前の添字
        Next
        If lngTgtIndex  UBound(varArray2D, 2) Then
            Error 13 '引数が不正
        End If
    Case 2
        For lngN2 = lngLower To lngUpper
            lngI = lngN2 - lngLower
            varTgtArray(0, lngI) = varArray2D(lngTgtIndex, lngN2)
            varTgtArray(1, lngI) = lngN2 'ソートする前の添字
        Next
        If lngTgtIndex  UBound(varArray2D, 1) Then
            Error 13 '引数が不正
        End If
    Case Else
        Error 13 '引数が不正
    End Select
    If lngLower  UBound(varArray2D, intDimension) Then
        Error 13 '引数が不正
    End If
    
    varSortedArray = MergeSortedArray2D(varTgtArray, 0, lngRange)
    
    Select Case intDimension
    Case 1
        ReDim varNewArray2D(lngRange _
            , UBound(varArray2D, 2) - LBound(varArray2D, 2))
        For lngI = 0 To UBound(varSortedArray, 2)
            For lngN2 = LBound(varArray2D, 2) To UBound(varArray2D, 2)
                lngJ = lngN2 - LBound(varArray2D, 2)
                varNewArray2D(lngI, lngJ) _
                    = varArray2D(varSortedArray(1, lngI), lngN2)
            Next
        Next
    Case 2
        ReDim varNewArray2D(UBound(varArray2D, 1) - LBound(varArray2D, 1) _
            , lngRange)
        For lngI = 0 To UBound(varSortedArray, 2)
            For lngN1 = LBound(varArray2D, 1) To UBound(varArray2D, 1)
                lngJ = lngN1 - LBound(varArray2D, 1)
                varNewArray2D(lngJ, lngI) _
                    = varArray2D(lngN1, varSortedArray(1, lngI))
            Next
        Next
    Case Else
    End Select
    If LBound(varArray2D, 1) = 0 And LBound(varArray2D, 2) = 0 _
            And UBound(varArray2D, 1) = UBound(varNewArray2D, 1) _
            And UBound(varArray2D, 2) = UBound(varNewArray2D, 2) Then
        On Error Resume Next
        varArray2D = varNewArray2D '引数が配列として宣言されていた場合はエラー
        If Err.Number = 0 Then
            On Error GoTo 0
            Exit Sub
        End If
        On Error GoTo 0
    End If
    
     '引数が配列として宣言されていた場合の処理
    Select Case intDimension
    Case 1
        For lngN1 = lngLower To lngUpper
            lngI = lngN1 - lngLower
            For lngN2 = LBound(varArray2D, 2) To UBound(varArray2D, 2)
                lngJ = lngN2 - LBound(varArray2D, 2)
                varArray2D(lngN1, lngN2) = varNewArray2D(lngI, lngJ)
            Next
        Next
    Case 2
        For lngN2 = lngLower To lngUpper
            lngI = lngN2 - lngLower
            For lngN1 = LBound(varArray2D, 1) To UBound(varArray2D, 1)
                lngJ = lngN1 - LBound(varArray2D, 1)
                varArray2D(lngN1, lngN2) = varNewArray2D(lngJ, lngI)
            Next
        Next
    Case Else
    End Select
End Sub
'******************************************************************************
'処  理:2次元配列を並び替え範囲で縮小し、昇順に並び替える(マージソート)
'
'戻 り 値:次元1の0番を基準に昇順で並び変えた2次元配列(並び替え範囲外は除外)
'
'引  数:varTgtArray2D - 2次元配列
'          lngTgtLower - 並び替え範囲下限の添字(INDEX)
'          lngTgtUpper - 並び替え範囲上限の添字
'
'備  考:MergeSort2D専用の関数1/2
'
Function MergeSortedArray2D(ByRef varTgtArray2D, ByVal lngTgtLower _
        , ByVal lngTgtUpper)
    Dim lngTgtRange, lngSep, lngI, lngJ, lngN1, lngN2, lngLZ, lngRZ
    Dim varLeftArray, varRightArray, varTempArray
    
    lngTgtRange = lngTgtUpper - lngTgtLower
    If lngTgtRange = 0 Then
        ReDim varTempArray(1, 0)
        varTempArray(0, 0) = varTgtArray2D(0, lngTgtLower)
        varTempArray(1, 0) = varTgtArray2D(1, lngTgtLower)
        MergeSortedArray2D = varTempArray
        Exit Function
    ElseIf lngTgtRange <= 20 Then '閾値以下で挿入ソートを実行         MergeSortedArray2D = InsertionSortedArray2D(varTgtArray2D _             , lngTgtLower, lngTgtUpper)         Exit Function     Else 'マージソートを実行         lngSep = Int((lngTgtLower + lngTgtUpper) / 2)         varLeftArray = MergeSortedArray2D(varTgtArray2D, lngTgtLower, lngSep)         varRightArray _             = MergeSortedArray2D(varTgtArray2D, lngSep + 1, lngTgtUpper)         ReDim varTempArray(1, lngTgtRange)         lngI = 0: lngJ = 0         lngLZ = UBound(varLeftArray, 2): lngRZ = UBound(varRightArray, 2)         For lngN1 = 0 To lngTgtRange             If lngJ> lngRZ Then '右の配列が終わった時
                For lngN2 = lngN1 To lngTgtRange '左の配列の残り全部を代入
                    varTempArray(0, lngN2) = varLeftArray(0, lngI)
                    varTempArray(1, lngN2) = varLeftArray(1, lngI)
                    lngI = lngI + 1
                Next
                Exit For
            ElseIf lngI > lngLZ Then '左の配列が終わった時
                For lngN2 = lngN1 To lngTgtRange '右の配列の残り全部を代入
                    varTempArray(0, lngN2) = varRightArray(0, lngJ)
                    varTempArray(1, lngN2) = varRightArray(1, lngJ)
                    lngJ = lngJ + 1
                Next
                Exit For
            ElseIf varLeftArray(0, lngI) <= varRightArray(0, lngJ) Then
                varTempArray(0, lngN1) = varLeftArray(0, lngI)
                varTempArray(1, lngN1) = varLeftArray(1, lngI)
                lngI = lngI + 1
            Else
                varTempArray(0, lngN1) = varRightArray(0, lngJ)
                varTempArray(1, lngN1) = varRightArray(1, lngJ)
                lngJ = lngJ + 1
            End If
        Next
        MergeSortedArray2D = varTempArray
    End If
End Function
'******************************************************************************
'処  理:2次元配列を並び替え範囲で縮小し、昇順に並び替える(挿入ソート)
'
'戻 り 値:次元1の0番を基準に昇順で並び変えた2次元配列(並び替え範囲外は除外)
'
'引  数:varTgtArray2D - 2次元配列
'          lngTgtLower - 並び替え範囲下限の添字(INDEX)
'          lngTgtUpper - 並び替え範囲上限の添字
'
'備  考:MergeSort2D専用の関数2/2
'
Function InsertionSortedArray2D(ByRef varTgtArray2D, ByVal lngTgtLower _
        , ByVal lngTgtUpper)
    Dim lngI, lngJ, varTemp0, varTemp1, varTempArray, lngTgtRange
    
    lngTgtRange = lngTgtUpper - lngTgtLower
    ReDim varTempArray(1, lngTgtRange)
    For lngI = 0 To lngTgtRange
        varTempArray(0, lngI) = varTgtArray2D(0, lngTgtLower + lngI)
        varTempArray(1, lngI) = varTgtArray2D(1, lngTgtLower + lngI)
    Next
    For lngI = 1 To lngTgtRange
        varTemp0 = varTempArray(0, lngI) '基準値
        varTemp1 = varTempArray(1, lngI)
        
        For lngJ = lngI - 1 To 0 Step -1
            If varTempArray(0, lngJ) <= varTemp0 Then Exit For                          varTempArray(0, lngJ + 1) = varTempArray(0, lngJ) '老番へ1移動             varTempArray(1, lngJ + 1) = varTempArray(1, lngJ)         Next         varTempArray(0, lngJ + 1) = varTemp0 '基準値を挿入         varTempArray(1, lngJ + 1) = varTemp1              Next     InsertionSortedArray2D = varTempArray End Function '****************************************************************************** '処  理:2次元配列のデータをメッセージ表示用の文字列に変換する ' '戻 り 値:メッセージ表示用の文字列 ' '引  数:strArray2D - 2次元配列 '          boolCS - True = 列間をカンマ区切り、False = 列間をTab区切り '          boolVertical - True = 2番目の次元を縦表示、False = 横表示 ' '備  考:配列の要素数が行列数の上限を超えた分は残りを省略 ' Function ConfirmationTextForArray2D(ByRef strArray2D, ByVal boolCS _                                     , ByVal boolVertical)     Dim intN1, intN2, strTemp, strSeparate, intD1, intD2     Const c_intIy = 10 '行数の上限     Const c_intIx = 10 '列数の上限          If boolCS = True Then         strSeparate = "," 'カンマ区切り     Else         strSeparate = Chr(9) 'Tab区切り     End If     If boolVertical = True Then         intD1 = 1: intD2 = 2 '2番目の次元を縦表示にする変数設定     Else         intD1 = 2: intD2 = 1 '2番目の次元を横表示にする変数設定     End If     For intN2 = LBound(strArray2D, intD2) To UBound(strArray2D, intD2)         If intN2> LBound(strArray2D, intD2) Then
            strTemp = strTemp & vbCrLf '改行の追加
        End If
        If c_intIy >= 1 And intN2 >= c_intIy + LBound(strArray2D, intD2) Then
            strTemp = strTemp & "他" & UBound(strArray2D, intD2) _
                - (c_intIy - 1) & "行" '行数上限超過の処理
            Exit For
        End If
        For intN1 = LBound(strArray2D, intD1) To UBound(strArray2D, intD1)
            If intN1 > LBound(strArray2D, intD1) Then
                strTemp = strTemp & strSeparate '区切り文字の追加
            End If
            If c_intIx >= 1 _
                    And intN1 >= c_intIx + LBound(strArray2D, intD1) Then
                If intN2 = LBound(strArray2D, intD2) Then
                    strTemp = strTemp & "他" & UBound(strArray2D, intD1) _
                        - (c_intIx - 1) & "列" '列数上限超過の処理
                End If
                Exit For
            Else
                If boolVertical = True Then
                    strTemp = strTemp & "配列(" & intN1 & ", " & intN2 _
                        & ") = " & strArray2D(intN1, intN2)
                Else
                    strTemp = strTemp & "配列(" & intN2 & ", " & intN1 _
                        & ") = " & strArray2D(intN2, intN1)
                End If
            End If
        Next
    Next
    ConfirmationTextForArray2D = strTemp
End Function

上記のコードを Windows 10 のアクセサリから開いたメモ帳へコピー&ペースト後、文字コードを「ANSI」に設定し、適当なファイル名に拡張子「.vbs」をつけてデスクトップ等に保存すると、すぐに動作確認できます。
保存した vbsファイルをダブルクリックすると、要素数3×16,384の配列をランダムの整数値で作成後、データの並び替えが1番目の次元の老番から基準に2、1、0と3回行われ、昇順でソートされた配列の若番から10×3の要素と、配列を3回ソートした時間(秒)がメッセージで表示されます。

これを Microsoft Excel のワークシートの配列で例えると、ワークシートの上から3行を端から端までランダムの整数値で埋め尽くした後、選択範囲を拡張した昇順の並び替えを横方向に3行目、2行目、1行目と3回実行している状態です。

このソートは安定ソートなので、1列目の要素が重複していた場合、2列目はかならず昇順で表示されます。

解説

4~10行目は要素数3×16,384の配列を0~49,151の範囲のランダムの整数値で作成しています。

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

12~14行目は20行目のアスタリスク(*)以下に記載しているプロシージャを使って配列varArray を1番目の次元の老番から順番に 2、1、0 を基準として昇順でソートしています。
このプロシージャはソートする範囲を指定できますが、今回は全てソートするので、並び替え範囲下限を0、上限を配列の添字の上限にしています。並び替え範囲は2番目の次元になるので、引数intDimention を 2 に設定しています

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

20~129行目は2次元配列のデータを昇順に並び替えるプロシージャです。このプロシージャの主な機能は引数不正の検知、並べ替える要素とソートする前の添字の2次元配列の作成、ファンクションによる並び替え、最後にソートする前の添字を参照した並び替え後の配列作成です。
プロシージャの名前は「MergeSort2D」となっていますが、マージソートのアルゴリズムを一切含んでいません。

36~70行目は引数の不正の検出と並べ替える要素と、ソートする前の添字の2次元配列を作成しています。
引数の不正を検出すると「Error 13」の記述によりメッセージボックスでエラーが表示され、プログラムが中断します。
ソートする前の添字の配列は、2次元配列でソートしない方向の要素数が3以上のときに、入れ替え回数を減らすのに必要です。

72行目は130行目のアスタリスク(*)以下に記載しているファンクションで、ソートされた要素と、ソートする前の添字で構成された2次元配列の変数を代入しています。
このファンクションの名前を「MergeSortedArray2D」から「InsertionSortedArray2D」に記述を替えると純粋な挿入ソートになりますが、このサンプルコードで作成しているような1万を超えるデータで挿入ソートを実行すると、処理に時間がかかりすぎるのでお勧めできません。

74~96行目はソートされた2次元配列の要素にある、ソートする前の添字を参照して、ソートされた位置へ配列の要素を代入しています。

97~107行目は配列varArray が0から始まる配列でソート範囲が配列全体だった場合、配列varArray にソートされた配列を一括で代入してプロシージャを終了します。
ただし、引数の変数が配列として宣言されていた場合は、配列の変数を一括で代入するとエラーが発生するので、110行目以降の処理に移行します。

110~128行目は配列varArray にソートされた配列を1つずつ代入しています。最後まで代入すると指定された範囲をソートした配列が完成します。

130~192行目は2次元配列のデータを「マージソート」するファンクションです。

147行目は153行目の挿入ソートを停止した時に実行されますが、挿入ソートを併用しているときは実行されません。

153行目は挿入ソートを実行する条件です。サンプルコードでは配列の数が20以下で挿入ソートが実行されます。この閾値の条件を「lngTgtRange < 0」にすると全てマージソートのみで処理されます。
しかし、このプログラムは閾値以下で挿入ソートに切り替えることを前提とした設計になっているため、配列の数によっては最後の分割で端数が発生しやすくなるので処理の効率が悪くなります。
よって、挿入ソートを停止した場合、純粋なマージソートよりも処理速度が若干遅くなります。

158~161行目は引数の配列を左右に分割して、自身のファンクション(再帰関数)を使ってソートしています。

162行目は並び替え範囲に縮小した一時保管の配列を作成しています。配列の範囲を縮小するとソートの時間を短縮できます

163~189行目は左右の配列を若番から順に値を比較して、一時保管の配列に並べています。

190行目は戻り値に一時保管配列を代入しています。

193~229行目は2次元配列のデータを「挿入ソート」するファンクションです。(2021/04/15 ソートの時間を短縮する為、一部改修)

208~213行目は並び替え範囲の値だけを抽出して一時保管の配列を作成しています。配列の範囲を縮小するとソートの時間を短縮できます

214~227行目は挿入ソートで一時保管の配列を並び替えています。

228行目は戻り値に一時保管配列を代入しています。

230行目のアスタリスク(*)以下に記載しているファンクションは【VBScript】プロシージャとファンクション(関数)の使い方で紹介したものを2次元配列用にアレンジしたものです。
引数の説明にも記載してありますが、2番目の引数を True に変更すると列間がカンマ区切りになり、3番目の引数を False に変更すると縦横が逆転します。

サンプルコードで使用しているプロシージャとファンクションは Excel等の VBAでも動作します。

2次元配列を1番目の次元の範囲で昇順に並び替える(安定ソート)

サンプルコード

2次元配列を1番目の次元の範囲(Microsoft Excel のワークシートの配列では縦方向)で昇順に並び替える場合も同じプロシージャを使います。

並び替えテスト用の配列のサイズとプロシージャの引数、メッセージボックスで使用しているファンクションの引数の設定だけ変わります。プロシージャの手前までのプログラムは次のとおりです。

Option Explicit
Dim varArray, sngTime, lngN1, lngN2

ReDim varArray(65535, 2)
For lngN1 = LBound(varArray, 1) To UBound(varArray, 1)
    For lngN2 = LBound(varArray, 2) To UBound(varArray, 2)
        varArray(lngN1, lngN2) = Int(Rnd * ((UBound(varArray, 1) + 1) _
            * (UBound(varArray, 2) + 1) + 1))
    Next
Next
sngTime = Timer
Call MergeSort2D(varArray, 0, 65535, 1, 2)
Call MergeSort2D(varArray, 0, 65535, 1, 1)
Call MergeSort2D(varArray, 0, 65535, 1, 0)
MsgBox ConfirmationTextForArray2D(varArray, False, False), , _
    "並び替え処理の時間(秒):" & Round(Timer - sngTime, 3)
WScript.Quit

上記のコードを利用するには、まず、「2次元配列を2番目の次元の範囲で昇順に並び替える(安定ソート)」で紹介したサンプルコードをWindows 10 のアクセサリから開いたメモ帳へコピー&ペースト後、最初のアスタリスクから上の部分を、上記のコードのコピー&ペーストで置き換えます。
文字コードを「ANSI」に設定し、適当なファイル名に拡張子「.vbs」をつけてデスクトップ等に保存すると、すぐに動作確認できます。
保存した vbsファイルをダブルクリックすると、要素数65,536×3の配列をランダムの整数値で作成後、データの並び替えが2番目の次元の老番から基準に2、1、0と3回行われ、昇順でソートされた配列の若番から10×3の要素と、配列を3回ソートした時間(秒)がメッセージで表示されます。

これを Microsoft Excel のワークシートの配列で例えると、ワークシートの左から3列を1~65,536行目までランダムの整数値で埋め尽くした後、選択範囲を拡張した昇順の並び替えを縦方向に3列目、2列目、1列目と3回実行している状態です。

このソートは安定ソートなので、1列目の要素が重複していた場合、2列目は必ず昇順で表示されます。

解説

4~10行目は要素数65,536×3の配列を0~196,607の範囲のランダムの整数値で作成しています。
今回は1番目の次元のソートなので、1番目の次元の要素の数を増量しています。

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

12~14行目は最初のサンプルコードで紹介したプロシージャを使って配列varArray を2番目の次元の老番から順番に2、1、0を基準として昇順でソートしています。引数は並び替え範囲上限の添字 lngUpper を 65,535、並び替えの基準となる添字 intDimention を 1 に変更しています。

15~16行目は最初のサンプルコードで紹介した、2次元配列のデータをメッセージ表示用の文字列で返すファンクション(関数)を使ってソート後の配列を表示すると同時に、Timer関数を使ってソート時間を表示しています。表示する配列は縦長になるので、引数boolVertical を False に変更しています。

まとめ

  • 2次元配列は不安定ソートで重複データを並び替えた時に、別の項目の順番が崩れる可能性がある
  • 2次元配列の重複データを含む並び替えは安定ソート推奨
  • 2次元配列は並び替える要素以外の全ての要素を並び替える前の添字(ソート以前のINDEX)に置き換えると、ソートしない方向の要素数が3以上のときに入れ替え回数が減る
  • 配列のデータが多いときはマージソート、配列の分割でデータが少なくなったときに挿入ソートへ切り替えると、短時間で並び替える安定ソートになる
  • 1万を超えるデータは挿入ソートを実行すると、処理に時間がかかりすぎる
  • 引数の変数が配列として宣言されていた場合、配列の変数を一括で代入するとエラーが発生する
  • ソートアルゴリズムは配列の範囲を縮小するとソートの時間を短縮できる

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

コメント

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