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

はじめに

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

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

バブルソート

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

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

バブルソート実装例

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

シェーカーソート

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

コムソート

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

アルゴリズムは以下になります。

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になっていた場合、そこでソート完了です。

ノームソート

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

選択ソート

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

挿入ソート

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

シェルソート

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

クイックソート

大雑把なアルゴリズムは以下にようになります。

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

バケットソート

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

基数ソート

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

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

ヒープソート

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

ヒープ構造の特徴は以下になります。

1. 二分木の根には必ず最大値がくる。
2. 二分木の各親子関係の親ノードには必ず最大値がくる

マージソート

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

おわりに

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

参考URL

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