【Unity/C#】名前がかっこいい奇偶転置ソートのアルゴリズムを実装

奇偶転置ソート……超かっこいい……(恍惚)

IT系のワードはこんな感じで厨二心にクリティカルヒットなネーミングが転がってるからやめられません。

いい歳した大人が「奇偶転置ソートで配列入れ替えて」みたいなこと言ってる職場もあるんですよ。夢が広がりますね。

それはさておき、今回は奇偶転置ソートのアルゴリズムをC#で実装します。Unityを開きっぱなしなのでUnityで実行させましょう。

Unityを使うならArray.Sort()やList<T>.Sort()を……というツッコミが毎回入りそうでビクビクしているのですが、目的はアルゴリズムを体験することなので目を瞑っていただきとうございます。

環境

macOS 10.14 Mojave

Unity2018.3.14f1

Unity Hub 2.1.0

アルゴリズムって？

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

エクスプラボ

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

https://ekulabo.com/whats-algorithm

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

奇偶転置ソートについて

奇偶転置ソートはバブルソートの改良型で、奇数番目の要素を起点にして比較を行うバターンと、偶数番目の要素を起点にして比較を行うパターンを繰り返します。

C#の場合だと、インデックス0と1、2と3、4と5……というように組を作っていくパターン、インデックス1と2、3と4、……というように組を作っていくパターンを繰り返すことになります。

バブルソートでは左からひとつずつ順番に比較・交換を行っていたため、交換した後の値を使っていくこととなり、順番に処理する必要がありました。

こちらの奇偶転置ソートでは、ひとつのパターンの中では比較・交換するペアが独立しているので、うまく処理を分散させれば高速化が見込めます。最悪計算時間のオーダーは\(O(n^2)\)でバブルソートと同じです。

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

エクスプラボ

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

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

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

奇偶転置ソートの仕組み

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

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

まず、開始インデックスが偶数となるペアで比較・交換を行います。インデックス0の『5』とインデックス1の『1』が最初の対象ですね。

このペアでは『1』の方が後ろにいるので、交換を行います。

次はインデックス2の『8』とインデックス『4』のペアで比較・交換を行います。

こちらも『4』が後ろにいるので交換を行います。注目して欲しいのは、『1』と『5』のペア、『4』と『8』のペアで比較・交換の処理が独立していること。この処理を並列で行うことができれば、処理時間の短縮になります。

続いて開始インデックスが奇数となるペアで比較・交換を行います。この例だとインデックス1とインデックス2のペアのみですね。実際には配列はもっと大きくなると思うので、その場合はペアが複数ある状態になります。

インデックス1の『5』とインデックス2の『4』の比較を行うと『4』の方が後ろにいるので交換を行います。

この時点で1回の外側ループが終了します。各ループ内で交換が行われなかった場合に終了と判断することができます。

奇偶転置ソートの実装

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

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

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

SortBase.cs

こちらが奇偶転置ソートの本体です。

OddEvenSort.cs

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

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

Whileループの中にあるループは2つで、開始インデックスが偶数のペアで比較・交換を行うループ、開始インデックスが奇数のペアで比較・交換を行うループとなっています。ループのインクリメントが2ずつになっていることに注目です。

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

実行結果

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

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

バブルソートでは毎回のループで右端の値が確定していたのでどんどん処理範囲を狭めることができたのですが、今回の奇偶転置ソートでは「偶数ループ、奇数ループの両方で交換が起こらなかったら終了」となっているので、回数だけで言えば増えてもやむなしかな。

むしろ奇偶転置ソートの強みは並列処理できるところにあります。

今回紹介したアルゴリズムは、「ハードウェア側で処理を分散させるのであれば」という前提のアルゴリズムになっています。

このあたりの性能差はもう少し大きな配列で比べないと分かりにくいと思うので、別記事で試してみたいと思います。

まとめ

今回は奇偶転置ソートのアルゴリズムをC#で実装しました。

ループが呼ばれた回数では性能を測ることは難しいため、処理時間を見て比較を行いたいと思います。

※追記

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

エクスプラボ

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

https://ekulabo.com/algorithm-performance

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