pythonでソートアルゴリズム -シェルソート

はじめに

プログラミング初心者がソートアルゴリズムを自分なりに理解し、コーディングしてみたものの忘備録になります。
間違いもあるかもしれませんがご了承ください＆ご指摘いただけると助かります…。
ここでは、シェルソートを扱います。
参考にした本と記事はこちら
→https://www.codereading.com/algo_and_ds/algo/
→https://book.impress.co.jp/books/1118101057

シェルソート

シェルソートは挿入ソートをさらに効率化したものです。
一定間隔の要素ごとにソートを行い、間隔を狭めていくことで全体をソートしていきます。
あらかじめ配列の頭のほうに小さい数字が集まるので、挿入できた時点で終了する挿入ソートによって効率化が図れます。

手順

下手に私の書いた手順を見るより、この動画を見るほうが手っ取り早いです(クリックで見れます)。

この動画シリーズ、他のソートのものも存在するのですが、踊ってるを見るのが楽しくて好きです。

比較回数

最大値

間隔の取り方によって変わります(たぶん)。
もし間隔を3で一度挿入ソートし、その後間隔1で挿入ソートを行う場合、2回目のソートは3個先は小さい値が入っていることがわかっており、最悪2回の比較で済むはずなので、最悪の値は

\frac{1}{2} * \frac{1}{3}n(\frac{1}{3}n-1) * 3 + 2(n-2) + 1

・・・？
きちんと考えられていないので違う気がします。またほかの考えが浮かんだら追記します…。

プログラム

shell_sort.py

a = [4,6,1,2,3,8,5]

gap = len(a) // 2

while gap > 0:
    for i in range(gap, len(a)):
        j = i
        # gapの間隔で挿入ソートする
        # gap間隔で比べるし、gap下の値が0以上じゃないといけない
        while j-gap >= 0 and a[j] < a[j-gap]:
            a[j], a[j-gap] = a[j-gap], a[j]
            j -= gap

    # 一通りソートしたらgapを半分にしてもう一度ソートする
    gap //= 2

print(a)

計算量

forとwhileで2重になっていますが、配列の長さ分回るわけではないので、計算量が少し変わってきます。
計算量も間隔の取り方によって変わりますが、平均O(n^1.25)らしいです(受け売り)。

#おわりに
シェルソートについてまとめました。
挿入ソートを最初に勘違いしていたため、シェルソートで？？？になりましたが、動画をみたらなるほどねとなりました。
やはり動いているものはわかりやすいですね。