はじめに

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

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

バブルソート

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

配列の要素を最初から最後まで見ていき、順序が逆の要素があれば入れ替える

全ての要素の順序が正しくなるまで 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になっていた場合、そこでソート完了です。

ノームソート

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

選択ソート

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

挿入ソート

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

シェルソート

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

クイックソート

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