初心者がpython３とpygameでソートアルゴリズムを可視化してみる【シェルソート】
挿入ソートを改良したシェルソートをPythonで実装し、Pygameで可視化。刻み幅ごとにデータを整列し、全体が徐々に昇順へ近づいていく過程を確認します。
シェルソート
前回に引き続いて調子に乗って別のソートアルゴリズムも試してみました。
まぁありがちですが。。。
あちこち見れば書いてますが、シェルソートは挿入ソートを改良したものです。
挿入ソートは、整列済みに近いデータ列に対しては、割と早い特徴があります。
最悪に近いケース
最善に近いケース
原理を考えれば、そりゃそうですが、かなり違いますね。
なので、この最善に近いケースにデータを近づけながら挿入ソートしたら早くなるんじゃね？
って言うのが、シェルソートの基本的なアイデアです。
アルゴリズム
データをある刻み幅hでグループ分けします。
例えば、
| v = [ 3, 7, 1, 4, 10, 2, 8, 9, 5, 6 ] |
を h=4 で分割すると、
| v1 = [ 3, 10, 5 ] |
| v2 = [ 7, 2, 6 ] |
| v3 = [ 1, 8 ] |
| v4 = [ 4, 9 ] |
のグループに分けられます。
これをそれぞれ、ソートして元の順番でつなぎ合わせます。
①ソート
| v1 = [ 3, 5, 10 ] |
| v2 = [ 2, 6, 7 ] |
| v3 = [ 1, 8 ] |
| v4 = [ 4, 9 ] |
②繋ぎなおし
| v = [ 3, 2, 1, 4, 5, 6, 8, 9, 10, 7] |
なんとなく、昇順に近い並びで並んでいるのがわかります。
次は、刻み幅を h = 2 として同じことを行うと、もう少し完全な昇順に近づきます。
最後に、通常の挿入ソートを行う。という手順です。
python的には、以下のように書いてみました。
（初心者ですので、効率は悪いと思います。）
結果
データの比較、並び替えの処理のみ記録してゆき、アニメーションにしてみました。
初めはランダムだったデータがだんだん昇順に近づいていくのがわかると思います。
最後は、気持ちいい速さで整列されますね。
所感
シェルソートを実装して可視化してみました。
可視化の部分は、汚すぎてお見せできないので、後回しに(-_-;)
Shellソートの名前の由来は、Donald L. Shellが、1959年に発表したアルゴリズムであることに由来しているそうです。
アルゴリズムやソートについて、なにか突っ込みやコメントありましたら、気軽にお願いします。
さて、次は何やってみようかな？
へだば、まだね！
