Pythonでシェルソートの実装

シェルソート

シェルソートは，挿入ソートの特徴を生かし，さらに高速化したアルゴリズムになります．
基本的な動作は挿入ソートと同じで二つの数字の大小を比較をしていき，最終的にソートが完成されているというものです．
挿入ソートでは隣り合った要素の大小の比較でしたが，シェルソートでは無駄な比較をなるべく減らすために一定の間隔g毎の数字の大小の比較をしていきます.
ある間隔gが終わったらそれよりも小さな間隔でさらにソートしていき，最終的に間隔1の比較，つまり，挿入ソートを行うことで全体が完全にソートされることになります.
この間隔gの選び方は諸説あるらしいのですが，g_n+1= 3g_n+1に従って選ぶとある程度高速になるそうです．
つまり，今回は20個の配列で試しているのでg = {1,4,13}のように選ぶといいようですね.
本プログラムではgapという配列を利用して間隔を指定しているので，そこの部分を自分なりにアレンジしてみて試してみてください.

def make_gap(num_list):
    gap_num = 1
    gap = [1]
    while gap_num < len(num_list):
        gap_num = gap[-1]*3 + 1
        gap.append(gap_num)
    gap.pop()
    return gap

def n_gapsort(num_list, gap):
    sort_list = list(num_list)
    for i in range(gap,len(num_list)):
        target = sort_list[i]
        j = i - gap
        while j >= 0 and sort_list[j] > target:
            sort_list[j+gap], sort_list[j] = sort_list[j], target
            j -= gap
    return sorted_list

def shellsort(num_list):
    sort_list = list(num_list)
    gap = make_gap(num_list)
    for i in gap:
        sort_list = n_gapsort(sort_list,i)
    return sort_list

num_list = list(range(1,20))
shuffle(num_list)
sorted_list =  shellsort(num_list)
print(num_list)
print(sorted_list)