ヒープソートのVBA実装：1次元・2次元配列を一度に扱う

ヒープソートの基本

ヒープソートは、配列を「ヒープ」という木構造に見立てて並べ替える方法です。ヒープは「親の値が子より大きい（または小さい）」という条件を保つ構造で、最大ヒープ（親が最大）と最小ヒープ（親が最小）があります。配列で木を表すと、親と子の位置が規則で決まるため、追加のポインタがいりません。

まず配列をヒープに作り直します（ヒープ化）。次に、先頭要素（最大または最小）を末尾と入れ替え、残りを再びヒープ化します。これを要素数ぶん繰り返すと、配列が整列します。安定ソートではありません。同じキーの場合、元の順は保たれないことがあります。

用語まとめ：親ノード（parent）、子ノード（left/right child）、ヒープ化（sift-down）。計算量は平均・最悪ともに O(n log n) です。必要メモリは固定で、原地（インプレース）で動きます。

ミニQA：ヒープとは何ですか？（配列で木構造を表す理由）

ヒープは、完全二分木の形をした優先度付きの構造です。配列なら、要素 i の左子は 2*i、右子は 2*i+1（1基準の場合）で求められます。これにより、ノード間のリンクを持たなくても、添字の計算だけで親子関係をたどれます。

1次元配列：VBAコード（昇順/降順対応）

ここでは、1次元のVariant配列をヒープソートするVBAコードを示します。昇順・降順は引数で切り替えます。配列は 0 または 1 開始のどちらでも使えます。

“`vba

Option Explicit

Public Sub HeapSort1D(ByRef arr As Variant, Optional ByVal ascending As Boolean = True)

Dim lo As Long, hi As Long

Dim n As Long

lo = LBound(arr): hi = UBound(arr)

n = hi – lo + 1

If n <= 1 Then Exit Sub

Dim i As Long

‘ ヒープの構築

For i = (n \ 2) – 1 To 0 Step -1

Heapify1D arr, lo, n, i, ascending

Next i

‘ 要素を末尾へ送りながら再ヒープ化

For i = n – 1 To 1 Step -1

Swap arr, lo, 0, i

Heapify1D arr, lo, i, 0, ascending

Next i

End Sub

Private Sub Heapify1D(ByRef arr As Variant, ByVal lo As Long, ByVal n As Long, ByVal idx As Long, ByVal ascending As Boolean)

Dim largest As Long, l As Long, r As Long, t As Long

largest = idx

Do

l = 2 * largest + 1

r = l + 1

t = largest

If l < n Then

If Cmp(arr(lo + l), arr(lo + t), ascending) > 0 Then t = l

End If

If r < n Then

If Cmp(arr(lo + r), arr(lo + t), ascending) > 0 Then t = r

End If

If t = largest Then Exit Do

Swap arr, lo, largest, t

largest = t

Loop

End Sub

Private Function Cmp(ByVal a As Variant, ByVal b As Variant, ByVal ascending As Boolean) As Long

‘ 文字列と数値が混在する場合は、文字列比較に寄せます

If IsNumeric(a) And IsNumeric(b) Then

If a = b Then Cmp = 0 Else If a > b Then Cmp = IIf(ascending, 1, -1) Else Cmp = IIf(ascending, -1, 1)

Else

Dim s1 As String, s2 As String

s1 = CStr(a): s2 = CStr(b)

Dim c As Long: c = StrComp(s1, s2, vbTextCompare)

If ascending Then Cmp = -c Else Cmp = c

End If

End Function

Private Sub Swap(ByRef arr As Variant, ByVal lo As Long, ByVal i As Long, ByVal j As Long)

Dim tmp As Variant

tmp = arr(lo + i)

arr(lo + i) = arr(lo + j)

arr(lo + j) = tmp

End Sub

“`

ミニQA：安定ソートですか？並び順が同じ要素はどうなりますか？

ヒープソートは安定ではありません。同じ値が並ぶと、元の並びは保持されないことがあります。安定性が必要なら、キーを組みにして「元の位置」を第2キーにする方法があります。

1次元配列：実行テストと使い方

このセクションでは、1次元配列のソートを試すテストコードを示します。配列の開始インデックスが 0 と 1 の両方で動く点を確認します。速度はPCやデータにより変わります。

“`vba

Sub TestHeapSort1D()

Dim a As Variant

a = Array(5, 3, 9, 1, 5, 7)

HeapSort1D a, True ‘ 昇順

Dim i As Long

For i = LBound(a) To UBound(a)

Debug.Print a(i)

Next i

‘ 1基準の配列例

Dim b(1 To 6) As Variant

b(1) = “b”: b(2) = “A”: b(3) = “c”: b(4) = “a”: b(5) = “B”: b(6) = “C”

HeapSort1D b, True

For i = LBound(b) To UBound(b)

Debug.Print b(i)

Next i

End Sub

“`

ミニQA：小さい配列でもヒープソートを使うべきですか？

要素数が少ないときは、挿入ソートの方が単純で速いことがあります。配列サイズが大きくなるほど、ヒープソートの強み（最悪 O(n log n)）が活きます。

1次元/2次元配列対応版：VBAコード

次は、1次元と2次元（行単位）に対応する汎用版です。2次元配列は、指定した「キー列」の値を比較して並べ替えます。ワークシートの範囲を配列に読み込んでから使うことを想定しています。

“`vba

Option Explicit

Public Sub HeapSort(ByRef data As Variant, Optional ByVal ascending As Boolean = True, _

Optional ByVal keyCol As Long = 1)

‘ data が 1次元配列なら各要素を比較、2次元配列なら keyCol 列で比較

Dim dims As Long

On Error Resume Next

dims = 1 + (UBound(data, 2) >= LBound(data, 2))

On Error GoTo 0

If dims = 1 Then

HeapSort1D data, ascending

ElseIf dims = 2 Then

HeapSort2D data, ascending, keyCol

Else

Exit Sub

End If

End Sub

Private Sub HeapSort2D(ByRef arr As Variant, ByVal ascending As Boolean, ByVal keyCol As Long)

Dim rLo As Long, rHi As Long, cLo As Long, cHi As Long

rLo = LBound(arr, 1): rHi = UBound(arr, 1)

cLo = LBound(arr, 2): cHi = UBound(arr, 2)

If keyCol < cLo Or keyCol > cHi Then Exit Sub

Dim n As Long: n = rHi – rLo + 1

If n <= 1 Then Exit Sub

Dim i As Long

For i = (n \ 2) – 1 To 0 Step -1

Heapify2D arr, rLo, n, i, keyCol, ascending

Next i

For i = n – 1 To 1 Step -1

SwapRow arr, rLo, cLo, cHi, 0, i

Heapify2D arr, rLo, i, 0, keyCol, ascending

Next i

End Sub

Private Sub Heapify2D(ByRef arr As Variant, ByVal rLo As Long, ByVal n As Long, ByVal idx As Long, _

ByVal keyCol As Long, ByVal ascending As Boolean)

Dim largest As Long, l As Long, r As Long, t As Long

largest = idx

Do

l = 2 * largest + 1

r = l + 1

t = largest

If l < n Then

If Cmp(arr(rLo + l, keyCol), arr(rLo + t, keyCol), ascending) > 0 Then t = l

End If

If r < n Then

If Cmp(arr(rLo + r, keyCol), arr(rLo + t, keyCol), ascending) > 0 Then t = r

End If

If t = largest Then Exit Do

SwapRow arr, rLo, LBound(arr, 2), UBound(arr, 2), largest, t

largest = t

Loop

End Sub

Private Sub SwapRow(ByRef arr As Variant, ByVal rLo As Long, ByVal cLo As Long, ByVal cHi As Long, _

ByVal i As Long, ByVal j As Long)

Dim c As Long, tmp As Variant

For c = cLo To cHi

tmp = arr(rLo + i, c)

arr(rLo + i, c) = arr(rLo + j, c)

arr(rLo + j, c) = tmp

Next c

End Sub

“`

ミニQA：2次元の比較対象は「列番号・キー列」で合っていますか？

はい。2次元配列は、keyCol で指定した列の値を見て比較します。列の基準は配列の下限に合わせます（通常は 1 から）。

1次元/2次元配列対応版：実行テスト

ワークシートのデータを配列に取り込み、2次元配列をキー列でソートする例です。列の選び方や書き戻しの流れも確認します。

“`vba

Sub TestHeapSort2D()

Dim rng As Range

Dim arr As Variant

Set rng = ThisWorkbook.Worksheets(1).Range(“A1:D10”)

arr = rng.Value ‘ 1基準の2次元配列

HeapSort arr, True, 2 ‘ 2列目を昇順で

rng.Value = arr ‘ 並べ替え結果を書き戻す

End Sub

“`

ミニQA：数値と文字列が混在するときの注意点は？

比較は、両方が数値なら数値比較、それ以外は文字列比較（大文字小文字を区別しない）に寄せています。桁のそろっていない文字列の数値は、文字列比較だと意図しない順になることがあります。

よくあるエラーと対処／他アルゴリズムとの比較の要点

境界のずれ（添字の開始 0/1）、キー列の範囲外、Variantの型の想定外変換などが典型です。Option Explicit を使い、引数チェックを入れると不具合を見つけやすくなります。速度の感じ方はデータと環境で変わるため、固定的な優劣の断定はしません。

比較の要点は次の通りです。

ミニQA：どのソートを選べばよいですか？判断の目安は？

安定性が必要か、最悪時間を抑えたいか、メモリを増やせるか、データの大きさはどうか。この4点で考えると選びやすくなります。