【Unity/C#】精霊が並び替えるノームソートのアルゴリズムを実装!

【Unity/C#】精霊が並び替えるノームソートのアルゴリズムを実装!

アルゴリズム、意識してますか?(挨拶)

今回は交換ソートの一種であるノームソートをC#で実装します。

ゲーマーにとってはおなじみの地の精霊ノームが植木鉢を並べ換える様子から名前がついたそうです。メガテニストには「精霊ノーム」の方が分かりやすいかもしれませんね。

ITワードはたまにファンタジーネーミングがあるのでやめられません。

今回もUnityを使いますが、「Array.Sort()やList<T>.Sort()を使え」は禁止ワードです。もしそんなことを言うのなら、オレサマ オマエ マルカジリ。

 

環境

macOS 10.14 Mojave

Unity2018.3.14f1

Unity Hub 2.1.0

アルゴリズムって?

アルゴリズムとは何かという話は別記事で書いたのでそちらをご覧くださいな。

ノームソートについて

ノームソートは挿入ソートに似たアルゴリズムですが、交換によって要素をずらしていきます。

ノームは一列に並んだ植木鉢をひとつひとつ確かめていきます。今自分の目の前にある植木鉢とひとつ前の植木鉢を比較して、目の前の植木鉢の花が小さければ、ひとつ前の植木鉢と場所を交換します。交換を行なったら、また目の前の植木鉢と、そのひとつ前の植木鉢を交換して……といったように交換を進めます。

列の後ろの方に小さな花の植木鉢があれば、どんどん前まで持っていきます。

ノームが最後の植木鉢までたどり着いて、交換が発生しなかったら並べ替えは終了です。

うん、ファンタジー。

最悪計算時間は\(O(n^2)\)ですが、実験的には挿入ソートと同じくらいの速度だそうで。これもあとでまとめて性能比較してみましょ。

ノームソートの仕組み

入れ替えの仕組みを簡単に説明します。

いま、以下のように大きさが4の配列があり、インデックスの小さな方から5, 1, 8, 4の数値が格納されているとします。この配列について、左から昇順で並べ替えることを考えます。

 

配列の初期状態
配列の初期状態

 

まず、ノームはインデックス0からスタートします。この時点では前の配列要素がないので次に進みます。

今いるインデックスは0
今いるインデックスは0

 

現在はインデックス1にいます。前の配列要素と比較を行い、順序が逆なら入れ替えます。

今いるインデックスは1
今いるインデックスは1
『5』と『1』の比較
『5』と『1』の比較
『5』と『1』の交換
『5』と『1』の交換

 

交換を行なったので、ノームは前に移動しました。同じように、前の配列要素がないので次に移動します。

今いるインデックスは0
今いるインデックスは0

 

インデックス1に移動しました。前の要素と比較を行いますが、順序が正しいので次の配列要素に移動します。

今いるインデックスは1
今いるインデックスは1

 

『1』と『5』の比較
『1』と『5』の比較

 

インデックス2に移動しました。こちらも前の要素と比較を行います。順序が正しいので次の配列要素に移動します。

今いるインデックスは2
今いるインデックスは2

 

『5』と『8』の比較
『5』と『8』の比較

 

インデックス3に移動しました。前の要素と比較を行い、順番が逆になっているので交換を行います。

今いるインデックスは3
今いるインデックスは3

 

『8』と『4』の比較
『8』と『4』の比較

 

『8』と『4』の交換
『8』と『4』の交換

 

交換を行なったので、現在位置がインデックス2になりました。前の要素と比較を行い、順序が逆なので交換を行います。

今いるインデックスは2
今いるインデックスは2

 

『5』と『4』の比較
『5』と『4』の比較

 

『5』と『4』の交換
『5』と『4』の交換

 

あとは配列の最後の要素までノームが歩いていけば処理は終了です。

ノームソートの実装

これをC#で実装したコードがこちら。みっちりコメントを書いたので長くなってます。

あとWikipediaに書かれているコードを思いっきり参考にしてます。すみません。

 

今回作成したスクリプトは、配列の中身を表示するためのメソッドを用意して継承しています。

SortBase.cs

 

こちらがノームソートの本体です。

 

配列の数値は特に意味はありません。ランダムなら何でも大丈夫です。

他の交換ソートと違って、ループが入れ子になっていないのが特徴です。現在のノームの位置を使って比較・交換を進めています。

インデックスが減った時に、配列の最小インデックスになった場合は比較・交換を行わずに次のインデックスに進めます。

このスクリプトをアタッチしてゲームを実行すると、コンソールに処理結果が出てきます。

実行結果

出力結果を整形すると以下のようになります。Whileループ1回ごとに配列の中身を出力するようにコーディングしていますが、途中の様子は出力結果から省きました。70行超えちゃうので。

ちゃんと並び変わってますね。よかった。

この配列だと後ろの方にいる13や14が結構ネックなので、外側のループ単位で見れば毎回前に移動できるのはでかいです。バブルソートでは、毎回不要な比較が行われてしまうので速くなっていると思います。

「思います」なのはまだ性能比較してないからなので、そのうち交換ソートで性能比較大会をやってみたいと思います。

 

※追記

他の交換ソートのアルゴリズムと性能比較を行ったので、よかったらこちらもぜひ。ちゃんとバブルソートよりも速くなっていました。

まとめ

今回はノームソートのアルゴリズムをC#で実装しました。

簡単に実装できるのでぜひ試してみてくださいな。

実装の間、悪魔に肉体を乗っ取られぬようお気をつけて……。

アプリ公開までの攻略チャートを作りました!

CTA-IMAGE

「スマホ向けのアプリを作ってみたいけど、何から手を付けていいか分からない!」


そんなお悩みをお持ちの方向けに、todoがアプリをリリースした経験から手順や考慮すべき点をまとめたe-bookを作成しました。ゲーム作りはそれ自体がゲームのように楽しいプロセスなので、「攻略チャート」と名付けています。


アプリをリリースする観点から書いているので各アプリストア向けの作業が入っていますが、企画、設計、開発、テスト部分については他のプラットフォームでも使える知識が満載です。


無料で入手できるのでぜひお早めにゲットして、開発をブーストさせてください!