スクリプトアルゴリズム、意識してますか?(挨拶)今回は交換ソートの一種であるノームソートをC#で実装します。ゲーマーにとってはおなじみの地の精霊ノームが植木鉢を並べ換える様子から名前がついたそうです。メガテニストには「精霊ノーム」の方が分かりやすいかもしれませんね。ITワードはたまにファンタジーネーミングがあるのでやめられません。今回もUnityを使いますが、「Array.Sort()やList<T>.Sort()を使え」は禁止ワードです。2.1.0アルゴリズムって?アルゴリズムとは何かという話は別記事で書いたのでそちらをご覧くださいな。時に読む記事【初心者向け】https://ekulabo.com/whats-algorithm初心者のうちからアルゴリズムを理解し、処理時間を意識していくと、超イケてるプログラミングが可能になります。慣れてる人は多分無意識のうちにやっていることなんですよね。ノームソートについてノームソートは挿入ソートに似たアルゴリズムですが、交換によって要素をずらしていきます。ノームは一列に並んだ植木鉢をひとつひとつ確かめていきます。今自分の目の前にある植木鉢とひとつ前の植木鉢を比較して、目の前の植木鉢の花が小さければ、ひとつ前の植木鉢と場所を交換します。交換を行なったら、また目の前の植木鉢と、そのひとつ前の植木鉢を交換して......といったように交換を進めます。列の後ろの方に小さな花の植木鉢があれば、どんどん前まで持っていきます。ノームが最後の植木鉢までたどり着いて、交換が発生しなかったら並べ替えは終了です。最悪計算時間は\(O(n^2)\)ですが、実験的には挿入ソートと同じくらいの速度だそうで。これもあとでまとめて性能比較してみましょ。ノームソートの仕組み入れ替えの仕組みを簡単に説明します。4の数値が格納されているとします。この配列について、左から昇順で並べ替えることを考えます。配列の初期状態まず、ノームはインデックス0からスタートします。この時点では前の配列要素がないので次に進みます。今いるインデックスは0現在はインデックス1にいます。前の配列要素と比較を行い、順序が逆なら入れ替えます。交換を行なったので、ノームは前に移動しました。同じように、前の配列要素がないので次に移動します。今いるインデックスは0インデックス1に移動しました。前の要素と比較を行いますが、順序が正しいので次の配列要素に移動します。今いるインデックスは1『1』と『5』の比較インデックス2に移動しました。こちらも前の要素と比較を行います。順序が正しいので次の配列要素に移動します。今いるインデックスは2『5』と『8』の比較インデックス3に移動しました。前の要素と比較を行い、順番が逆になっているので交換を行います。交換を行なったので、現在位置がインデックス2になりました。前の要素と比較を行い、順序が逆なので交換を行います。『5』と『4』の交換あとは配列の最後の要素までノームが歩いていけば処理は終了です。ノームソートの実装これをC#で実装したコードがこちら。コメントを書いたので長くなってます。あとWikipediaに書かれているコードを思いっきり参考にしてます。今回作成したスクリプトは、配列の中身を表示するためのメソッドを用意して継承しています。Gist.こちらがノームソートの本体です。Gist.配列の数値は特に意味はありません。ランダムなら何でも大丈夫です。他の交換ソートと違って、ループが入れ子になっていないのが特徴です。現在のノームの位置を使って比較・交換を進めています。インデックスが減った時に、配列の最小インデックスになった場合は比較・交換を行わずに次のインデックスに進めます。整形すると以下のようになります。Whileループ1回ごとに配列の中身を出力するようにコーディングしていますが、途中の様子は出力結果から省きました。70行超えちゃうので。Gist.ちゃんと並び変わってますね。この配列だと後ろの方にいる13や14が結構ネックなので、外側のループ単位で見れば毎回前に移動できるのはでかいです。バブルソートでは、毎回不要な比較が行われてしまうので速くなっていると思います。「思います」なのはまだ性能比較してないからなので、そのうち交換ソートで性能比較大会をやってみたいと思います。他の交換ソートのアルゴリズムと性能比較を行ったので、よかったらこちらもぜひ。バブルソートよりも速くなっていました。エクスプラボ【Unity/C#】交換ソートのアルゴリズムを性能比較するのだhttps://ekulabo.com/algorithm-performance交換ソートの性能比較を行いました。数字で比較すると、オーダーでの比較に現れない差異が見て取れて楽しいですね。まとめ今回はノームソートのアルゴリズムをC#で実装しました。簡単に実装できるのでぜひ試してみてくださいな。実装の間、悪魔に肉体を乗っ取られぬようお気をつけて......。ゲーム開発の攻略チャートを作りました!「ゲームを作ってみたいけど、何から手を付けていいか分からない!」そんなお悩みをお持ちの方向けに、todoがアプリをリリースした経験を中心に、ゲーム作りの手順や考慮すべき点をまとめたe-bookを作成しました。ゲーム作りはそれ自体がゲームのように楽しいプロセスなので、「攻略チャート」と名付けています。投稿一覧Unityを使ってアプリを作ったり、Assetを作ったりしてる個人開発者。Unity全般ネタとAsset開発の情報を扱っています。Asset開発は日本語の情報が少ないのよね。ことで些細なネタでも情報を蓄積するのが目的です。2019.08.24シェーカーソートについての説明とC#による実装を紹介しています。バブルソートの改良型としてこれも有名。2019.08.28交換ソートのひとつであるクイックソートは、ソートするならクイックソートで、と言われるくらいには速いソート方法です。2019.08.29交換ソートの性能比較を行いました。数字で比較すると、オーダーでの比較に現れない差異が見て取れて楽しいですね。2019.08.27交換ソートのひとつであるコムソートは、実装が単純なのに速度が出る素敵ソート。ポイントは伸縮率の1.3という数字です。コメントをキャンセルメールアドレスが公開されることはありません。コメントデータの処理方法の詳細はこちらをご覧ください。todoUnityのアセットを作ったり、スマホ向けのアプリを作っています。このブログではUnity初心者に向けたチュートリアルやテクニックを放出しています。詳しいプロフィールはこちら。お仕事の相談や現在提供中のサービスについては、こちらの『サービス内容』のページをご覧ください。Explorers_todoオンライントレーニングのサイトをオープン!エクスプラボを運営しているtodoが、より集中的にゲーム作りについて学べるオンライントレーニングのサイトをオープンしました。エクスプラボのトレーニングルーム』です。勉強したことの進捗も表示できるようになっているので、どれだけ頑張ったのかが分かるようになっています。ゲーム開発の攻略チャート』というe-bookをプレゼントしています。メルマガではゲーム開発のテクニックを中心に役立つ情報をお届けします。詳しくはこちら!お仕事の依頼はこちら!ゲーム開発のサポートも可能!エクスプラボではゲーム開発のサポートのサービスも行なっています。いう場合にオススメのプランです。普通に開発依頼をいただいてもOKです。【Unity】ポストプロセシングを使って簡単にプロっぽいゲーム画面を作るゲームの作り方を学べるオンライン講座のサイトをオープンしました!【ゲーム開発】ゲーム開発者こそ体を動かしてアイディアを出すべきRANKING【Unity】Mathfの切り上げ、切り捨て、偶数丸め。使い分けが大事よねMathf【Unity】ゲームといえばランダム要素。(12)作ったアプリ空とにゃんこと風船と癒し系縦スクロール避けゲーの『空とにゃんこと風船と』(TODOWORKS名義でリリース)気軽に遊べるスマートフォン向けアプリです。ボクセルアートで彩られるどこかレトロ、でも新しい世界で癒されてみませんか?ぼく、猫ですって!タップ系RPG『ぼく、猫ですって!』(TODOWORKS名義でリリース)気軽に遊べるスマホRPG。