平成31年春期 午前問題6
次の手順はシェルソートによる整列を示している。データ列7，2，8，3，1，9，4，5，6を手順(1)～(4)に従って整列するとき，手順(3)を何回繰り返して完了するか。ここで，[ ]は小数点以下を切り捨てた結果を表す。
手順２は理解しくいですね。
手順に沿って整列を行うと次のようになります。
（１）H←9÷3＝3
（２）要素ごとが互いに3つずつ離れた要素から成る3つの部分文字列に分解し、それぞれ整列を行います。 ←こんな意味ですよ。
[部分列1] 7,3,4 →(整列)→ 3,4,7
[部分列2] 2,1,5 →(整列)→ 1,2,5
[部分列3] 8,9,6 →(整列)→ 6,8,9
（３）H←3÷3＝1 //1回目
（４）H≠0なので2に戻る
（２）要素ごとが互いに1つずつ離れた要素から成る 3,4,7,1,2,5,6,8,9 を整列し、1,2,3,4,5,6,7,8,9 とします。
H←1÷3＝0(小数点未満切り捨て) //2回目
この時点でHが0になるためデータ列の整列は完了します。したがって(3)の処理が繰り返される回数は2回です。
挿入法
挿入ソート（基本挿入法）とは
挿入ソートとは、「未整列な配列」から値を1つずつ取り出し「整列済み配列」の適切な位置に挿入していく手法です。
・「未整列配列」から値から1つ取り出します。
・取り出した値を「整列済み配列」の適切な位置に挿入します。
・1と2を繰り返し全て「整列済み配列」に挿入し終われば完了となります。
つまり、シェルソートは、まずデータ列を小さい若干データ列に分けて、各自が挿入法によりソースしていて、あとは、合わせてソートするということですね。
参考：
https://www.ap-siken.com/kakomon/24_haru/q7.html
挿入法
https://medium-company.com/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88/