VBでのクイックソートについて
普通、ソートは、DBを使っている時は、まず、SQL上のOrder Byでソートし、つぎにVB上のロジックでソートし、そのつぎにEXCEL上のメソッドでソートします。
VB上でソートしたい時は、配列内の重複データ削除の前処理としてソートするとかで、それには、クイックソートがもっとも速いとされています。
クイックソートのアルゴリズム
- まず、配列の中央付近のインデックスの内容値を基準値とします。
- 配列のインデックスの小さい方から基準値に向かって、基準値より大きい値を探します。
- 配列のインデックスの大きい方から基準値に向かって、基準値より小さい値を探します。
- ２と３の双方の値を交換します。 そして、２から３を繰り返すと５の状態になります。
- 基準値より小さな値が基準値より左に、大きな値が基準値より右にきます。
- つぎに、基準値の左の配列と右の配列に対して、１から４のを繰り返します。
- 各々配列の要素が１になるまで、上記を繰り返せば、結果的に全配列内がソートされるわけです。
クイックソートのアルゴリズム具体例
インデックス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 '＊１、降順は『>=』を『<=』 にする。
Exit For
End If
Next
'配列のインデックスの大きい方から基準値に向かって、インデックス内容値が基準値より小さい値かイコールな値を探します。
For lngIdxR = lngIdxR To lngMin Step -1
If (vntSortData(lngIdxR) <= vntKijunChi) Then '＊２、降順は『<=』を『>=』 にする。
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なので、整数型と文字列型の両方が対応できます。また、＊１と＊２の通りに2箇所を変更するだけで昇順から降順になります。
とにかく、クイックソートの実装は難しいです。上記ソースは、あくまでもコーディング例（間違っているかも）であり、何かに流用する場合は、ご自分の責任でお願いします。
