午後わてんのブログ

ベランダ菜園とWindows用アプリ作成(WPFとC#)

エクセルVBAでクイックソート

 
基準値を配列の中から選んで基準値以上の値を配列の右へ、基準値以下は左へ寄せてから基準値の場所で配列を二分割、この処理を分割した配列それぞれで繰り返す
 
'vが配列、tは並び替える範囲の先頭の添字(index)、bは最後尾の添字
Sub QuickSort4(v As Variant, t As Long, b As Long)
   'ピボット、基準点、真ん中にしたのでmiddle
    Dim m As Long: m = (b + t) \ 2 '演算子\は割り算の商部分
    Dim p As Long: p = v(m) '基準値
    Dim l As Long: l = t '左の場所
    Dim r As Long: r = b '右の場所
    Dim tmp As Variant
    Do
       '基準値以下の場所取得
        Do While v(l) < p
            l = l + 1
        Loop
       '基準値以上の場所取得
        Do While v(r) > p
            r = r - 1
        Loop
       '左右の位置を比較
        If l >= r Then
           '左右が同じか逆ならループ抜け
            Exit Do
        Else
           '左右が順なら値を入れ替え
            tmp = v(l)
            v(l) = v(r)
            v(r) = tmp
            l = l + 1 '次の探索開始場所を1つ右へ
            r = r - 1 '次の探索開始場所を1つ左へ
        End If
    Loop
   '配列を分割して再帰処理
    If t < l - 1 Then Call QuickSort4(v, t, l - 1) '分割の左側
    If r + 1 < b Then Call QuickSort4(v, l, b) '分割の右側
End Sub
 
これと
Sub testQuick4(v As Variant)
    Call QuickSort4(v, LBound(v), UBound(v))
End Sub
これの組み合わせで使う
 
 
配列を並べ替えるなら
Sub quickSort()
    Dim v As Variant
    v = Array(1, 2, 4, 2, 8, 9, 6, 8)
    Call testQuick4(v)
End Sub
こう
 
セルの値を並べ替えるなら
 
Sub bubble1000()
    Dim v() As Variant
    Dim y As Long: y = 10000
    v = WorksheetFunction.Transpose(Sheets("Sheet3").Range("a1:a" & y))
    Call testQuick4(v)
    Sheets("Sheet3").Range("b1:b" & y) = WorksheetFunction.Transpose(v)
End Sub
これはSheet3のA1:A10000の値を並べ替えてB1:B10000に記入する
 
 
1万件のランダム数値をソートするときの処理時間計測
OS:Windows 10
Excel2007
CPU:PhenomⅡ X3 720BE @3.0GHz
の環境で
計測するマクロはいつもの
Sub sortTestBubble2()
    Dim c As Long: c = 10000
    Dim v() As Variant
    ReDim v(c - 1)
    Randomize
    For i = 0 To c - 1
        v(i) = CLng(c * Rnd)
    Next
    Dim st As Single
    st = Timer
    Call testQuick4(v) 'クイックソート
    MsgBox Timer - st & "秒"
End Sub
 
イメージ 1
評判通りの最速
1回1回計測するとタイムがばらつくので
10回連続で処理しての平均
イメージ 2
0.03秒!
これまで一番速かったコムソートとシェルソートの0.0625秒の2倍速い!
 
グラフで
イメージ 3
 
1秒以下のものだけと比較
イメージ 6
 
100万件をソート
イメージ 4
件数を増やしても速くて4秒台で
これもコムソート、シェルソートの2倍速い
 
今までのまとめ

f:id:gogowaten:20191031112344p:plain

 
 
 
 
まともなクイックソートを書いたここまで来るのに1ヶ月かかった
最後の方にある
If r + 1 < b Then Call QuickSort4(v, l, b) '分割の右側
これ
分割した右側の配列を再帰処理に行くかどうかの判定の
If r + 1 < b Then
これが思いつかなくて同じ数値がある場合に無限ループになっていた
rは右側から左へ探索した基準値以下の数値の場所
bは探索範囲の最後尾の場所
たしか
If l < b Then
って書いてたのかな、これだと同じ数値がある場合には無限ループ
これを解消するのに色々遠回りな継ぎ接ぎをしてできたクイックソートが3秒もかかる代物でぜんぜんクイックじゃなかったwここでクイックソートは諦めて基本って言われるバブルソートを書いていて、Wikipediaを見ていたら他にも色々なソート方法があるのを知っていろいろ試して1ヶ月、やっとクイックなクイックソートが書けた。書けたといってもしっくりこないというかなんかイマイチ納得いかないというか相性が良くないのかなあ、1番速いんだけどねえ。速さで驚いたのはコムソートとシェルソートバブルソートの10秒台や偽クイックソートが3秒のところに0.06秒だったからホント驚いた、それにコードにするのもすんなりできた
マージソートクイックソートでも使っているけど再帰処理ってのが少しわかったかなあ、でも頭がこんがらがる、こんがらがるって言葉も面白いなあ、いったんマージソートも書けたぞってググっていたら再帰処理を使わないボトムアップ型ってのもあってこれで書いたら2倍も速くなったのは面白かった
ヒープソートWikipedia見ても全くわからなかったんだよねえ、まずヒープってのが何なのかからググってなんとなくわかった気になって、でもわかって無くてを何回か繰り返してなんとか書いた感じ、だから記事もあとから見ても思い出せるようにって書いたからあんなに長くなった
Wikipediaで説明があるソート方法はだいたい書けたので、諦めていたクイックソートを書き直そうかってことで今回やっと書けたってわけ
書けたので”VBA クイックソート”でぐぐったら
1次元配列の並べ替え(バブルソート,クイックソート)|ExcelマクロVBAサンプル集
http://excel-ubara.com/excelvba5/EXCELVBA228.html
こちらの方のコードとそっくりで驚くと同時に、ああこれであっているんだという安心感
クイックソートで始まってクイックソートで終わった?感じかなあ
次回はソートする値(配列)の状態によってどんなふうに処理時間が変わるのか、変わらないのか
 
 
 
前回
エクセルVBAヒープソート ( ソフトウェア ) - 午後わてんのブログ - Yahoo!ブログ
https://blogs.yahoo.co.jp/gogowaten/14814563.html
次回
エクセルVBAでソートアルゴリズムまとめ
エクセルVBAで、ソートアルゴリズムとデータの違いによるソート処理時間比較 ( ソフトウェア ) - 午後わてんのブログ - Yahoo!ブログ
https://blogs.yahoo.co.jp/gogowaten/14836198.html