エクセル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回計測するとタイムがばらつくので

10回連続で処理しての平均

0.03秒！

これまで一番速かったコムソートとシェルソートの0.0625秒の2倍速い！

グラフで

1秒以下のものだけと比較

100万件をソート

件数を増やしても速くて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秒もかかる代物でぜんぜんクイックじゃなかったｗここでクイックソートは諦めて基本って言われるバブルソートを書いていて、Wikipediaを見ていたら他にも色々なソート方法があるのを知っていろいろ試して1ヶ月、やっとクイックなクイックソートが書けた。書けたといってもしっくりこないというかなんかイマイチ納得いかないというか相性が良くないのかなあ、1番速いんだけどねえ。速さで驚いたのはコムソートとシェルソート！バブルソートの10秒台や偽クイックソートが3秒のところに0.06秒だったからホント驚いた、それにコードにするのもすんなりできた

マージソートはクイックソートでも使っているけど再帰処理ってのが少しわかったかなあ、でも頭がこんがらがる、こんがらがるって言葉も面白いなあ、いったんマージソートも書けたぞってググっていたら再帰処理を使わないボトムアップ型ってのもあってこれで書いたら2倍も速くなったのは面白かった

ヒープソートはWikipedia見ても全くわからなかったんだよねえ、まずヒープってのが何なのかからググってなんとなくわかった気になって、でもわかって無くてを何回か繰り返してなんとか書いた感じ、だから記事もあとから見ても思い出せるようにって書いたからあんなに長くなった

Wikipediaで説明があるソート方法はだいたい書けたので、諦めていたクイックソートを書き直そうかってことで今回やっと書けたってわけ

書けたので”VBA クイックソート”でぐぐったら