スクリプトアルゴリズム、意識してますか?(挨拶)アルゴリズムの例を考えるときにはまずソートから、という黄金律に従ってソートのアルゴリズムを片っ端からC#で実装していきます。今回はコムソートのアルゴリズムをC#で実装します。コム(comb)は櫛を意味する英単語。コームと呼んだりする人もいます。Unityを使うならArray.Sort()やList<T>.Sort()を......というツッコミが毎回入りそうでビクビクしているのですが、目的はアルゴリズムを体験することなので目を瞑っていただきとうございます。2.1.0アルゴリズムって?アルゴリズムとは何かという話は別記事で書いたのでそちらをご覧くださいな。時に読む記事【初心者向け】https://ekulabo.com/whats-algorithm初心者のうちからアルゴリズムを理解し、処理時間を意識していくと、超イケてるプログラミングが可能になります。慣れてる人は多分無意識のうちにやっていることなんですよね。コムソートについてコムソートはバブルソートの改良型で、適当な間隔を定義して、その要素同士で比較を行なっていきます。間隔5で要素を比較して、次に間隔4で比較して......といったように、最初に間隔を決めてから、徐々にその間隔を狭めていきます。この間隔の決め方ですが、1.3で割って狭めていくとちょうど良いようです。元々の論文でも実験の結果から1.3が導き出されたみたい。この値を変えて実験してらっしゃる方がいたのでこちらも勉強になります。JavaScripthttp://www13.plala.or.jp/beni/combsort2_js.htmlなぜ比較する要素を離れたインデックス同士にしているかというと、例えば昇順に配列要素を並べ替えたい場合に、インデックスの大きな要素に小さい値が入っていると、それを前の方に持ってくるのに時間がかかってしまうためです。バブルソートの場合は大きな値は1回のループで奥まで持っていけますが、逆に小さな値は1つしか動かせないので、それだけで1ループ必要になります。ループの中では値の比較が行われ続けているので、これはちょっと時間がかかります。これを解消するため、コムソートでは離れた要素の比較・交換を行い、隣り合う要素の比較・交換の回数を減らせるようになっています。n)\)となるため、バブルソートより高速にソートすることができます。バブルソートについてはこちらの記事をご覧ください。交換ソートのアルゴリズムhttps://ekulabo.com/algorithm-bubble-sortバブルソートについての説明とC#による実装を紹介しています。一度は触れるアルゴリズムよね。コムソートの仕組み入れ替えの仕組みを簡単に説明します。6の数値が格納されているとします。この配列について、左から昇順で並べ替えることを考えます。配列の初期状態まずはじめに、要素の比較・交換を行う間隔(h)を決めます。配列の大きさは8なので、1.3で割って、小数点以下を切り捨てると6になります。この間隔6を使って、左端から確認していきます。インデックス0の『5』から6離れた要素はインデックス6の『3』です。こちらを比較しましょう。『3』の方が手前にいて欲しいので、『5』と交換します。次にインデックスを増やして『1』と『6』を比較します。こちらは『1』の方が手前にいるのでそのままで大丈夫そうですね。続いてインデックス2から6離れた要素......といきたいところですが、OutOfRange(範囲外)なので、このループは終了させなければなりません。ループが終了したら、hの値を再計算します。hは6だったので、1.3で割って、小数点以下を切り捨てると4になります。次は間隔4で比較・交換を行なっていきます。インデックス0の『3』とインデックス4の『7』を比較すると、どうやら並びは正しいようです。続いて『1』と『2』の比較です。こちらも交換は発生しません。『8』と『5』の比較です。『8』と『5』の比較こちらは交換が発生し、『5』が前に送られます。『4』と『6』の比較では交換は発生しません。これでこのループは終了です。『4』と『6』の比較h=4だったので1.3で割って小数点以下を切り捨ててh=3で確認します。このループでは『5』と『2』の交換、『7』と『6』の交換が発生します。『7』と『6』の交換h=3だったので1.3で割って小数点以下を切り捨ててh=2で確認します。このループでは『3』と『2』の交換が発生します。次はh=1になりますが、ここからはループ終了後に1.3で割らず、交換が発生しなくなるまでループを回します。隣り合う要素の比較・交換なので、ここからはバブルソートと同じですね。残りの要素の交換ループの中で交換が発生しなかったら処理終了です。コムソートの実装これをC#で実装したコードがこちら。コメントを書いたので長くなってます。あと例のごとくWikipediaに書かれているCのコードを思いっきり参考にしてます。今回作成したスクリプトは、配列の中身を表示するためのメソッドを用意して継承しています。Gist.こちらがコムソートの本体です。Gist.配列の数値は特に意味はありません。ランダムなら何でも大丈夫です。バブルソートと同じように外側のループと内側のループが存在しています。こちらでは外側のループの実行回数が確定でないため、Whileループを使って処理が終了するまで回しています。Whileループの開始時に間隔を表すhを計算しています。Mathf.FloorToIntは小数点以下切り捨ての処理です。内側のforループの処理は単純で、要素同士の比較を行い、順番が違っていれば入れ替えを行います。範囲外の要素へのアクセスを防ぐため、終了条件にhを使っています。整形すると以下のようになります。Gist.並べ替えがちゃんとできていました。バブルソートのように毎回値が確定するわけではないため、交換が発生しないことを確かめるループが入るのはやむなしです。処理時間については要素を増やして他のソートとも比較してみたいですね。まとめ今回はコムソートのアルゴリズムをC#で実装しました。n)\)となるだけあって、スムーズにソートされてる感じがします(主観)実装が単純で速さを出せる点がメリットですね。他の交換ソートのアルゴリズムと性能比較を行ったので、よかったらこちらもぜひ。思ったよりすごかったです。エクスプラボ【Unity/C#】交換ソートのアルゴリズムを性能比較するのだhttps://ekulabo.com/algorithm-performance交換ソートの性能比較を行いました。数字で比較すると、オーダーでの比較に現れない差異が見て取れて楽しいですね。ゲーム開発の攻略チャートを作りました!「ゲームを作ってみたいけど、何から手を付けていいか分からない!」そんなお悩みをお持ちの方向けに、todoがアプリをリリースした経験を中心に、ゲーム作りの手順や考慮すべき点をまとめたe-bookを作成しました。ゲーム作りはそれ自体がゲームのように楽しいプロセスなので、「攻略チャート」と名付けています。投稿一覧Unityを使ってアプリを作ったり、Assetを作ったりしてる個人開発者。Unity全般ネタとAsset開発の情報を扱っています。Asset開発は日本語の情報が少ないのよね。ことで些細なネタでも情報を蓄積するのが目的です。2019.08.29交換ソートの性能比較を行いました。数字で比較すると、オーダーでの比較に現れない差異が見て取れて楽しいですね。2019.08.23バブルソートについての説明とC#による実装を紹介しています。一度は触れるアルゴリズムよね。2019.08.29挿入ソートは配列の要素をずらして移動させるソート方法。リアルな世界で本棚を整理するときのことを思い浮かべたら分かりやすいかもしれません。2019.08.30ソートアルゴリズムの一種であるヒープソートは、ヒープの性質、法則性が分かると簡単に実装できます。実行も速いのでぜひ挑戦してみてね。2019.08.27交換ソートのひとつであるノームソート。名前がファンタジーなのでお気に入りのアルゴリズムです。コメントをキャンセルメールアドレスが公開されることはありません。コメントデータの処理方法の詳細はこちらをご覧ください。todoUnityのアセットを作ったり、スマホ向けのアプリを作っています。このブログではUnity初心者に向けたチュートリアルやテクニックを放出しています。詳しいプロフィールはこちら。お仕事の相談や現在提供中のサービスについては、こちらの『サービス内容』のページをご覧ください。Explorers_todoオンライントレーニングのサイトをオープン!エクスプラボを運営しているtodoが、より集中的にゲーム作りについて学べるオンライントレーニングのサイトをオープンしました。エクスプラボのトレーニングルーム』です。勉強したことの進捗も表示できるようになっているので、どれだけ頑張ったのかが分かるようになっています。ゲーム開発の攻略チャート』というe-bookをプレゼントしています。メルマガではゲーム開発のテクニックを中心に役立つ情報をお届けします。詳しくはこちら!お仕事の依頼はこちら!ゲーム開発のサポートも可能!エクスプラボではゲーム開発のサポートのサービスも行なっています。いう場合にオススメのプランです。普通に開発依頼をいただいてもOKです。【Unity】ポストプロセシングを使って簡単にプロっぽいゲーム画面を作るゲームの作り方を学べるオンライン講座のサイトをオープンしました!【ゲーム開発】ゲーム開発者こそ体を動かしてアイディアを出すべきRANKING【Unity】Mathfの切り上げ、切り捨て、偶数丸め。使い分けが大事よねMathf【Unity】ゲームといえばランダム要素。(12)作ったアプリ空とにゃんこと風船と癒し系縦スクロール避けゲーの『空とにゃんこと風船と』(TODOWORKS名義でリリース)気軽に遊べるスマートフォン向けアプリです。ボクセルアートで彩られるどこかレトロ、でも新しい世界で癒されてみませんか?ぼく、猫ですって!タップ系RPG『ぼく、猫ですって!』(TODOWORKS名義でリリース)気軽に遊べるスマホRPG。