【VBA】バブルソートとクイックソートの速度差を実測比較

前回の記事では、シート上でのセル操作が遅い理由を解説しました。同じ並び替え処理でも、シートに直接書き込みながら処理するのと、配列上で処理してから一括で書き戻すのとでは、処理時間に大きな差が出ます。

前回は「なぜシート操作は遅いのか」という原理の部分を解説しました。今回はその実践編として、ソートのアルゴリズム自体の違い（バブルソート vs クイックソート）と、処理場所の違い（シート上 vs 配列上）を掛け合わせた4パターンを実装し、実測で比較します。

バブルソートとクイックソートの違い
検証条件
検証1：2,000行での4パターン比較
検証2：6万行でのクイックソート比較
なぜこれだけ差が出るのか
配列を使う場合の基本
まとめ

バブルソートとクイックソートの違い

バブルソートは、隣り合う要素を先頭から順に比較し、大小が逆であれば入れ替える処理を、データの末尾まで繰り返すアルゴリズムです。1回のパスでは末尾に近い部分から順に正しい位置が確定していくため、n件のデータに対して最大でn×n回程度の比較が発生します。データ件数が増えると、処理量は件数の2乗に比例して増えていきます。

クイックソートは、基準値（ピボット）を1つ選び、それより小さい値のグループと大きい値のグループに分割する処理を再帰的に繰り返すアルゴリズムです。1回の分割でデータがおおよそ半分になっていくため、n件のデータに対する比較回数はnにデータ件数の対数（log n）を掛けた程度で済みます。件数が増えても、バブルソートほど急激には処理量が増えません。

この計算量の違いに加えて、処理をシート上のセルに対して直接行うか、配列上で完結させてから書き戻すかという違いも、実際の処理時間に大きく影響します。今回はこの2つの軸（アルゴリズムの種類×処理場所）を組み合わせた4パターンで検証しました。なお、シート上の並び替え自体はExcelのRange.Sortメソッドでも実行できます。今回はセルの読み書きコストそのものを検証する目的で、あえて自前の比較・入れ替え処理として実装しています。

検証条件

同じ生成処理で作ったランダムな数値データを、4パターンすべてに同一の内容で使用
比較の軸を明確にするため、まず2,000行のデータで4パターンをまとめて計測（検証1）
バブルソートは比較回数が件数の2乗に比例して増えるため、6万行で計測すると現実的な時間に収まらない。そのため6万行での計測はクイックソートの2パターンのみに絞った（検証2）
Timer関数で処理時間を計測し、ソート後のデータが正しく昇順に並んでいるかも合わせて確認
各パターンとも複数回実行し、大きなブレがないことを確認済み

検証1：2,000行での4パターン比較

パターン	処理時間（3回平均）	判定
バブルソート×配列	0.058秒	昇順OK
バブルソート×シート	115.062秒	昇順OK
クイックソート×配列	0.003秒（計測誤差の範囲内）	昇順OK
クイックソート×シート	0.771秒	昇順OK

同じバブルソートでも、配列上で処理してからシートへ書き戻す方式と、シートのセルを直接読み書きする方式とで、2,000行のデータで約2,000倍の差になりました。

また、同じ「シート上で直接処理する」条件でアルゴリズムだけを比較すると、バブルソート（115.062秒）とクイックソート（0.771秒）の差は約149倍です。処理する場所（シートか配列か）と、アルゴリズムの選び方（バブルかクイックか）は、それぞれ独立して処理時間に効いてくることが分かります。

VBAでバブルソート・クイックソートの配列版とシート版の処理時間を比較した実行結果 — 4パターンの実行結果（イミディエイトウィンドウ）

検証2：6万行でのクイックソート比較

クイックソートの2パターンについて、目標としていた6万行でも計測しました。

パターン	処理時間（3回平均）	判定
クイックソート×配列	0.028秒	昇順OK
クイックソート×シート	31.044秒	昇順OK

配列上で完結させれば6万行でも0.028秒で終わります。同じ6万行をシート上で直接処理すると31.044秒かかり、こちらも約1,100倍の差が出ました。

なぜこれだけ差が出るのか

バブルソートは比較回数がデータ件数の2乗に比例して増えるアルゴリズムです。今回の実測（2,000行で115.062秒）をもとに、件数が30倍（6万行）になった場合を計算すると、比較回数は30の2乗、つまり900倍に増える計算になります。単純計算では、

115.062秒 × 900 ≒ 103,556秒 ≒ 約28.8時間

となり、「半日どころか丸1日以上かかってもおかしくない」という規模になります。これはあくまで計算上の見積もりで、実際に6万行で計測したものではありませんが、前回のエピソードで触れた「6万行のシートソートで半日かかった」という体験とも近い数字です。バブルソート特有の2乗の計算量と、セル1つ1つへの読み書きコストが重なることで、件数が増えるほど雪だるま式に処理時間が膨らんでいったと考えられます。

一方、クイックソートは6万行でもシート上の処理で31.044秒で済んでいます。同じ「シートに直接読み書きする」という条件でも、アルゴリズムの計算量が違うだけでここまで差が出ることが、今回の検証で確認できました。

配列を使う場合の基本

今回の配列版のコードでは、Dimで宣言した配列をReDimで必要なサイズに広げてから使っています。配列の宣言やReDimの基本的な使い方は、こちらの記事でも解説していますので、あわせて参考にしてください。

実際にシート上でクイックソートを動かす様子を、単体で動く最小コードで確認できます。以下は再現用の最小コードです（記事の検証コードとはSub名が異なります）。

Sub DemoSortSample()
    Dim data As Variant
    Dim i As Long
    Dim wb As Workbook
    Dim ws As Worksheet
 
    ' サンプルデータ（10件）
    data = Array(58, 3, 91, 27, 64, 10, 45, 82, 19, 36)
 
    Set wb = Workbooks.Add
    Set ws = wb.Sheets(1)
    For i = 0 To UBound(data)
        ws.Cells(i + 1, 1).Value = data(i)
    Next i
 
    Debug.Print "ソート前："
    For i = 1 To 10
        Debug.Print ws.Cells(i, 1).Value
    Next i
 
    Call QuickSortSheetDemo(ws, 1, 10)
 
    Debug.Print "ソート後："
    For i = 1 To 10
        Debug.Print ws.Cells(i, 1).Value
    Next i
 
    MsgBox "並び替え完了。イミディエイトウィンドウを確認してください。", vbInformation
 
    wb.Close SaveChanges:=False
End Sub
 
Sub QuickSortSheetDemo(ByVal ws As Worksheet, ByVal lo As Long, ByVal hi As Long)
    Dim i As Long, j As Long, pivot As Long, tmp As Long
    If lo >= hi Then Exit Sub
    i = lo
    j = hi
    pivot = ws.Cells((lo + hi) \ 2, 1).Value
    Do While i <= j
        Do While ws.Cells(i, 1).Value < pivot
            i = i + 1
        Loop
        Do While ws.Cells(j, 1).Value > pivot
            j = j - 1
        Loop
        If i <= j Then
            tmp = ws.Cells(i, 1).Value
            ws.Cells(i, 1).Value = ws.Cells(j, 1).Value
            ws.Cells(j, 1).Value = tmp
            i = i + 1
            j = j - 1
        End If
    Loop
    If lo < j Then QuickSortSheetDemo ws, lo, j
    If i < hi Then QuickSortSheetDemo ws, i, hi
End Sub