さんぽみち

なにか思いついたときとかに気まぐれに更新されます。

比較演算を行わないバブルソート

C# アルゴリズム

はじめに

　とりあえず何か書きたかったので、一発ネタで前に作った比較演算を行わないバブルソート。

　だいぶ前に書いたので今見ると無駄が多い！！

　全体を通して言えることだけども、数字に 1 を掛けると変化せず、 0 を掛けると 0 へつぶれることを利用して、比較せずに数字を選択しています。

　以下簡単な解説を。

各メソッドの概要

　引数が 0 であれば 0 を返し、それ以外であれば 1 を返すメソッドです。

　0 以外の任意の整数 n において、これの二の補数を m として、

　　n or m

　をとると必ず最上位ビットが立ち、0 の場合のみ立たないことを利用して判断しています。

　今回メインとなるメソッドです。

　0 または自然数 numA, numB のうち、大きな数字を返すメソッドです。

　まずは、符号なしなので最上位ビットを比較することでどちらが大きな数字であるか判断します。

　numA, numB いずれか一方のみの最上位ビットが立っていた場合は、立っていた値が残り、同じ場合であった場合は 0 となります。

　次に、差をとって比較します。

　符号なし整数での減算は、被減数が減数と比べて小さい場合はオーバーフローして最上位ビットが立ちます。

　numA, numB が違う値であればこの最上位ビットを見ることで、どちらが大きな値であるか判断できます。

　次に、numA, numB が等しかった場合を考慮して、等しければ適当に numA を残します。

　最後に、これまでの計算結果をすべて足し合わせます。

　それぞれの計算結果は、大きな値が確定できた場合のみ大きな値が、確定できなかった場合は 0 が残っているので、足すことで正しい結果が得られます。

 　Maxメソッドと同様に、逆のことを行っているだけです。

　符号付き整数を、大小関係そのままに符号なし整数と相互変換するメソッド達です。

　普通にキャストすると、符号付き整数は補数表現されたビット列になるので、そこへ最上位ビットのみ立てた数値と足すだけです。

  • BubbleSortActionデリゲート

　ソートするためにはインデックスを使用して配列にアクセスしなければなりません。

　よって条件を付けて何らかの形でループさせてインデックスを操作しなければなりませんが、比較演算を行わない縛りであるため通常のループ構文は使えません。

　そこで、再帰によりループを再現し、2 要素のデリゲート配列に対するインデックスを切り替えることで 継続：終了 をスイッチします。

　スタックを大量に使うので、なるべく節約するために引数は参照渡しです。

　クラス変数にしないことで、一応スレッドセーフです。

　再帰的にバブルソートを行うメソッドです。

　再帰なのを除けば何の変哲もないバブルソートです。

　インデックスが一回りすればデリゲートが切り替わるように細工してあります。

　再帰を終了させるためのメソッドです。

　out 修飾子は値を代入しなければエラーとなるため、ダミーで初期化します。

　バブルソートを行うための入口です。

　引数で渡す領域の初期化を行って再帰を始めます。

 

　以上、大雑把な説明でした。

おわりに

　確かどこかにLargeメソッドとSmallメソッドを追加して書き換えたのがあったはずだけど見当たらないので見つけたらそっちで書き直す。。。

　この再帰を使った方法でマージソートが実装できる気がしたからやってみようと思ってたはずだけども手付かずなので、気が向いたら書きます！