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

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

シェーカーソートとは？

シェーカーソートとは、バブルソートを効率良くなるように改良したソートです。
バブルソートについて、理解が曖昧な方は下の記事で紹介していますので、御覧ください。

バブルソートとは？コードやアルゴリズムを初心者向けに解説

バブルソートは１方向のみのソートですが、シェーカーソートは交互に２方向でソートを行います。
下の動画を見て、シェーカーソートについて動画でイメージしてみてください。

いかがでしたか。
シェーカーソートを一言で言えば、前から後ろ、後ろから前、と順番にソートしていく整列アルゴリズムです。
これにより、１方向のバブソートよりも効率の良いソートを可能にします。

シェーカーソートは比較的理解しやすいソートですので、イメージしやすいと思います。
ソースコードを書く上で、アルゴリズムをイメージできていることは非常に重要ですので、動画を見ながら理解してくださいね。

シェーカーソートの計算量

シェーカーソートの計算量は「Ｏ（ｎ²）」であり、比較回数は「 n(n-1)/2 」です。
シェーカーソートは安定性のある整列アルゴリズムです。

Pythonコード

def shaker_sort(nums):
    beginning = 0
    ending = len(nums) - 1

    while beginning < ending:
        for i in range(beginning, ending):
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        ending -= 1

        for i in range(ending - 1, beginning - 1, -1):
            print(i)
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        beginning += 1

    return nums

上記がPythonを用いて作成した、シェーカーソートの関数です。
動画で理解しながら、ゆっくりとコードを眺め、自力でコードが書けるようにイメージを膨らませてください。

６〜９行目で、前方から後方までのソート
１１〜１５行目で、後方から前方までのソート
全体のwhileループで、「前方から後方」「後方から前方」のソートを更に繰り返しループさせ、全体のソートを可能にしています。

シェーカーソートの実行

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

def shaker_sort(nums):
    beginning = 0
    ending = len(nums) - 1

    while beginning < ending:
        for i in range(beginning, ending):
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        ending -= 1

        for i in range(ending - 1, beginning - 1, -1):
            print(i)
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        beginning += 1

    return nums


if __name__ == '__main__':
    nums = [65, 45, 66, 4, 89, 50, 24, 43, 99, 14]
    print(shaker_sort(nums))

【実行結果】
[4, 14, 24, 43, 45, 50, 65, 66, 89, 99]

実行結果から、
２１行目で宣言した[65, 45, 66, 4, 89, 50, 24, 43, 99, 14]のリストを昇順に上手くソートできていることがわかります。

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

超オススメのPC用品

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

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