サイトについて      連絡先   検索

VBA 配列の並び替え

はじめに

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

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

数値の配列や構造体の配列の順序を昇順に並び替える方法を紹介します。

安定ソートとは

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

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

不安定ソートは並び替えるたびに2a, 2b2b, 2aになります。

挿入ソート (Insertion Sort)

安定ソートです。平均速度は O(n2) と遅めですが、コードが単純です。

配列の並び替え


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

使い方


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

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

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

構造体の並び替え


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 Variant
    ComparePoint = data1.X - data2.X
End Function

' 標準モジュールに定義
Public Type Point
    X As Long
    Y As Long
End Type

使い方


Dim data(99) As Point

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

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

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

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


Function ComparePoint(ByRef data1 As Point, ByRef data2 As Point) As Variant
    ' 第 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 関数を呼び出す、いわゆる再帰呼び出しをしています。このためデータ量が膨大だと、エラー「スタック領域が不足しています。」が発生する可能性があります。

配列の並び替え


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

使い方


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

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

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

構造体の並び替え


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 Variant
    pivot = data((low + high) \ 2)

    Dim temp As Variant
    
    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 QuickSort(data, low, r)
    End If
    If (l < high) Then
        Call QuickSort(data, l, high)
    End If

End Sub

' 構造体の比較用関数
Function ComparePoint(ByRef data1 As Point, ByRef data2 As Point) As Variant
    ComparePoint = data1.X - data2.X
End Function

' 標準モジュールに定義
Public Type Point
    X As Long
    Y As Long
End Type

使い方


Dim data(99) As Point

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

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

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

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


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

関連ページ