Help us understand the problem. What is going on with this article?

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

はじめに

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

sort.gif

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

バブルソート

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

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

1_bubble_sort.gif

バブルソート実装例
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

コムソート

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

アルゴリズムは以下になります。
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/ソート

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした