シェルソートとは？【アルゴリズム紹介・Pythonによる実行】

本記事はPythonのシェルソートについて、優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なシェルソートを一緒に学習しましょう！

シェルソートとは？

シェルソートは、挿入ソートの改良版です。
挿入ソートについて、理解が曖昧な方は下の記事紹介していますので、ぜひ御覧ください。

挿入ソートとは？【アルゴリズム紹介・Pythonによる実行】

挿入ソートは昇順を降順に並べ替える場合などのすべての要素をソートする必要がある場合、処理速度は非常に遅くなる欠点がりました。この欠点を解決した整列アルゴリズムがシェルソートです。
挿入ソートは隣接する値を比較しあって挿入を行うアルゴリズムのため、処理速度の低下が考えられました。そこで、予め間隔のある値を比較しあって挿入を行い、ある程度のソートが行われた上で挿入ソートを適用します。

下の動画でなんとなく理解ができると思います。

シェルソートは、英語で書くと「shell sort」と書き、「shell」とは「貝」という意味があります。
開いた貝がとじていくように、初めは間隔のある要素を比較しあい、少しずつ比較する間隔を狭めていくアルゴリズムです。

１．一定間隔ごとに要素を比較して並べ替え
２．間隔を狭めて、１の操作を繰り返す
３．一定間隔が０になればソート完了

「一定間隔」はコードを書く人によって分かれます。適当に「４」とか数字を決める人もいますし数学的に「一定間隔」を決める人もいます。
一般的には、「gap = n / 2（nは先頭要素）」という考え方が利用されます。

シェルソートの計算量

シェルソートの計算量は間隔によって変わります。
よって、シェルソートは安定性のない整列アルゴリズムです。

Pythonコード

def shell_sort(nums):
    gap = len(nums) // 2
    while gap > 0:
        for i in range(gap, len(nums)):
            tmp = nums[i]
            j = i
            while j >= gap and nums[j - gap] > tmp:
                nums[j] = nums[j - gap]
                j -= gap
            nums[j] = tmp
        gap //= 2
    return nums

上記がPythonを用いて作成したシェルソートの関数です。

７〜１０行目で、要素の比較、挿入を処理しています。
また、１１行目でforループから抜けるたびにgap（比較間隔）を狭める処理をしています。

シェルソートの実行例

上記で作成した関数を使用して、実際にシェルソートをPython環境で実行してみました。
下がそのコードと実行結果です。

def shell_sort(nums):
    gap = len(nums) // 2
    while gap > 0:
        for i in range(gap, len(nums)):
            tmp = nums[i]
            j = i
            while j >= gap and nums[j - gap] > tmp:
                nums[j] = nums[j - gap]
                j -= gap
            nums[j] = tmp
        gap //= 2
    return nums

if __name__ == '__main__':
    nums = [54, 32, 2, 76, 39, 47, 99, 15]
    print(shell_sort(nums))

【実行結果】
[2, 15, 32, 39, 47, 54, 76, 99]

実行結果から、
１５行目で宣言した[54, 32, 2, 76, 39, 47, 99, 15]のリストを昇順に上手くソートできていることが分かります。

ということで、本記事はシェルソートについて、Pythonのコードを使用しながら紹介しました。
最後まで読んでいただき、ありがとうございました＼(^o^)／

超オススメのPC用品

PCを操作する上で、トラックボールマウスが非常におすすめです！
僕も感動したこのマウスを、騙されたと思って使ってみてください！(^^)

外部モニターで２倍以上の効率化が見込めます！
安いものだと、たったの１万円前後なのでおすすめですよー！＼(^o^)／