[VBA]クイックソート(Quick sort)の実装

2020年5月4日

概要

VBAでクイックソートを実装しました。O記法での平均計算量はO(n log n)です。データの並び順に規則性が無ければ、まず期待通りの性能を発揮してくれるソートアルゴリズムです。アルゴリズムの説明はWikipediaより引用させて頂きました。

1. 適当な数(ピボット(英語版)という)を選択する(この場合はデータの総数の中央値が望ましい)
2. ピボットより小さい数を前方、大きい数を後方に移動させる (分割)
3. 二分割された各々のデータを、それぞれソートする。

実際にこれを実現するためのアルゴリズムは色々考えられるが、一例を挙げると以下のようなものがある。
1. ピボットとして一つ選びそれをPとする。
2. 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
3. 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
4. iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。
5. 2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。

Wikipedia

コード

'* @fn Public Sub QuickSort(ByRef Values As Variant, Optional ByVal StartIndex As Long = -1, Optional ByVal EndIndex As Long = -1)
'* @brief 一次元配列をクイックソートします。
'* @param[in,out] Values    値型の一次元配列を指定します。内部処理形式が値型のVariant型配列も指定可能です。
'* @param[in] StartIndex    第1引数Valuesの中から、ソートする範囲の開始位置をインデックスで指定します。引数を省略するか、-1以下を指定すると、配列の先頭が開始位置となります。
'* @param[in] EndIndex      第1引数Valuesの中から、ソートする範囲の終了位置をインデックスで指定します。引数を省略するか、-1以下を指定すると、配列の末尾が終了位置となります。
'* @details クイックソートは不安定ソートで、平均計算量は、O(n log n)です。
''*
Public Sub QuickSort(ByRef Values As Variant, Optional ByVal StartIndex As Long = -1, Optional ByVal EndIndex As Long = -1)
    If (StartIndex <= -1) Then StartIndex = LBound(Values)
    If (EndIndex <= -1) Then EndIndex = UBound(Values)
    Call pvtQuickSort(Values, StartIndex, EndIndex)
End Sub
'* @fn Private Sub pvtQuickSort(ByRef Values As Variant, ByVal StartIndex As Long, ByVal EndIndex As Long)
'* @brief クイックソートの実体となる再帰関数です。この関数は上記のQuickSort内でのみ呼び出されることを想定しています。
'* @param[in,out] Values    値型の一次元配列を指定します。内部処理形式が値型のVariant型配列も指定可能です。
'* @param[in] StartIndex    第1引数Valuesの中から、ソートする範囲の開始位置をインデックスで指定します。
'* @param[in] EndIndex      第1引数Valuesの中から、ソートする範囲の終了位置をインデックスで指定します。
''*
Private Sub pvtQuickSort(ByRef Values As Variant, ByVal StartIndex As Long, ByVal EndIndex As Long)
    
    'ピボット、基準点、真ん中にしたのでmiddle
    Dim MiddleIndex As Long: MiddleIndex = (EndIndex + StartIndex) \ 2 '演算子\は割り算の商部分
    Dim Pivot As Variant: Pivot = Values(MiddleIndex) '基準値
    Dim Forword As Long: Forword = StartIndex   '配列の先頭から末尾へ巡回するインデックス
    Dim Backword As Long: Backword = EndIndex   '配列の末尾から先頭へ巡回するインデックス
    Dim tmp As Variant
    Do
        '基準値未満の値のインデックス取得
        Do While (Values(Forword) < Pivot)
            Forword = Forword + 1
        Loop
        
        '基準値を超える値のインデックスを取得
        Do While (Pivot < Values(Backword))
            Backword = Backword - 1
        Loop
        
        '左右の位置を比較
        If Backword <= Forword Then
            Exit Do '左右が同じか逆ならループ終了
        
        Else
            '左右が順なら値を入れ替え
            tmp = Values(Forword)
            Values(Forword) = Values(Backword)
            Values(Backword) = tmp
            Forword = Forword + 1 '次の探索開始場所を1つ右へ
            Backword = Backword - 1 '次の探索開始場所を1つ左へ
        End If
    Loop
    
    '配列を分割して再帰処理
    If StartIndex < Forword - 1 Then Call pvtQuickSort(Values, StartIndex, Forword - 1) '分割の左側
    If Backword + 1 < EndIndex Then Call pvtQuickSort(Values, Forword, EndIndex) '分割の右側
End Sub

ソースコードの利用について

本ソースコードは「GPL v3.0(GNU General Public License Version 3.0)」ライセンスで利用可能です。

本ソースコードを私的に利用される方は、本ソースコードが無料で利用できると考えて差し支え御座いません。下記の著作権表示をソースコード内に表示して頂ければ幸いです。

Copyright © 2017 黒い箱の中 All Rights Reserved.(https://kuroihako.com/)

本ホームページのソースコードを利用したソフトウェアを商用利用したり、ホームページ等で一般公開する方は、本ホームページのソフトウェアまたはソースコードに適用されているライセンスをご理解頂いてからご使用ください。同ライセンス以外での利用をご希望の方はお問い合わせフォームよりご連絡下さい。