初心者がpython３とpygameでソートアルゴリズムを可視化してみる【シェルソート】
シェルソート
前回に引き続いて調子に乗って別のソートアルゴリズムも試してみました。
まぁありがちですが。。。
あちこち見れば書いてますが、シェルソートは挿入ソートを改良したものです。
挿入ソートは、整列済みに近いデータ列に対しては、割と早い特徴があります。
最悪に近いケース
youtu.be
最善に近いケース
youtu.be
原理を考えれば、そりゃそうですが、かなり違いますね。
なので、この最善に近いケースにデータを近づけながら挿入ソートしたら早くなるんじゃね？
って言うのが、シェルソートの基本的なアイデアです。
アルゴリズム
データをある刻み幅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的には、以下のように書いてみました。
（初心者ですので、効率は悪いと思います。）
結果
データの比較、並び替えの処理のみ記録してゆき、アニメーションにしてみました。
初めはランダムだったデータがだんだん昇順に近づいていくのがわかると思います。
最後は、気持ちいい速さで整列されますね。
