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

【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

アルゴリズムって?

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

バブルソートについて

配列の中身を昇順、あるいは降順に並び変えるのがソートですが、その中身の要素をそれぞれ比較して値の大小を確認し、並び変えていくのが交換ソートです。

泡のイメージ(ドット絵)
泡のイメージ(ドット絵)

 

配列を縦に並べたときに、要素がどんどん上にいく様子が泡のようだからバブルソートと名付けられたそうです。

いわゆる学習用のアルゴリズムで、とりあえず最初にやってみよう! と言われることの多いソート方法なので、平均計算時間、最悪計算時間ともに\(O(n^2)\)でちょっと遅め。効率を求めるなら派生先の奇遇転置ソートやシェルソートを使った方が良いですね。というか普通にクイックソートを使えばいいか。

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

バブルソートの仕組み

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

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

 

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

 

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

 

要素の比較
要素の比較

 

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

 

『5』と『1』を交換した
『5』と『1』を交換した

 

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

 

『5』と『8』の比較
『5』と『8』の比較

 

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

 

『8』と『4』の比較
『8』と『4』の比較

 

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

『8』と『4』の交換
『8』と『4』の交換

 

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

 

1巡目が終了した時の状態
1巡目が終了した時の状態

 

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

 

『5』が確定
『5』が確定

 

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

 

『1』と『4』が確定
『1』と『4』が確定

 

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

バブルソートの実装

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

 

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

SortBase.cs

 

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

BubbleSort.cs

 

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

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

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

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

実行結果

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

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

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

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

まとめ

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

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

 

※追記

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

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

CTA-IMAGE

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


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


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


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