🐺

シェルソートを実装してみる

に公開
Python 3
sort
アルゴリズム
shellsort
tech

アドベントカレンダー（自称）： vol.1

皆さん、こんにちは。yumyum116 です。SWE転職を目指す者です。
アドベントカレンダーに便乗して、1日1記事投稿に挑戦するとともに、執筆活動の習慣化にも挑戦してみます。

記念すべき初稿は、概念は理解できても、プログラムに起こすことが苦手な自分が綴る、概念を実装してみたシリーズです。
自分と同じようなところで躓いている方、プログラミング初学者の方の参考になれば嬉しいです。

今回は、効率的なソートアルゴリズムの一つとして知られる、シェルソートを複数パターン実装してみます。

1. シェルソートとは

シェルソートとは、基本的なソートアルゴリズムの一つである、挿入ソートを改良したアルゴリズムです。挿入ソートは、配列の隣り合う要素同士を比較します。一方、シェルソートは任意の間隔（gap）で離れた要素同士を挿入ソートする操作を、gapを狭めながら繰り返すアルゴリズムです。最終的には、gap = 1 の挿入ソートになります。

最終的に挿入ソートになるのであれば、シェルソートは挿入ソートの何を改良したのでしょうか。

少し寄り道をします。

アルゴリズムのパフォーマンスを評価する指標として用いられるものに、時間計算量と空間計算量という概念があります。ここでは、計算量の概念の説明は割愛しますが、これらの計算量を評価する指標は、一般にO記法と呼ばれる記法で表現されます。

入力サイズ n の場合、挿入ソートでは時間計算量が O(n^2) ~ O(n) になります。
シェルソートの場合は、O(n^{1.3}) ~ O(nlogn) ほどになります。
時間計算量の導出が気になる方は、アルゴリズムイントロダクションのような書籍をご覧ください。
この時間計算量の差は、入力サイズが1,000を超えるくらいから、実感できるようになります。

具体的な問題をベースに考えてみましょう。

エンジニア10,000人のプログラミングスコアが整数で与えられます。スコアはランダムに並んでいます。スコアが近い人同士をペアにするプログラムを作成してください。

この問題を、
　①スコア順にソートし、
　②隣り合う要素を元にペアを形成する
アプローチで解くことを考えます。

①のアプローチとして挿入ソートを用いる場合、最悪の場合では時間計算量が O(n^2) となるため、今回の問題のケースでは最悪 1億回 操作する可能性もあります。

シェルソートを用いる場合は、平均計算量は O(n^{1.3}) ~ O(nlogn) ほどに改善します。

ここまでお読みいただいた方であれば、もうお気づきかもしれませんが、シェルソートは、とくに大規模な入力サイズにおける挿入ソートの非効率性を改良したアルゴリズムです。

2. シェルソートのアプローチ

シェルソートのアプローチの説明に入る前に、挿入ソートのアプローチを整理します。

挿入ソートのアプローチ

  1. i 回目に A_i を合計 n-1 回挿入する
  2. A_i の値を変数 x に保存する
  3. A_j > x である間、A_j を右にずらす
  4. A_{j+1} に x を代入する

挿入ソートは、シェルソートにおける gap = 1 の場合です。
したがって、挿入ソートのアプローチを汎用化したものがシェルソートのアプローチになります。

具体的には、次のように書き換えることができます。

シェルソートのアプローチ

  1. i 回目に A_i を合計 n-1 回挿入する
  2. A_i の値を変数 x に保存する
  3. A_j > x である間、A_j をgap分ずらす
  4. A_{j+g} に x を代入する
  5. 2~4をgap = 1になるまで繰り返す

さて、前置きが長くなりましたが、次はこのアプローチを実装してみます。

3. シェルソートの実装

パターン１：gap の配列が標準入力で与えられる場合

shell_sort_ver1.py
def insertion_sort(array, n, gap):
    for i in range(gap, n):

        # A[i]の値を変数 x に保存する
        x = array[i]

        j = i - gap

        while j >= 0 and array[j] > x:
            # A[j] を gap 分ずらす
            array[j + gap] = array[j]
            j -= gap

        # A[j + g]に x を代入する
        array[j + gap] = x

def shell_sort(array, n, gap_sequence):
    for gap in gap_sequence:
        insertion_sort(array, n, gap)

ここで、n は配列 array の要素数を表します。

パターン2：gap の配列をアルゴリズムの中で生成する場合

shell_sort_ver2.py
def insertion_sort(array, n, gap):
    for i in range(gap, n):

        # A[i]の値を変数 x に保存する
        x = array[i]

        j = i - gap

        while j >= 0 and array[j] > x:
            # A[j] を gap 分ずらす
            array[j + gap] = array[j]
            j -= gap

        # A[j + g]に x を代入する
        array[j + gap] = x

def shell_sort(array, n):
    # 間隔 gap を格納する配列を作成する
    gap_sequence = []

    # 要素数 n を２で割った商の整数値を間隔の初期値として、gap に代入する
    gap = n // 2

    while gap > 0:
        gap_sequence.append(gap)
        # gap をどんどん小さくする
        gap //= 2
    if not gap_sequence:
        gap_sequence.append(1)

    for gap in gap_sequence:
        insertion_sort(array, n, gap)

これで、シェルソートの実装は終わりです。

小話ですが、シェルソートの間隔gapの最適解は未解決らしいです。
興味のある方は、色々なデータセットにおける最適解を探してみるのも面白いと思います。

記事内に不適切な表現や、誤謬がある場合は修正します。
その際は、ご連絡いただけますと助かります。

それでは、また。

Discussion