【Unity】ソートアルゴリズム12種を可視化してみた

はじめに

ソートアルゴリズムの学習として、12種のソートアルゴリズムを実装して可視化してみました。

sort.gif

Unityにはあまり関係がなさそうな話題ですが、Unity上で作ったのでUnityタグをつけます。

バブルソート

バブルソートのアルゴリズムは以下のような感じです。

  1. 配列の要素を最初から最後まで見ていき、順序が逆の要素があれば入れ替える
  2. 全ての要素の順序が正しくなるまで 1.を繰り返す.

1_bubble_sort.gif

バブルソート実装例

void BubbleSort(int[] a)
{
    bool isEnd = false;
    while (!isEnd)
    {
        bool loopSwap = false;
        for (int i = 0; i < a.Length - 1; i++)
        {
            if (a[i] < a[i + 1])
            {
                Swap(ref a[i], ref a[i + 1]);
                loopSwap = true;
            }
        }
        if (!loopSwap) // Swapが一度も実行されなかった場合はソート終了
        {
            isEnd = true;
        }
    }
}

シェーカーソート

シェーカーソートはバブルソートを改良したソートアルゴリズムです。
バブルソートでは1方向にスキャンを行っていたところを、往復してスキャンするようにしたものです。

2_shaker_sort.gif

コムソート

コムソートはバブルソートを改良したソートアルゴリズムです。

アルゴリズムは以下になります。
1. データ数n を 1.3 で割った整数部分を間隔 h とします。
2. i を 0 -> n-h-1 でfor文で回します。
3. i番目と i+h 番目を比べたときに順序が逆になっていた場合入れ替えます。
4. 3.が完了したら、h を 1.3 で割った整数部分を新たなhとして再び2.と3.を行います。
5. 4.が終了したときに h が 1になっていた場合、そこでソート完了です。

3_comb_sort.gif

ノームソート

  1. 配列の要素を順方向へ順番に見ていきます。
  2. 順序が逆になっている要素を見つけたらその要素をつかみます。
  3. つかんだ要素を一つ手前の要素と交換します。交換した後も順序が逆だったらさらに手前にずらす・・・という操作を繰り返します。
  4. ずらし終わったら、その位置から再び順方向へ要素を見ていきます。
  5. 配列の最後の要素まで到達したらソート完了です。

4_gnome_sort.gif

選択ソート

配列の要素を順番に見ていき、要素を最大値と入れ替えていくことで整列を行います

5_selection_sort.gif

挿入ソート

要素を適切な場所へ挿入することで整列を行います。

6_insertion_sort.gif

シェルソート

  1. 適当な間隔 h を決める
  2. 間隔 h をあけて取り出したデータ列に挿入ソートを適用する
  3. 間隔 h を狭めて、2.を適用する操作を繰り返す h=1 になったら、最後に挿入ソートを適用して終了

7_shell_sort.gif

クイックソート

大雑把なアルゴリズムは以下にようになります。
1. 配列からピボットとして要素一つ選び、ピボットより左側のすべての要素は小さく、右側はピボットより大きくなるように互いを入れ替えていきます。
2. ピボットの左側から新たなピボットを選び、1.を行います。 ピボットの右側からも新たなピボットを選び同様の操作を行いソートします。
3. これらを繰り返すことでソートを行います。

8_quick_sort.gif

バケットソート

  1. 配列の要素の値をインデックスとして直接バケツへ移動
  2. バケツの手前から順番に配列に戻してソート完了

9_bucket_sort.gif

9B_bucket_sort.gif

基数ソート

要素の1の位でバケットソートをし、次に10の位でバケットソート、その次は100の位で...
といった感じに、桁に対応する数字でバケツソートを行うソートアルゴリズムです。

メモリ使用量がバケツソートよりも少なくて済みます。

10_radix_sort.gif

ヒープソート

  1. 配列をヒープ構造にして、根元のノードの数字を取り出す。
  2. 再びヒープ構造にして1.を行う
  3. 全ての数字を取り出したらソート完了

11_heap_sort_edit.gif

ヒープ構造の特徴は以下になります。
1. 二分木の根には必ず最大値がくる。
2. 二分木の各親子関係の親ノードには必ず最大値がくる

マージソート

  1. 配列を2つに分割する
  2. 各々をソートする
  3. 二つのソートされた配列をマージする

おわりに

筆者はソートアルゴリズムについては疎いため、本記事には誤りがある可能性があります。
誤りを見つけた場合は教えていただけると助かります。

参考URL

ソート - Wikipedia
https://ja.wikipedia.org/wiki/ソート