更新日:、 作成日:

VBA 配列の並び替え

はじめに

Excel VBA マクロの配列の並び替え、ソートする方法を紹介します。

挿入ソート (Insertion Sort) と、クイックソート (QuickSort) の 2 種類の方法を紹介します。

数値の配列や構造体の配列を昇順に並び替えられます。

降順にするには「配列の並びを反転させる」をご覧ください。

安定ソートとは

並び替えのアルゴリズムには安定ソートと不安定ソートの 2 種類があります。

安定ソートとは 1, 2, 2, 3 のように同じ値の要素があるときに、並び替え前の順序と後の順序が変わらないことです。前の 2 を 2a、後の 2 を 2b と区別すると、何回並び替えても 2a, 2b の順番になります。

不安定ソートは並び替えるたびに 2a, 2b2b, 2a になります。数値の配列では問題になりませんが、構造体の配列では結果が異なることになります。

  • 挿入ソート (Insertion Sort):安定ソート
  • クイックソート (QuickSort):不安定ソート

挿入ソート (Insertion Sort)

安定ソートです。平均速度は O(n2) と遅めです。コードが単純な InsertionSort 関数を作成します。

Sub 実行()
    Dim data As Variant
    data = Array(7, 2, 6, 3, 9, 1, 8, 0, 5, 4)

    ' 並び替え
    Call InsertionSort(data, LBound(data), UBound(data))
    ' 0 1 2 3 4 5 6 7 8 9
End Sub

Sub InsertionSort(ByRef data As Variant, ByVal low As Long, ByVal high As Long)

    Dim i As Variant
    Dim k As Variant
    Dim temp As Variant

    For i = low + 1 To high
        temp = data(i)
        If data(i - 1) > temp Then
            k = i

            Do While k > low
                If data(k - 1) <= temp Then
                    Exit Do
                End If

                data(k) = data(k - 1)
                k = k - 1
            Loop

            data(k) = temp
        End If
    Next

End Sub

どの型にも対応するために Variant 型を使用していますが、Integer や Long など型を指定した方が速度が上がります。

引数に渡したインデックスの範囲だけを並び替えられます。

構造体の並び替え

構造体を並び替える InsertionSortType 関数を作成します。

Sub 実行()
    Dim data(99) As Point

    ' 構造体の配列にランダムなデータを入れる
    Const low As Long = 1
    Const high As Long = 100
    Randomize
    Dim i As Long
    For i = LBound(data) To UBound(data)
        data(i).X = Int((high - low + 1) * Rnd + low)
    Next

    ' 並び替え
    Call InsertionSortType(data, LBound(data), UBound(data))
End Sub

Sub InsertionSortType(ByRef data() As Point, ByVal low As Long, ByVal high As Long)

    Dim i As Variant
    Dim k As Variant
    Dim temp As Point

    For i = low + 1 To high
        temp = data(i)
        If ComparePoint(data(i - 1), temp) > 0 Then
            k = i

            Do While k > low
                If ComparePoint(data(k - 1), temp) <= 0 Then
                    Exit Do
                End If

                data(k) = data(k - 1)
                k = k - 1
            Loop

            data(k) = temp
        End If
    Next

End Sub

' 構造体の比較用関数
Function ComparePoint(ByRef data1 As Point, ByRef data2 As Point) As Long
    ComparePoint = data1.X - data2.X
End Function
' 標準モジュールに定義
Public Type Point
    X As Long
    Y As Long
End Type

Point という構造体を使っていますが、その名前を実際に使う名前に置き換えて使います。

構造体を比較するために ComparePoint 関数を作成しています。比較する値が同じときに別の値を比較すれば、第 1 キー、第 2 キーのようにできます。

Function ComparePoint(ByRef data1 As Point, ByRef data2 As Point) As Long
    ' 第 1 キー
    If data1.X <> data2.X Then
        ComparePoint = data1.X - data2.X
        Exit Function
    End If

    ' 第 2 キー
    ComparePoint = data1.Y - data2.Y
End Function

クイックソート (QuickSort)

不安定ソートです。平均速度は O(n log n) です。一般的に最速と言われている QuickSort 関数を作成します。

QuickSort 関数の中から QuickSort 関数を呼び出す、いわゆる再帰呼び出しをしています。このためデータ量が膨大だと、エラー「スタック領域が不足しています。」が発生する可能性があります。
Sub 実行()
    Dim data As Variant
    data = Array(7, 2, 6, 3, 9, 1, 8, 0, 5, 4)

    ' 並び替え
    Call QuickSort(data, LBound(data), UBound(data))
    ' 0 1 2 3 4 5 6 7 8 9
End Sub

Sub QuickSort(ByRef data As Variant, ByVal low As Long, ByVal high As Long)

    Dim l As Long
    Dim r As Long
    l = low
    r = high

    Dim pivot As Variant
    pivot = data((low + high) \ 2)

    Dim temp As Variant

    Do While (l <= r)
        Do While (data(l) < pivot And l < high)
            l = l + 1
        Loop
        Do While (pivot < data(r) And r > low)
            r = r - 1
        Loop

        If (l <= r) Then
            temp = data(l)
            data(l) = data(r)
            data(r) = temp
            l = l + 1
            r = r - 1
        End If
    Loop

    If (low < r) Then
        Call QuickSort(data, low, r)
    End If
    If (l < high) Then
        Call QuickSort(data, l, high)
    End If

End Sub

どの型にも対応するために Variant 型を使用していますが、Integer や Long など型を指定した方が速度が上がります。

引数に渡したインデックスの範囲だけを並び替えられます。

構造体の並び替え

構造体を並び替える QuickSortType 関数を作成します。

Sub 実行()
    Dim data(99) As Point

    ' 構造体の配列にランダムなデータを入れる
    Const low As Long = 1
    Const high As Long = 100
    Randomize
    Dim i As Long
    For i = LBound(data) To UBound(data)
        data(i).X = Int((high - low + 1) * Rnd + low)
    Next

    ' 並び替え
    Call QuickSortType(data, LBound(data), UBound(data))
End Sub

Sub QuickSortType(ByRef data() As Point, ByVal low As Long, ByVal high As Long)

    Dim l As Long
    Dim r As Long
    l = low
    r = high

    Dim pivot As Point
    pivot = data((low + high) \ 2)

    Dim temp As Point

    Do While (l <= r)  
        Do While ((ComparePoint(data(l), pivot) < 0) And l < high)
            l = l + 1
        Loop  
        Do While ((ComparePoint(pivot, data(r)) < 0) And r > low)
            r = r - 1
        Loop

        If (l <= r) Then
            temp = data(l)
            data(l) = data(r)
            data(r) = temp
            l = l + 1
            r = r - 1
        End If
    Loop

    If (low < r) Then
        Call QuickSortType(data, low, r)
    End If
    If (l < high) Then
        Call QuickSortType(data, l, high)
    End If

End Sub

' 構造体の比較用関数
Function ComparePoint(ByRef data1 As Point, ByRef data2 As Point) As Long
    ComparePoint = data1.X - data2.X
End Function
' 標準モジュールに定義
Public Type Point
    X As Long
    Y As Long
End Type

Point という構造体を使っていますが、その名前を実際に使う名前に置換して使います。

構造体を比較するために ComparePoint 関数を作成しています。比較する値が同じときに別の値を比較すれば、第 1 キー、第 2 キーのようにできます。

Function ComparePoint(ByRef data1 As Point, ByRef data2 As Point) As Long
    ' 第 1 キー
    If data1.X <> data2.X Then
        ComparePoint = data1.X - data2.X
        Exit Function
    End If

    ' 第 2 キー
    ComparePoint = data1.Y - data2.Y
End Function