【Unity/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

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

クイックソートについて

交換ソートの一種であり、配列から部分配列を抜き出してその中でソートして元の配列に戻るという分割統治法の一種です。

分割して統治するのは、問題を小分けにして各個撃破していくのに似ていますね。

バブルソートから学び始めて、最終的にクイックソートにたどり着くのが大体のルートでしょうか。バブルだのクイックだの、これもうロックマン2だな？

分割の仕方ですが、まず基準となる値(ピボット)を決めます。ピボットの決め方は何種類かの流派があり、配列の最初の値、配列内のランダムな要素の値、配列から3つの値を選んだうちの中央値、配列の最後の値、などがあります。

配列内を検索し、ピボットより大きな値を後方の配列に、ピボットより小さな値を前方の配列に持っていきます。前から検索していったインデックスと後ろから検索していったインデックスが交わったところで、配列内の探査領域を2つに分けます。

分割された領域についても同様の手順で分割していくと、要素数が少なくなったところで並び順が確定していきます。これを繰り返せば並び変わった配列が現れます。

最悪計算時間は\(O(n^2)\)ですが、平均計算時間が\(O(n\log n)\)となるため、要素数が多い場合にも計算時間はそこまで大きく増えたりはしません。

クイックソートの仕組み

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

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

まずはピボットを選択します。今回は配列の先頭、配列の最後尾、配列の真ん中の値を抜き出し、その中央値をピボットとする方法をとります。

配列の先頭は『5』、配列の最後尾は『6』、配列の真ん中の値は『4』となっています。このうち中央値となるのは『5』なのでこれをピボットにします。

左から『5』以上の値を検索すると、最初のインデックスにある『5』が該当します。これを交換対象とします。

右から『5』以下の値を検索すると、インデックス6の『3』が該当します。これを『5』と交換します。

続いて左から『5』以上の値を検索すると、インデックス2の『8』が該当します。

右から『5』以下の値を検索すると、インデックス5の『2』が該当します。これを『8』と交換しましょう。

続けて左から『5』以上の値を検索すると、インデックス4の『7』が該当します。

右から『5』以下の値を検索すると、インデックス3の『4』が該当します。

しかし、このふたつを交換してしまうとせっかく前に集めた小さい数字が後ろに行ってしまうので、ここで検索を終了します。

左からの検索で最後に見つけたインデックス4の『7』の左側で範囲を分割します。

次は分割した範囲の左側を見ていきます。

配列の先頭は『3』、配列の最後尾は『4』、配列の真ん中の値は『1』となっています。このうち中央値となるのは『3』なのでこれをピボットにします。

左から『3』以上の値を検索すると、最初のインデックスにある『3』が該当します。これを交換対象とします。

右から『3』以下の値を検索すると、インデックス2の『2』が該当します。これを『3』と交換します。

続けて左から『3』以上の値を検索すると、インデックス2の『3』が該当します。

右から『3』以下の値を検索すると、インデックス1の『1』が該当します。しかし、やっぱりこのふたつを交換してしまうとせっかく前に集めた小さい数字が後ろに行ってしまうので、ここで検索を終了します。

左からの検索で最後に見つけたインデックス2の『3』の左側で範囲を分割します。

範囲を分割したインデックス0から1の範囲について見ていきます。

配列の先頭は『2』、配列の最後尾は『1』、配列の真ん中の値は……って値は2つしかないので、どちらかの値を中央値にするか、あるいは2つの値からの選択でピボットを選びます。ここでは値の大きい『2』をピボットにします。

左から『2』以上の値を検索すると、最初のインデックスにある『2』が該当します。これを交換対象とします。

右から『2』以下の値を検索すると、インデックス1の『1』が該当します。これを『2』と交換します。

続けて左から『2』以上の値を検索すると、インデックス1の『2』が該当します。

右から『2』以下の値を検索すると、インデックス0の『1』が該当します。これも交換する必要がないため、ここで検索を終了します。

左からの検索で最後に見つけたインデックス1の『2』の左側で範囲を分割します。この状態になればもう分割する必要はないため、次の範囲であるインデックス2から3の確認に進みます。

『3』と『4』でピボットを選択します。ここでは値の大きい『4』をピボットにしますが、交換は行われません。

ここでも『3』と『4』で分割して処理終了です。

左側の範囲であるインデックス0から3と同様に、右側の範囲のインデックス4から7についても同じ処理を行い、最終的に並び替えられたところで処理が終了します。

範囲を変えて同じ処理を行なっていく点は、メソッド内で同じメソッドを呼び出す再帰的な処理で表現します。

範囲を分割し、その分割した範囲内で整理していくあたりが分割統治法と呼ばれる所以です。

クイックソートの実装

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

あと例のごとくWikipediaに書かれているコードを思いっきり参考にしてます。

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

SortBase.cs

こちらがクイックソートの本体です。

QuickSort.cs

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

ExecuteQuickSortのメソッドを呼び出すことでクイックソートが実行されます。このメソッド内でも範囲を変えてExecuteQuickSortのメソッドを再帰的に呼び出しています。

ExecuteQuickSortでは要素数が1になったところで再帰的な呼び出しを行わずに処理を終了します。

GetMediumValueのメソッドでは引数で渡された3つの値のうち、中央値を返しています。値が同じ場合は、配列の最後尾の要素が返されるようになっています。

交換の後にインデックスを進める処理を忘れると、配列内に同じ数字が2つあった場合に無限ループに陥るので気をつけましょう(1敗)

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

実行結果

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

無事に並び変わっていそうです。処理回数として表示しているのはExecuteQuickSortが呼ばれた回数です。

処理範囲を狭めていっているからか、交換回数も少ない印象です。あくまで「印象」なので、これもちゃんと性能比較してみないといけませんね。

※追記

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

エクスプラボ

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

https://ekulabo.com/algorithm-performance

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

まとめ

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

ソートするならクイックソートで、くらいに言われているので、それだけ速さが期待できるソート方法です。

名前の潔さも素敵ですよね。「俺が一番速いぜ！」って名前してますもの。