【Unity/C#】挿入ソートのアルゴリズムをC#で実装するばい!

【Unity/C#】挿入ソートのアルゴリズムをC#で実装するばい!

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

交換ソートのアルゴリズムを6種類ほど扱ったので、今度はちょっと違った系統の挿入ソートをC#で実装します。

交換ソートでは配列内にある要素同士で交換を行っていたのに対し、挿入ソートでは要素をずらした後、適切な位置に挿入する形で移動させます。

リアルな世界で本棚を整理するときのことを思い浮かべたら分かりやすいかもしれません。

今回もUnityを使いますが、「Array.Sort()やList<T>.Sort()を使え」はやっぱり禁止ワードです(いつもの)

 

環境

macOS 10.14 Mojave

Unity2018.3.14f1

Unity Hub 2.1.0

アルゴリズムって?

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

挿入ソートについて

挿入ソートはソートアルゴリズムの一種で、移動対象の要素を配列内の適切な位置に挿入する形で移動させます。

作者名で本棚を整理するときのように、ある本を手にとって、本棚の中で適切な位置を見つけたら、そこに本を挿入するイメージです。

最悪計算時間が\(O(n^2)\)、平均計算時間も\(O(n^2)\)なので要素数が増えると目に見えて遅くなります。しかし実装が簡単なため、要素数が少ない範囲では実戦でも使われています。

Unityが使っているC#では、Array.Sort()というソート用のメソッドがあります。このメソッドは要素数に応じてクイックソート、ヒープソート、挿入ソートをうまく使い分けているんです。

クイックソートでは配列の検索範囲をどんどん狭めていきますが、この検索範囲が16より小さくなった時には挿入ソートを使用しています。

クイックソートについてはこのブログでも扱っているのでよかったらあわせてご覧くださいな。

 

Array.Sort()の仕組みについてはMicrosoft社のドキュメントをご覧ください。メソッド説明の注釈部分に書かれています。

 

挿入ソートの仕組み

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

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

 

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

 

左から確認していきますが、インデックス0についてはそれより前の要素がないので次のインデックスに移ります。

インデックス0のチェック
インデックス0のチェック

 

インデックス1について比較を行います。『1』よりも前にある要素を見ると、『5』の位置に『1』が入るとちょうど良さそうです。

インデックス1のチェック
インデックス1のチェック

 

移動させる方法として、まず確認中のインデックス1の値を一時変数にキープします。『1』はインデックス0に入って欲しいので、そのインデックスまでの値(この場合は『5』)を右にずらします。

対象インデックスの値をキープ
対象インデックスの値をキープ

 

インデックス0にいた『5』をインデックス1にコピーしたため、インデックス0に『1』を挿入できるようになりました。

適切な位置が空くまで移動
適切な位置が空くまで移動

 

これで『1』の挿入は完了です。

キープした値をセット
キープした値をセット

 

続いてインデックス2に移りますが、『8』より大きな値が前のインデックスにないため、次のインデックスに移ります。

インデックス2のチェック
インデックス2のチェック

 

最後にインデックス3です。『4』より大きな値は2つあるので、これらをずらす必要があります。

インデックス3のチェック
インデックス3のチェック

 

移動させたい『4』の値をキープして、『5』と『8』を右にずらします。

対象インデックスの値をキープ
対象インデックスの値をキープ

 

インデックス1にいた『5』をインデックス2にコピーしたため、インデックス1に『4』を挿入できるようになりました。

適切な位置が空くまで移動
適切な位置が空くまで移動

 

『4』を挿入して処理は完了です。

キープした値をセット
キープした値をセット

 

挿入ソートの実装

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

 

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

SortBase.cs

 

こちらが挿入ソートの本体です。

InsertionSort.cs

 

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

挿入を行いたい要素はkeyという変数に保存し、適切な位置に挿入するようにしています。

外側のループでは確認対象のインデックスを表す変数iを増やしているのに対し、内側のループで挿入位置を検索する時には変数jを減らしています。

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

実行結果

出力結果を整形すると以下のようになります。

ちゃんと入れ替わってますね。

バブルソートではループごとに最後尾の値が確定していきましたが、こちらは値の確定がされていないことに注意してください。

挿入ソートもあとでまとめて性能比較して、バブルソートとの速度差を確認してみたいと思います。比較回数が少なくて済むので、理論的には挿入ソートの方が速いです。

まとめ

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

今回紹介したスクリプトはコメントやコンソール出力用の処理で長くなっていますが、よくよく見てみると単純な処理をしているだけだったりします。

ぜひ自分でもやってみてくださいな。

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

CTA-IMAGE

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


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


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


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