Edited at

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

More than 1 year has passed since last update.


はじめに

ソートアルゴリズムの学習として、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/ソート