【Unity/C#】バブルソートをC#で！　交換ソートのアルゴリズム

IT系の会社に入った当初、アルゴリズムについて学びました。

その時の気持ちを思い出して、基礎からもう一度アルゴリズムについておさらいしたいと思います。

今回は基本中の基本、バブルソートをC#で実装します。Unityを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)\)でちょっと遅め。効率を求めるなら派生先の奇遇転置ソートやシェルソートを使った方が良いですね。というか普通にクイックソートを使えばいいか。

バブルソートとかクイックソートとか出てくるなんて……これもうロックマン2だな？

バブルソートの仕組み

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

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

バブルソートでは左から順番に配列の要素を比較します。

インデックス0の『5』とインデックス『1』を比較した時、値の大きい『5』の方が前にいるため、『5』と『1』を入れ替えます。

続いてインデックス1とインデックス2の比較に移ります。『5』と『8』を比較すると、どうやら順番が正しいようです。この場合は何も処理を行わずに次のインデックスに移ります。

次に行うのはインデックス2とインデックス3の比較です。

『8』と『4』を比較すると、大きい『8』の方が前にいるので交換を行います。

インデックス3については次のインデックスが存在しないので、バブルソートの1巡目はこれで終了です。この時、右端の『8』については一番大きな値であることがわかっているため、確定できます。次のループでは確認から外すことができますね。

同じように2巡目が終了すると以下の状態になります。私たちは『1』と『4』が正しい位置にいることが分かりますが、アルゴリズムの中ではまだ『1』と『4』の比較が行われていないのでもう1回ループが発生します。

3巡目終了時にこのように確定されます。

何となく時間がかかりそうというのは掴んでもらえたかと思います。でも単純で分かりやすいですよね。

バブルソートの実装

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

配列の中身を表示するためのメソッドを用意して継承しています。

SortBase.cs

こちらがバブルソートの本体です。

BubbleSort.cs

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

このバブルソートでは外側のループと内側のループがあり、外側のループが終了するごとに右端の数字が確定していきます。内側のループの終了条件でiを使っていることに注目してもらえるといいかも。

内側のループでは比較と交換を行なっていきます。jが1からスタートしているのは、対象のインデックスと、その一個前のインデックスで比較を行なっているためです。

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

実行結果

テキストで実行結果を抜き出すと以下のようになります。

ちゃんと並べ替えができていそうですね。

上で説明したように、一番大きな数字は右端に送られて動いていないのが分かります。

ループを2重にして比較、交換を行うだけなので、簡単に実装できます。

まとめ

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

アルゴリズムに意識を向ける意味でも、もしやったことがなかったら、ぜひやってみてくださいな。

※追記

他の交換ソートのアルゴリズムと性能比較を行ったので、よかったらこちらもぜひ。

エクスプラボ

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

https://ekulabo.com/algorithm-performance

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