【Unity/C#】シェーカーソートのアルゴリズムをC#で実装！

バブルソートを改良したシェーカーソートのアルゴリズムを使ってC#で実装してみようという試みです。

Unityを使うならArray.Sort()やList<T>.Sort()を使えばいいのですが、アルゴリズムについて基礎から振り返ってみるのが目的なので、その辺りには目を瞑ってくださいな。

環境

macOS 10.14 Mojave

Unity2018.3.14f1

Unity Hub 2.1.0

アルゴリズムって？

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

エクスプラボ

アルゴリズムってなんやいね？　って時に読む記事【初心者向け】

https://ekulabo.com/whats-algorithm

初心者のうちからアルゴリズムを理解し、処理時間を意識していくと、超イケてるプログラミングが可能になります。慣れてる人は多分無意識のうちにやっていることなんですよね。

シェーカーソートについて

シェーカーソートは交換ソートの一種で、バブルソートを改良したもの。

バブルソートでは配列のインデックスが小さい方から順番に比較を行なっていたのに対し、シェーカーソートではインデックスの小さい方から比較を行った後、今度はインデックスの大きな方から比較を行っていきます。

バブルソートでは毎回のループで右端の値が確定していたのに加えて、外側のループ1回につき左端の値も確定するようになります。確定した要素があればその分比較を行う範囲も狭められるので、処理時間の短縮に繋がります。最悪計算時間のオーダーは\(O(n^2)\)でバブルソートと同じですが、切り捨てた係数などでちょっとアドバンテージがあります。

バブルソートについてはこちらの記事をご覧ください。

エクスプラボ

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

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

バブルソートについての説明とC#による実装を紹介しています。一度は触れるアルゴリズムよね。

シェーカーソートの仕組み

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

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

まずはインデックスの0から3に向かって昇順で比較を行っていきます。この時の動きはバブルソートと同様です。インデックスの昇順方向への処理が終了した時点で以下のように8が確定します。

同じループ内で、今度はインデックスの3から0に向かって降順で比較を行います。8は確定しているので、『4』と『5』の比較から行います。

『4』と『5』は順番が逆になっているので交換を行います。比較を行うときの条件は昇順時と異なるのでよく確認します。

このとき、最後に交換したインデックスを記憶しておくことで、次回のループの開始地点として設定することができます。交換が発生しなかったということは、正しい並び順になっているということなので、処理対象から外すことができます。

インデックスの小さい方、大きい方の双方から範囲を狭めていくことができるため、バブルソートより高速に並べ替えが終了します。

シェーカーソートの実装

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

あとWikipediaに書かれているCのコードを思いっきり参考にしてます。すみません。

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

SortBase.cs

こちらがシェーカーソートの本体です。

ShakerSort.cs

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

バブルソートと同じように外側のループと内側のループが存在しています。こちらでは外側のループの実行回数が確定でないため、Whileループを使って処理が終了するまで回しています。

Whileループの中では昇順に比較を行うループと降順に比較を行うループが存在しています。それぞれのループが終了した後に終了条件を確認しています。

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

実行結果

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

並べ替えがちゃんとできていました。内側のループが呼ばれた回数を処理回数としてカウントしているのですが、バブルソートの時は55回、今回は47回と呼ばれる回数が減りました。

バブルソートでは外側のループが呼ばれた回数が11回、シェーカーソートでは4回で済みました。4回目のループでは比較が発生しないことを確認して処理を抜けていますね。

どえらい高速化という訳ではありませんが、多少改良されているなーというのは感じます。性能比較をするなら要素数が10000とか100000の配列を使って処理時間の比較を行うべきですが、この記事ではそこまでやらないことにします。

まとめ

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

バブルソートをやった後に改良型のアルゴリズムを試すと、処理がちょっと改善されているのを感じられて楽しいですね。

※追記

他の交換ソートのアルゴリズムと性能比較を行ったので、よかったらこちらもぜひ。ちゃんとバブルソートよりも速くなっていました。

エクスプラボ

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

https://ekulabo.com/algorithm-performance

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