アルゴリズム日記 2022/10/12

10月12日

今マージソートを勉強しているのですが難しいので日記をつけて整理することにしました。
プログラムソースは以下です。
https://github.com/suzukiiichiro/Algorithms-And-Data-Structures/blob/master/Bash/05_1MergeSort.sh

ロジックは配列を上半分と下半分に分割して行き、分割しきったら分割したものをマージするようにソートしていくという動きです
イメージですと以下の動きですが

0,1,2,3,4,5,6,7,8,9|

0,1,2,3,4|5,6,7,8,9|

0,1,2|3,4|5,6,7|8,9|

0,1|2|3|4|5,6|7|8|9|

0|1|2|3|4|5|6|7|8|9|<--分割しきる

0,1|2|3,4|5,6|7|8,9|<--マージソート開始

0,1,2|3,4|5,6,7|8,9|

0,1,2,3,4|5,6,7,8,9|

0,1,2,3,4,5,6,7,8,9|

プログラムの動きは最初下半分の0,1,2,3,4を取り出し、さらにその下半分の0,1,2を取り出し、そこから0,1を取り出し、0と1に分割しきったら0,1をマージソートするというようにより下の部分を半分ずつ取り出し分割しきったらマージソートする。ソートしたらもう半分を分割してソートというような感じになります。

0,1,2,3,4,5,6,7,8,9

0,1,2,3,4 | 

0,1,2 |

0,1|   

0|1| 

0,1| <--マージソート

0,1|2|

0,1,2|<--マージソート

     |3,4|
     |3|4|
     |3,4|<--マージソート
0,1,2|3,4|<--マージソート 
0,1,2,3,4|<--マージソート

         |5,6,7,8,9|
         |5,6|
         |5|6|
         |5,6|<--マージソート
         |5,6|7|
         |5,6,7|<--マージソート
               |8,9|
               |8|9|
               |8,9|<--マージソート 
         |5,6,7|8,9|
         |5,6,7,8,9|<--マージソート
0,1,2,3,4|5,6,7,8,9|<--マージソート
0,1,2,3,4,5,6,7,8,9<--マージソート

プログラムを見てみましょう。
mergeメソッドをみて下さい。
2つの再帰呼び出しと、実際にsortしているmargeSortLogicがキモです。

・low 前半分をソート
mergeSort “$lowerBound” “$mid” ;

・upp 後半分をソート
mergeSort “$((mid+1))” “$upperBound”

・sort 両者をマージ
mergeSortLogic “$lowerBound” “$((mid+1))” “$upperBound” ;

low,upp,sortの順に処理して行きます。

low,uppは再帰呼び出しなので、
基底条件にマッチするまでは再帰呼び出しにより先頭にあるlowが再帰呼び出しされ続ける
low->再帰->low->再帰->low->再帰

lowからupp uppからsortに移動するには
基底条件(第１引数 lowerBound 第２引数 upperBoundの値が同じ)にマッチして再帰から戻る必要がある。

low->再帰->基底条件にマッチ->一つ前の再帰に戻る->uppに進む

upp->再帰->基底条件にマッチ->一つ前の再帰に戻る->sortに進む

再帰から抜ける条件は２箇所
・基底条件
if [ “$lowerBound” -eq “$upperBound” ]; then
echo “1:$lowerBound$upperBound:範囲が１なら再帰呼び出しの終了 基底条件”
#ソートは不要
:

・処理が最後まで行った時
　mergeSortLogic 完了時

呼び出しの具体的な動作は以下となります。

0,9->low->0,4->low->0,2->low->0,1->low->0,0->基底条件
                                                   0,1->upp->1,1->基底条件
                                                   0,1->sort->一番下(0,1をソート)
                                  0,2->upp->2,2->基底条件
                                  0,2->sort->一番下(0,1,2をソート)
                 0,4->upp->3,4->low->3,3->基底条件
                                   3,4->upp->4,4-> 基底条件
                                   3,4->sort->一番下(3,4をソート)
                0,4->sort->一番下(0,1,2,3,4をソート)
0,9->upp->5,9->low->5,7->low->5,6->low->5,5->基底条件
                                                ->5,6->upp->6,6->基底条件
                                                ->5,6->sort->一番下(5,6をソート)
                                  5,7->upp->7,7->基底条件
                                  5,7->sort->一番下(5,6,7をソート)
                 5,9->upp->8,9->low->8,8->基底条件
                                   8,9->upp->9,9->基底条件
                                   8,9->sort->一番下(8,9をソート)
                 5,9->sort->一番下(5,6,7,8,9をソート)
0,9->sort->一番下(0,1,2,3,4,5,6,7,8,9をソート)                             

書籍の紹介