[ 初めての方へ | 一覧(最新更新順) | 全文検索 | 過去ログ ]
『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
こんにちは
処理を分けて追っかけてみたらどうでしょう と思って書き換えて見ました
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
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
昨晩、つらつらと考えて、コードに間違いがあるなぁと気づきました
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
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
(隠居Z) 2023/03/23(木) 14:46:45
安定ソート :同一値でソート前に前方にあったものがそのまま前方にある
不安定ソート:同一値でソート前に前方にあったものがそのまま前方にあるとは限らない
不安定ソートの代表的なものがクイックソートです。
(火災報知器) 2023/03/23(木) 15:02:46
「安定なソート」については火災報知器さんの回答のとおりです。
>増殖するのが不思議でした 増殖っていうのは、実際はどのような動作のことをいってますか? 全然わからないので教えてください (´・ω・`) 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
私の事なのでそのような気がするだけかもですが。。。( ̄▽ ̄)
m(__)m
(隠居Z) 2023/03/24(金) 09:48:02
こんばんは! 先日土筆を採って来ましたよ。 技術的なことでお力になれず申し訳ないです。 でも、良い内容になりましたね。 私も勉強させていただいております。 ありがとうございます😊 (SoulMan) 2023/03/24(金) 22:52:34
[ 一覧(最新更新順) ]
YukiWiki 1.6.7 Copyright (C) 2000,2001 by Hiroshi Yuki.
Modified by kazu.