> udemyで学習する

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

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

シェルソートとは?

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

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

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

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


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

1.一定間隔ごとに要素を比較して並べ替え
2.間隔を狭めて、1の操作を繰り返す
3.一定間隔が0になればソート完了

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

シェルソートの計算量

平均計算時間最悪計算時間最良計算時間
gap(間隔)によるO(n2O(n*log(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を用いて作成したシェルソートの関数です。

7〜10行目で、要素の比較、挿入を処理しています。
また、11行目で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]

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

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

超オススメのPC用品

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

外部モニターで2倍以上の効率化が見込めます!
安いものだと、たったの1万円前後なのでおすすめですよー!\(^o^)/

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です