[[20230321142747]] 『VBA マージソートのコード解読』(隠居Z) ページの最後に飛ぶ

[ 初めての方へ | 一覧(最新更新順) | 全文検索 | 過去ログ ]

 

『VBA マージソートのコード解読』(隠居Z)

こんにちわ。^^
三日ほど再帰を使ったコード、眺めてるのですが
終盤の大小比較、入れ替えをしながら、マージ
する箇所で、乳酸菌のよ〜に、増殖して、元の
配列と、同じ大きさになる箇所のパラメータの
変化が解りません。お詳しい方、で、かつ
私の様な頭の悪い老人でも理解できるように
説明してやろうと、温かいお気持ちをお持ちの
回答者様、是非ご教授たまわれば、とてもうれ
しいです。( ̄▽ ̄)
ここのサイトが良いとか
この書籍読めば、サルでも解るよ
とかも、御座いましたら、大歓迎です
もう、無理せず、そのまま死ねって、言わない方だけ
お願い致します。
トレースしているコードのURL
https://www.hokkyokun.com/vba-mergesort/
あやしげな、サイトではなかったですよ。^^;
m(__)mm(__)mm(__)m

< 使用 アプリ:Excel 2016 365タイプ、使用 OS:Windows10 >


 こんばんは!
珍しいひとからの質問なので調べてみました。
ご提示のコードは一次元なので二次元に描き直そうかと思いましたが既にありました。💦
私も意味なんてわかりませんが、変数の名前を自分流に置換されると理解が進むかもですよ
頑張ってくださいね
では、では、また

https://qiita.com/HiroshiAkutsu/items/0c6b3a1c1ab54e3f9fe1
(SoulMan) 2023/03/21(火) 18:40:20


ありがとうございます。〜^^
ご無沙汰いたしております。
取り合えず、御礼まで。
謹んで、拝読いたします。m(__)mm(__)mm(__)m
(隠居Z) 2023/03/21(火) 18:45:50

 こんにちは

 処理を分けて追っかけてみたらどうでしょう
 と思って書き換えて見ました

 Sub test の N を N=2 から徐々に増やして実行してみるのがいいかと。

 分からない部分をもう少し具体的に聞いてもらえるとよいです
 
    Enum mySortOder
       ASCENDING = -1
       DESCENDING = 0
    End Enum

    Sub test()
       Const N = 10
       Dim Ary(1 To N)
       For i = 1 To N
          Ary(i) = Int(Rnd * 100)
       Next
       Stop
       MergeSort Ary, ASCENDING      ' 昇順でソート
       Stop
       MergeSort Ary, DESCENDING     ' 降順でソート
       Stop
    End Sub

    Sub MergeSort(Ary(), Optional ByVal Order As mySortOder = ASCENDING)
        Dim LAry(), RAry()
        If UBound(Ary) - LBound(Ary) < 1 Then Exit Sub
        DevideAry Ary, LAry, RAry
        MergeSort LAry, Order
        MergeSort RAry, Order
        MergeAry Ary, LAry, RAry, Order
    End Sub

    Sub DevideAry(Ary(), LAry(), RAry())
        Dim k As Long, i As Long, l As Long, m As Long
        l = LBound(Ary)     ' 次元の最小
        m = UBound(Ary)     ' 次元の最大
        k = (l + m) \ 2     ' 次元の最小と最大の中点
        ReDim LAry(l To k)
        ReDim RAry(k + 1 To m)
        For i = l To k
            LAry(i) = Ary(i)
        Next
        For i = k + 1 To m
            RAry(i) = Ary(i)
        Next
    End Sub
    Sub MergeAry(Ary(), LAry(), RAry(), Order As mySortOder)
        Dim iL As Long, nL As Long, iR As Long, nR As Long
        Dim i As Long
        iL = LBound(LAry): nL = UBound(LAry)
        iR = LBound(RAry): nR = UBound(RAry)
        i = LBound(Ary)
        Do While iL <= nL And iR <= nR
           If (LAry(iL) > RAry(iR)) = Order Then  ' 2023/3/23 10:13 修正
              Ary(i) = RAry(iR)
              iR = iR + 1
           Else
              Ary(i) = LAry(iL)
              iL = iL + 1
           End If
           i = i + 1
        Loop
        Do While iL <= nL
           Ary(i) = LAry(iL)
           iL = iL + 1
           i = i + 1
        Loop
        Do While iR <= nR
           Ary(i) = RAry(iR)
           iR = iR + 1
           i = i + 1
        Loop
    End Sub
(´・ω・`) 2023/03/21(火) 19:09:24

(´・ω・`)さん
コード、ありがとうございます。
これを使わせて戴いて、私なりにトレース後、今少し
具体的に、疑問点をお聞きしたいと思います。
時間をかけて、じっくり、学習してみますので、暫し
御猶予[1週間ほど^^;]を、
ありがとうございます。
m(_ _)m
(隠居Z) 2023/03/21(火) 19:21:16

 Sub MergeSortを途中の処理が分かるようにイミディエイトウインドウに書き出すようにしました
 こちらに置き換えてやってみるとなにか手がかりがつかめるかと

    Sub MergeSort(Ary(), Optional ByVal Order As mySortOder = ASCENDING, Optional ByVal t = 0)
        Dim LAry(), RAry()
        If UBound(Ary) - LBound(Ary) < 1 Then: Debug.Print String(t, vbTab); "←(" & LBound(Ary) & ")のソート結果"; Ary(UBound(Ary)): Exit Sub
        Debug.Print String(t, vbTab); "→(" & LBound(Ary); ")〜(" & UBound(Ary) & ")をSORT";
        For i = LBound(Ary) To UBound(Ary) - 1: Debug.Print Ary(i); ",";: Next: Debug.Print Ary(i)
        DevideAry Ary, LAry, RAry
        MergeSort LAry, Order, t + 1
        MergeSort RAry, Order, t + 1
        Debug.Print String(t + 1, vbTab); "(" & LBound(Ary); ")〜(" & UBound(Ary) & ")を結合"
        MergeAry Ary, LAry, RAry, Order
        Debug.Print String(t, vbTab);
        Debug.Print "←(" & LBound(Ary); ")〜(" & UBound(Ary) & ")のSORT結果";
        For i = LBound(Ary) To UBound(Ary) - 1: Debug.Print Ary(i); ",";: Next: Debug.Print Ary(i)
    End Sub
(´・ω・`) 2023/03/21(火) 22:29:07

こんばんわ。。。^^
重ね重ねの、ご配慮、深く感謝いたします。
早速差し換え、テスト開始致しますです。
ありがとう御座いました。
m(__)m
(隠居Z) 2023/03/21(火) 23:02:07

 昨晩、つらつらと考えて、コードに間違いがあるなぁと気づきました

 Sub MergeAry の以下の部分に問題があります。

           If (LAry(iL) < RAry(iR)) = Order Then  
              Ary(i) = LAry(iL)
              iL = iL + 1
           Else
              Ary(i) = RAry(iR)
              iR = iR + 1
           End If
           i = i + 1

 LAry(iL) = RAry(iR) のときに、LAry(iL)が先に入る様にしないと安定なソートになりません。
 安定なソートであることがマージソートのメリットなので、こりやまずいですね

 というわけで、以下のように修正が必要です

           If (LAry(iL) > RAry(iR)) = Order Then
              Ary(i) = RAry(iR)
              iR = iR + 1
           Else
              Ary(i) = LAry(iL)
              iL = iL + 1
           End If
 
 再帰プログラムの練習と意味ではあまり関係ありません

 2023/03/21(火) 19:09:24のコードもこっそり直しておきます
(´・ω・`) 2023/03/23(木) 10:12:23

こんにちわ。^^
お手を煩わせ、恐縮です。更なる、詳細のご説明
重ね重ね御礼申し上げます。m(__)m
なにせ、何が、安定で、何が不安定なのかも良く理解出来ておりません。
後日、学びなおします。

SoulManさん、(´・ω・`)さん
お付き合い、賜り、本当に有難う御座いました。私の頭の中で
【再帰呼び出しのコード実行の流れ】←これの認識が出来ていなかったようです。
1.配列変数Aryの要素数及び要素の動きが変化することが、再定義もしていないのに
  変化する、 LAry(), RAry()と置き換わるので、減るのは理解できるのですが
  増殖するのが不思議でした。
呼び出した次の箇所へ呼び出した回数分戻る。!!←これ、忘却致しておりました。
と言うか、普段、使う事が殆ど御座いませんので、あまり良く理解できていなかった
ようです。m(__)m

私なりに、ソートとは何ら関係有りませんが、再帰こさえて、確認
してみました。[研究発表^^;]

 Option Explicit
Dim wt&
Sub OneInstanceMain()
    Dim v() As Variant
    v = Array("E", "D", "J", "C", "F", "X")
    Worksheets("Sheet1").UsedRange.Clear
    wt = 0
    change v
    MsgBox "再帰呼び出しの回数 = " & wt - 1
End Sub
Private Sub change(v())
    wt = wt + 1
    Dim x(), i&, lR&
    wSWrite v
    If UBound(v) <= 0 Then Exit Sub
    ReDim x(UBound(v) - 1)
    For i = 0 To UBound(v) - 1
        x(i) = Chr(Int((90 - 65 + 1) * Rnd + 65))
    Next
    change x
    wSWrite v
End Sub
Private Sub wSWrite(v())
    Dim lR&
    With Worksheets("Sheet1")
        lR = .Cells(.Rows.Count, 1).End(xlUp).Row + 1
        lR = IIf(lR > 1 And .Cells(1) = "", 1, lR)
        .Cells(lR, 1).Resize(, UBound(v) + 1) = v
    End With
End Sub
何とか解ったような気がいたします。
自分でマージソート、練習で組んでみます。← できるかどぉかかなり怪しい(*^^*)?
ありがとうございました。
m(__)m
(隠居Z) 2023/03/23(木) 13:42:06

安定ソート?
言葉の意味は理解致しました。Akeyでソートした場合に
 Akey Bkey
カレー 牛
カレー 豚
の場合
カレー 牛
カレー 豚
となり
カレー 豚
カレー 牛
とは
確実にならない=安定
成る場合もあるし成らない場合もある=不安定?

良いのでしょうか^^;、お暇な時にでも。。。m(__)m

(隠居Z) 2023/03/23(木) 14:46:45


隠居Zさんの考えの通りです。

安定ソート :同一値でソート前に前方にあったものがそのまま前方にある
不安定ソート:同一値でソート前に前方にあったものがそのまま前方にあるとは限らない

不安定ソートの代表的なものがクイックソートです。
(火災報知器) 2023/03/23(木) 15:02:46


火災報知器さん、ありがとうございます。
了解いたしました。
m(__)m
(隠居Z) 2023/03/23(木) 15:08:13

 「安定なソート」については火災報知器さんの回答のとおりです。

 >増殖するのが不思議でした
 増殖っていうのは、実際はどのような動作のことをいってますか? 
 全然わからないので教えてください
(´・ω・`) 2023/03/23(木) 16:20:35

 失礼します。
[[20170724204331]]←このトピを思い出しましたのでご案内。
 トピ主さん自身が挙げられているコードに、再帰レベル(深さ)を管理するStatic変数が使われてました。参考になるかも知れません。
 使われてたのはクイックソート内でしたけど、最悪パターン回避目的でマージソートも一緒に組み込まれてます。そちらも参考になるのでは。

 ↓私もちょっと抜粋させてもらって遊んでみました。

    Rem マージソート1次元配列用 ←単体では絶対使うこと無いやろな ================================================
    Public Sub MergeSort(Target(), indexFrom As Long, indexTo As Long, Optional Desc As Boolean)
        Static LvA As Long, LvB As Long
    Rem オプション **********************************
    Rem     Decs --------- 降順に並べる
    Rem *********************************************
    Rem 対象区間が既にソート済みだったら何もしないで抜ける
    ''''    If IsSorted(Target, indexFrom, indexTo, Desc) Then Exit Sub
        Dim EndOfA As Long, StartOfB As Long
    Rem 再帰処理で配列をAパートとBパートに2分割
        EndOfA = indexFrom + Int((indexTo - indexFrom) / 2)
        StartOfB = EndOfA + 1
        If EndOfA > indexFrom Then
            LvA = LvA + 1
            Call MergeSort(Target, indexFrom, EndOfA, Desc)
            LvA = LvA - 1
        End If
        If StartOfB < indexTo Then
            LvB = LvB + 1
            Call MergeSort(Target, StartOfB, indexTo, Desc)
            LvB = LvB - 1
        End If
    Rem 分割したAパートとBパートを比較してソート済み仮配列を作成
        Dim SWP() As Variant
        Dim i As Long
        Dim CurA As Long, CurB As Long
        Dim SortFlg As Boolean
        ReDim SWP(indexFrom To indexTo)
        CurA = indexFrom
        CurB = StartOfB
        For i = indexFrom To indexTo
            If CurA > EndOfA Then      'Aパートが処理済ならBパートの残りを仮配列に書込み
                SWP(i) = Target(CurB)
                CurB = CurB + 1
            ElseIf CurB > indexTo Then 'Bパートが処理済ならAパートの残りを仮配列に書込み
                SWP(i) = Target(CurA)
                CurA = CurA + 1
            Else                       'どちらも残ってたら比較して一方を仮配列に書込み
                If Desc Then '昇順降順の指定に従って判定
                    SortFlg = Target(CurA) >= Target(CurB)
                Else
                    SortFlg = Target(CurA) <= Target(CurB)
                End If
                If SortFlg Then '判定結果に基づき、一方を仮配列に書込み
                    SWP(i) = Target(CurA)
                    CurA = CurA + 1
                Else
                    SWP(i) = Target(CurB)
                    CurB = CurB + 1
                End If
            End If
        Next
    Rem 仮配列をそのまま元配列に転記
        Debug.Print " ------------------------+------------------------+------------------------+------------------------+"; " 再帰深度"; LvA + LvB; "("; LvA; "+"; LvB; ")"
        Debug.Print Spc((LvA + LvB) * 25 + 1); Join(Target, "|")
        For i = indexFrom To indexTo
            Target(i) = SWP(i)
        Next
        SWP = Target
        For i = LBound(Target) To UBound(Target)
            SWP(i) = " "
            If i >= indexFrom And i <= indexTo Then SWP(i) = "v"
        Next
        Debug.Print Spc((LvA + LvB) * 25 + 1); Join(SWP, " ")
        Debug.Print Spc((LvA + LvB) * 25 + 1); Join(Target, "|")
    End Sub

 で、テスト

    Sub test()
        Dim v()
        v = [{6,3,8,4,3,5,8,9,2,6,1,3,3}]
        Call MergeSort(v, LBound(v), UBound(v))
    End Sub

 ↓実行結果

 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 3 ( 3 + 0 )
                                                                            6|3|8|4|3|5|8|9|2|6|1|3|3
                                                                            v v                      
                                                                            3|6|8|4|3|5|8|9|2|6|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 3 ( 2 + 1 )
                                                                            3|6|8|4|3|5|8|9|2|6|1|3|3
                                                                                v v                  
                                                                            3|6|4|8|3|5|8|9|2|6|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 2 ( 2 + 0 )
                                                   3|6|4|8|3|5|8|9|2|6|1|3|3
                                                   v v v v                  
                                                   3|4|6|8|3|5|8|9|2|6|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 3 ( 2 + 1 )
                                                                            3|4|6|8|3|5|8|9|2|6|1|3|3
                                                                                    v v              
                                                                            3|4|6|8|3|5|8|9|2|6|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 2 ( 1 + 1 )
                                                   3|4|6|8|3|5|8|9|2|6|1|3|3
                                                           v v v            
                                                   3|4|6|8|3|5|8|9|2|6|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 1 ( 1 + 0 )
                          3|4|6|8|3|5|8|9|2|6|1|3|3
                          v v v v v v v            
                          3|3|4|5|6|8|8|9|2|6|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 3 ( 2 + 1 )
                                                                            3|3|4|5|6|8|8|9|2|6|1|3|3
                                                                                          v v        
                                                                            3|3|4|5|6|8|8|2|9|6|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 2 ( 1 + 1 )
                                                   3|3|4|5|6|8|8|2|9|6|1|3|3
                                                                 v v v      
                                                   3|3|4|5|6|8|8|2|6|9|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 3 ( 1 + 2 )
                                                                            3|3|4|5|6|8|8|2|6|9|1|3|3
                                                                                                v v  
                                                                            3|3|4|5|6|8|8|2|6|9|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 2 ( 0 + 2 )
                                                   3|3|4|5|6|8|8|2|6|9|1|3|3
                                                                       v v v
                                                   3|3|4|5|6|8|8|2|6|9|1|3|3
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 1 ( 0 + 1 )
                          3|3|4|5|6|8|8|2|6|9|1|3|3
                                        v v v v v v
                          3|3|4|5|6|8|8|1|2|3|3|6|9
 ------------------------+------------------------+------------------------+------------------------+ 再帰深度 0 ( 0 + 0 )
 3|3|4|5|6|8|8|1|2|3|3|6|9
 v v v v v v v v v v v v v
 1|2|3|3|3|3|4|5|6|6|8|8|9

(白茶) 2023/03/23(木) 17:02:54


(´・ω・`)さま へ
 >増殖するのが不思議でした
分割して要素数は減らしているのに、最終結果は元の大きさと同じ
なのが、わたしの勘違い。?はてな?おしえて〜、わからないよ〜(T_T)
でした。
ま
当たり前と言えば、当たり前なのですが、何分、当方、ぼけ老人なので
お許しを。m(__)m
作っていただいたサンプルで、コードの流れを読むことが出来ました
ありがとうございます。m(__)m
(白茶)さん、ありがとうございます。最近ひまなので、ゆっくりと
お勉強させて戴きます。コード&解説、有難う御座いました。
取り急ぎ、御礼まで。
m(__)m

(隠居Z) 2023/03/23(木) 17:30:54


 >最終結果は元の大きさと同じ
 なるほどです

 Sub MergeSortの中はこうなってまして

     DevideAry Ary, LAry, RAry         ' 右と左に分けて
     MergeSort LAry, Order       ' 左をソート
     MergeSort RAry, Order       ' 右をソート 
     MergeAry Ary, LAry, RAry, Order  ’右と左を合体

 これを
    ステップイン(F8)で実行すると、頭がぐにゅぐにゅしますが、
   ステップオーバー(Shift+F8)で実行すると、当たり前すぎてフフフンという感じになります

 ステップオーバーで理解できれば十分だと私は思ってます
(´・ω・`) 2023/03/23(木) 18:42:14

ステップオーバー(Shift+F8)
うwww。。。^^;
知りませんでした。。。早速やってみますです。(#^^#)v
ありがとうございます。m(__)m
(隠居Z) 2023/03/23(木) 19:28:00

あああ。。。なるほど。
プロシジャー単位で実行してくれるみたいですね。
これは、これで、確かに、便利ですね。勉強になりました
活用させて戴きます。^^。m(__)m
(隠居Z) 2023/03/23(木) 20:07:24

おはようございます。^^
白茶さん
ありがとうございました。再帰の様子がテキスト表示されて
処理内容が解りやすいですね。マージソートに挑戦する時、
参考にさせて戴きます。
(´・ω・`)さん
白茶さん
SoulManさん[もう、つくしが出てくる頃ですね。。。(#^^#)v]
ありがとうござしました。おかげさまで、理解出来たようです。
                   
                     ↑

   私の事なのでそのような気がするだけかもですが。。。( ̄▽ ̄)
m(__)m

(隠居Z) 2023/03/24(金) 09:48:02


 こんばんは!
先日土筆を採って来ましたよ。
技術的なことでお力になれず申し訳ないです。
でも、良い内容になりましたね。
私も勉強させていただいております。
ありがとうございます😊
(SoulMan) 2023/03/24(金) 22:52:34

こんばんわ〜^^
こちらこそ
ありがとうございました。
また、宜しくお願い致します。m(__)m
(隠居Z) 2023/03/24(金) 23:02:57

コメント返信:

[ 一覧(最新更新順) ]


YukiWiki 1.6.7 Copyright (C) 2000,2001 by Hiroshi Yuki. Modified by kazu.