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

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

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

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

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

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

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

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

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

エクスプラボ

 

1 User

【Unity/C#】最速と噂のクイックソートのアルゴリズムを実装！

https://ekulabo.com/algorithm-quick-sort

交換ソートのひとつであるクイックソートは、ソートするならクイックソートで、と言われるくらいには速いソート方法です。バブルとクイックは押さえておきたいところ。

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

docs.microsoft.com

Array.Sort Method (System)

https://docs.microsoft.com/ja-jp/dotnet/api/system.array.sort?view=netframework-4.8

1 次元配列の要素を並べ替えます。Sorts the elements in a one-dimensional array.

挿入ソートの仕組み

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

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

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

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

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

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

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

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

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

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

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

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

挿入ソートの実装

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

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

SortBase.cs

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

InsertionSort.cs

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

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

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

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

実行結果

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

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

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

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

まとめ

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

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

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