VBでのクイックソートについて

VB6,VBA,VBS,EXCEL,DOS,BAT,WSH,WORDの小技メモ

HTML/ CSS/ CGI-Perl/ JavaScript/ JavaApplet/ AccessUp/ Internet/ EnglishLearn/ ちゃいちゃん天使/ 天使メッセージ/ 飯田ワールド/ 結城ワールド/ プロフィール/ WEB相談室/ WEBアンテナ/ 燈明日記/ Perlノート/ 漢字起源/ yahoo

はじめに

本ページは、ウインドウズ系全般のティプスメモです。

そう、はじめはVB系のティプスメモだったのですが…いつの間にか、ウインドウズ系全般のティプスメモになってしまいました。

ちなみに、ティプス(Tips)とは、マニュアルに書かれていない技法や裏わざのことですが、本ページでは、私が経験してこれはと思ったノウハウのメモになっています。

尚、以下は本サイトの最新情報(ブログ)です。

それでは、本ページが何かのお役に立てれば幸いです。ごゆっくりご覧ください。

◆ VBでのクイックソートについて

普通、ソートは、DBを使っている時は、まず、SQL上のOrder Byでソートし、つぎにVB上のロジックでソートし、そのつぎにEXCEL上のメソッドでソートします。

VB上でソートしたい時は、配列内の重複データ削除の前処理としてソートするとかで、それには、クイックソートがもっとも速いとされています。

クイックソートのアルゴリズムは、以下の感じです。

クイックソートのアルゴリズム

  1. まず、配列の中央付近のインデックスの内容値を基準値とします。
  2. 配列のインデックスの小さい方から基準値に向かって、基準値より大きい値を探します。
  3. 配列のインデックスの大きい方から基準値に向かって、基準値より小さい値を探します。
  4. 2と3の双方の値を交換します。 そして、2から3を繰り返すと5の状態になります。
  5. 基準値より小さな値が基準値より左に、大きな値が基準値より右にきます。
  6. つぎに、基準値の左の配列と右の配列に対して、1から4のを繰り返します。
  7. 各々配列の要素が1になるまで、上記を繰り返せば、結果的に全配列内がソートされるわけです。

クイックソートのアルゴリズム具体例

インデックス0〜8の配列内の値が下記の場合だとします。 

0 1 2 3 4 5 6 7 8 : インデックス
2 9 8 3 5 4 1 7 6 : インデックス内容値

まず、中央のインデックス4の内容値5を基準値5と表現します。 

2 9 8 3 5 4 1 7 6

配列のインデックスの小さい方から基準値5に向かって、基準値5より大きい値は、9です。
配列のインデックスの大きい方から基準値5に向かって、基準値5より小さい値は、1です。
ですので9と1を交換します。すると配列内は以下の状態になります。

2 1 8 3 5 4 9 7 6

引き続き、
配列のインデックスの小さい方から基準値5に向かって、基準値5より大きい値は、8です。
配列のインデックスの大きい方から基準値5に向かって、基準値5より小さい値は、4です。
ですので8と4を交換します。すると配列内は以下の状態になり、基準値5より小さい値が左に、大きい値が右にきます。

2 1 4 3 5 8 9 7 6

配列のインデックスの小さい方から基準値5に向かっていくと基準値5より大きい値は、ありません。
配列のインデックスの大きい方から基準値5に向かっていくと基準値5より小さい値は、ありません。
基準値5は確定しました。

2 1 4 3 5 8 9 7 6
    1 <---------確定サイン

つぎに、基準値5より左の部分(2 1 4 3)を同じようにソートします。
基準値を1とします。
配列のインデックスの小さい方から基準値1に向かって、基準値1より大きい値は、2です。
配列のインデックスの大きい方から基準値1に向かって、基準値1より小さい値は、ありません。
このときは、2と基準値1を交換します。

1 2 4 3 5 8 9 7 6
    1 

配列のインデックスの小さい方から基準値1に向かっていくと基準値1より大きい値は、ありません。
配列のインデックスの大きい方から基準値1に向かっていくと基準値1より小さい値は、ありません。
基準値1は確定しました。

1 2 4 3 5 8 9 7 6
1       1 

つぎに、基準値1より右の部分(2 4 3)を同じようにソートします。
基準値を4とします。
配列のインデックスの小さい方から基準値4に向かって、基準値4より大きい値は、ありません。
配列のインデックスの大きい方から基準値4に向かって、基準値4より小さい値は、3です。
このときは、基準値4と3を交換します。

1 2 3 4 5 8 9 7 6
1       1 

配列のインデックスの小さい方から基準値4に向かっていくと基準値4より大きい値は、ありません。
配列のインデックスの大きい方から基準値4に向かっていくと基準値4より小さい値は、ありません。
基準値4は確定しました。

1 2 3 4 5 8 9 7 6
1     1 1 

つぎに、基準値4より左の部分(2 3)を同じようにソートします。
基準値を2とします。
配列のインデックスの小さい方から基準値2に向かっていくと基準値2より大きい値は、ありません。
配列のインデックスの大きい方から基準値2に向かっていくと基準値2より小さい値は、ありません。
基準値2は確定しました。また、配列の要素が一つになってしまったので3も確定です。

1 2 3 4 5 8 9 7 6
1 1 1 1 1 

つぎに、先の基準値5より右の部分(8 9 7 6)を同じようにソートします。
基準値を9とします。
配列のインデックスの小さい方から基準値9に向かって、基準値9より大きい値は、ありません。
配列のインデックスの大きい方から基準値9に向かって、基準値9より小さい値は、6です。
このときは、基準値9と6を交換します。

1 2 3 4 5 8 6 7 9
1 1 1 1 1       

配列のインデックスの小さい方から基準値9に向かっていくと基準値9より大きい値は、ありません。
配列のインデックスの大きい方から基準値9に向かっていくと基準値9より小さい値は、ありません。
基準値9は確定しました。

1 2 3 4 5 8 6 7 9
1 1 1 1 1       1 

つぎに、基準値9より左の部分(8 6 7)を同じようにソートします。
基準値を6とします
配列のインデックスの小さい方から基準値6に向かって、基準値6より大きい値は、8です。
配列のインデックスの大きい方から基準値6に向かって、基準値6より小さい値は、ありません。
このときは、基準値6と8を交換します。

1 2 3 4 5 6 8 7 9
1 1 1 1 1       1

配列のインデックスの小さい方から基準値6に向かっていくと基準値6より大きい値は、ありません。
配列のインデックスの大きい方から基準値6に向かっていくと基準値6より小さい値は、ありません。
基準値6は確定しました。

1 2 3 4 5 6 8 7 9
1 1 1 1 1 1     1

つぎに、基準値6より右の部分(8 7)を同じようにソートします。
基準値を8とします。
配列のインデックスの小さい方から基準値に向かって、基準値より大きい値は、ありません。
配列のインデックスの大きい方から基準値に向かって、基準値より小さい値は、7です。
このときは、基準値8と7を交換します。

1 2 3 4 5 6 7 8 9
1 1 1 1 1 1     1

配列のインデックスの小さい方から基準値8に向かっていくと基準値8より大きい値は、ありません。
配列のインデックスの大きい方から基準値8に向かっていくと基準値8より小さい値は、ありません。
基準値8は確定しました。また、配列の要素が一つになってしまったので7も確定です。

1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1

これで、ソートが完了しましした。

クイックソートのコーディング例

上記を踏まえてコーディングをすると以下の感じになります。

Sub QuickSort(vntSortData() As Variant, lngMin As Long, lngMax As Long)
    '----------------------------------------------------------------------------------
    'クイックソート(配列データ, 配列データ最小インデックス, 配列データ最大インデックス)
    '----------------------------------------------------------------------------------
        Dim lngIdxL        As Long
        Dim lngIdxR        As Long
        Dim vntKijunChi    As Variant
        Dim vntWk          As Variant
        
        '中央付近のインデックス内容値を基準値とします。
        vntKijunChi = vntSortData((lngMin + lngMax) \ 2)
        '最小インデックスをセット。
        lngIdxL = lngMin
        '最大インデックスをセット。
        lngIdxR = lngMax
        Do
            '配列のインデックスの小さい方から基準値に向かって、インデックス内容値が基準値より大きい値かイコールな値を探します。
            For lngIdxL = lngIdxL To lngMax Step 1
                If (vntSortData(lngIdxL) >= vntKijunChi) Then  '*1、降順は『>=』を『<=』 にする。
                    Exit For
                End If
            Next
            '配列のインデックスの大きい方から基準値に向かって、インデックス内容値が基準値より小さい値かイコールな値を探します。
            For lngIdxR = lngIdxR To lngMin Step -1
                If (vntSortData(lngIdxR) <= vntKijunChi) Then  '*2、降順は『<=』を『>=』 にする。
                   Exit For
                End If
            Next
            '最小インデックスと最大インデックスが同じか大きくになったらブレイクDOループ。
            If lngIdxL >= lngIdxR Then
               'この段階で、基準値より小さな値が基準値より左に、大きな値が基準値より右にきています。
               Exit Do
            End If
            '双方の値を交換します。
            vntWk = vntSortData(lngIdxL)
            vntSortData(lngIdxL) = vntSortData(lngIdxR)
            vntSortData(lngIdxR) = vntWk
            '配列のインデックスの小さい方から基準値に向かってのインデックスを更新する。
            lngIdxL = lngIdxL + 1
            '配列のインデックスの大きい方から基準値に向かってのインデックスを更新する。
            lngIdxR = lngIdxR - 1
        Loop
        '左の配列の処理が必要か
        If (lngMin < lngIdxL - 1) Then
              '基準値の左の配列に対してのソート処理を行う。
              QuickSort vntSortData(), lngMin, lngIdxL - 1
        End If
        '右の配列の処理が必要か
        If (lngMax > lngIdxR + 1) Then
              '基準値の右の配列に対してのソート処理を行う。
              QuickSort vntSortData(), lngIdxR + 1, lngMax
        End If
End Sub

'QuickSort使用例
Sub Test()
    Dim vntwkx(8)   As Variant
    
    vntwkx(0) = "2"
    vntwkx(1) = "9"
    vntwkx(2) = "8"
    vntwkx(3) = "3"
    vntwkx(4) = "5"
    vntwkx(5) = "4"
    vntwkx(6) = "1"
    vntwkx(7) = "7"
    vntwkx(8) = "6"
    QuickSort vntwkx(), 0, 8
    
    vntwkx(0) = 2
    vntwkx(1) = 9
    vntwkx(2) = 8
    vntwkx(3) = 3
    vntwkx(4) = 5
    vntwkx(5) = 4
    vntwkx(6) = 1
    vntwkx(7) = 7
    vntwkx(8) = 6
    QuickSort vntwkx(), 0, 8
End Sub

ソートする配列のエリアが、Variantなので、整数型と文字列型の両方が対応できます。また、*1と*2の通りに2箇所を変更するだけで昇順から降順になります。

とにかく、クイックソートの実装は難しいです。上記ソースは、あくまでもコーディング例(間違っているかも)であり、何かに流用する場合は、ご自分の責任でお願いします。

クイックソートの参考URL

おわりに

以下のページには、すべてのTIPSがあります。もしよろしければ、どうぞ!

尚、ご感想、ご意見、誤字、脱字、間違い等がありましたら遠慮なくVB-TIPS掲示板へご指摘ください。