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

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

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

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

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

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

環境

macOS 10.14 Mojave

Unity2018.3.14f1

Unity Hub 2.1.0

アルゴリズムって？

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

エクスプラボ

アルゴリズムってなんやいね？　って時に読む記事【初心者向け】

https://ekulabo.com/whats-algorithm

初心者のうちからアルゴリズムを理解し、処理時間を意識していくと、超イケてるプログラミングが可能になります。慣れてる人は多分無意識のうちにやっていることなんですよね。

ノームソートについて

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

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

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

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

うん、ファンタジー。

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

ノームソートの仕組み

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

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

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

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

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

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

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

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

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

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

ノームソートの実装

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

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

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

SortBase.cs

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

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

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

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

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

実行結果

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

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

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

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

※追記

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

エクスプラボ

【Unity/C#】交換ソートのアルゴリズムを性能比較するのだ

https://ekulabo.com/algorithm-performance

交換ソートの性能比較を行いました。数字で比較すると、オーダーでの比較に現れない差異が見て取れて楽しいですね。

まとめ

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

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

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