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

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

![sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/cf32e4c3-04bf-0767-77e1-04fb57c4e0ea.gif)

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


# バブルソート
バブルソートのアルゴリズムは以下のような感じです。
>1. 配列の要素を最初から最後まで見ていき、順序が逆の要素があれば入れ替える
>2. 全ての要素の順序が正しくなるまで 1.を繰り返す.

![1_bubble_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/883b7528-faf6-2d22-7c9c-fad496380114.gif)

```csharp:バブルソート実装例

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方向にスキャンを行っていたところを、往復してスキャンするようにしたものです。

![2_shaker_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/72eecbe1-e74b-8fcf-6e65-45e73078c9de.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](https://qiita-image-store.s3.amazonaws.com/0/44288/0b53474f-7448-322f-33d9-9d44799485e4.gif)


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

![4_gnome_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/133639c1-a0ac-57f9-4bde-e9f31e4beed9.gif)


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

![5_selection_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/7111a984-d9d7-3e98-3db5-734fb1da5a92.gif)

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

![6_insertion_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/cf7945e7-ed0a-3629-6616-a8c9d234b5c6.gif)


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

![7_shell_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/47f7ad21-3e2a-1d9e-760e-75017f18649b.gif)

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

![8_quick_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/c3d2a2c3-2c79-0a1e-d753-e73346406be3.gif)

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

![9_bucket_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/e6e143b4-a139-b5a4-4d6f-a58cf949a7fc.gif)

![9B_bucket_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/e9d08b73-887a-221f-9515-274db690ecde.gif)

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

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

![10_radix_sort.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/05377b84-5f9e-ac90-1216-e2bf5dbb5431.gif)

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

![11_heap_sort_edit.gif](https://qiita-image-store.s3.amazonaws.com/0/44288/91b76d64-816b-0a53-d29f-9b1db21450dd.gif)

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

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

<img src = "https://qiita-image-store.s3.amazonaws.com/0/44288/2955b3da-ca94-9bbb-2547-72b3afdf86f8.gif">

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

# 参考URL
ソート - Wikipedia
https://ja.wikipedia.org/wiki/ソート