シェルソート

シェルソートのやり方がよく分からなかったので下記で学習しました。
（ありがとうございます）

def insertion_sort(A, n, h):
    # アルゴリズムが正しく実装されていることを確認するために導入するカウンタ変数、ソート処理には関係がないことに注意
    num_of_move = 0

    for i in range(h,n):
        # A[i] を、整列済みの A[i-ah], ..., A[i-2h], A[i-h] の適切な位置に挿入する
        # 実装の都合上、A[i] の値が上書きされてしまうことがあるので、予め A[i] の値をコピーしておく 
        x = A[i]
        # A[i] の適切な挿入位置を表す変数 j を用意
        j = i - h

        # A[i] の適切な挿入位置が見つかるまで、A[i] より大きい要素を後ろにずらしていく
        while j >= 0 and A[j] > x:
            A[j+h] = A[j]
            j -= h
            num_of_move += 1
        
        # A[i] を挿入
        A[j+h] = x
    print(num_of_move)
    
def shell_sort(A, n):
    H = list(map(int,input().split()))
    
    for h in H:
        insertion_sort(A, n, h)
        
n = int(input())
A = list(map(int,input().split()))
k = int(input())
shell_sort(A,n)

基本的には、前に学習した挿入ソートを距離間隔のループの中で回していくだけなのだが、
学習したサイトでは、きれいに２つに分けられていた。８要素を４つにきれいに分けることができるのでグループにわけやすい。

しかし、こちらのケースだとどうだろうか。
7,6,10,2,5,4,8,3,9,1　この１０個の要素において、
最初の間隔が４でグループを作るケース。

この場合、
７と、４つ先にある５、次の４つ先が９
同じように
6と、４つ先にある４、次の４つ先が１
10、４つ先が8その先はないので終わり
２と、４つ先にある３、その先はないので終わり
ということになる。

その後、理屈では、
７，５，９の場合、5だけ７の前に入れ替えることになる。

A[i] の適切な挿入位置が見つかるまで、
A[i] より大きい要素を後ろにずらしていくというところが
難しい。
要するに、グループの中で、4つ飛びに要素を取得して比較するということを
繰り返しやっているということ。