初心者がpython３とpygameでソートアルゴリズムを可視化してみる【シェーカーソート】

初心者がpython３とpygameでソートアルゴリズムを可視化してみる【シェーカーソート】

シェーカーソート

シェーカーソートはバブルソートの改良版です。
バブルソートは、並びが良い場合（交換が少なくて済む場合）はソートが早いという特徴があります。
ということは、最悪のケースを考えてみたときに、逆側からバブルソートを行うと早くソートが終わるってことになります。
最悪のケースの逆は最高のケースででしょう、という前提でバブルソートを往復で行うことにより、交換回数を減らそうというものです。
実際比較はほぼすべてに対して行うので、アニメーションの処理回数的には変わらないですが、交換という部分で見ると処理は早くなっているはずです。

アルゴリズム

バブルソートを往復で行うだけですので、特に工夫もなく直感的に実装できます。

まんまですね。

所感

実装は当然のように簡単なアルゴリズムだけれども、効果はそれなりにあるかなぁと思いました。
アニメーションではわからないですが、交換回数は減ってるはずです。