初心者がpython３とpygameでソートアルゴリズムを可視化してみる【シェーカーソート】
バブルソートを左右から往復させるシェーカーソートをPythonで実装。アルゴリズムの考え方と、交換回数を減らす仕組みをPygameのアニメーションで確認します。
シェーカーソート
シェーカーソートはバブルソートの改良版です。
バブルソートは、並びが良い場合（交換が少なくて済む場合）はソートが早いという特徴があります。
ということは、最悪のケースを考えてみたときに、逆側からバブルソートを行うと早くソートが終わるってことになります。
最悪のケースの逆は最高のケースででしょう、という前提でバブルソートを往復で行うことにより、交換回数を減らそうというものです。
実際比較はほぼすべてに対して行うので、アニメーションの処理回数的には変わらないですが、交換という部分で見ると処理は早くなっているはずです。
アルゴリズム
バブルソートを往復で行うだけですので、特に工夫もなく直感的に実装できます。
まんまですね。
所感
実装は当然のように簡単なアルゴリズムだけれども、効果はそれなりにあるかなぁと思いました。
アニメーションではわからないですが、交換回数は減ってるはずです。
