Brainfuckでもバブルソートができたら強いと思いませんか。
私は思うので記事を書きます。
この記事ができた経緯
私個人的な意見ですがソートプログラムはプログラマのスキルを測る一つの指標のような認識があります。
だから何としてもBrainfuckでバブルソートを成し遂げたいと思いました。
私が用いたアプローチはこうでした。
- あらかじめ用意されたデータの列がある
- そのデータ列に対して左の値が右の値よりも大きい場合、左右を入れ替えるといった処理を繰り返し行う
- 入れ替えが発生しなかったら順番に並んでると見做して終了。
このアプローチは一般的なバブルソートのそれとは異なります。
一般的なバブルソートでは繰り返しごとに実際にソートされるデータは1つずつ減少していきます。
しかし私の書いたものではいつまでも、既に整列されていることが明らかなデータまでもがソートの対象になってしまっています。
そこであるコードを追加して以下のような機能を追加しました。
- 明らかに整列が完了したデータは切り離す。
これで一般的なバブルソートに近い形になりました。
実際は並び替えが発生しなくなった段階で終了するので一般的なものより早く終わります。
前準備
データの構造
まず、ソートの対象となるデータは01からFFまでの値です。
00はソートの対象から外しています。
データの構造はそれぞれのソート対象のデータの両端に00があり、それぞれの要素が00で分けられているものとします。
NN=01~FF
...|00|00|NN|00|NN|...|NN|00|NN|00|00|...
swap
n0,n1=NN
...|n0|00|n1|...
となっている二値をswapするコードは以下の通りです。
[-<+>]<<[->>+<<]>[-<+>]
状態の遷移は以下の通りです。
...|n0|00|n1|...
^[-<+>]
...|n0|n1|00|...
^<<
...|n0|n1|00|...
^[->>+<<]
...|00|n1|n0|...
^>
...|00|n1|n0|...
^[-<+>]
...|n1|00|n0|...
^
大小の比較
数値の大小を比較する方法を考えましょう。
今回のソートアルゴリズムでは昇順に整列させたいので左側>右側の場合にswapを行いたいと思います。
前提としてBrainfuckには比較演算子がありません。
そのため、数値の大小という考えそのものが素朴です。
そのため、数値の大小をBrainfuck的に定義する必要があります。
さて、数値、例えばa,bの大小を考える時、a<b⇔0<b-aならaはb未満であり、a≧b⇔0≧b-aならaはb以上であるとわかります。
もちろん比較演算子がないのでこの式をそのまま実装はできないのですが、数値の大小は引き算と密接に関わっています。
それを踏まえて、とりあえずBrainfuckで引き算を考えていきます。
これは単純に
aとbの両方から同じ値だけ引けば実現できます。
[->>-<<]
さて、もし左側にあるのをa、右側にあるのをbとした時、a≧bであればbの値は一度は00をとるはずです。
...|NN|00|NN|...
↑a ↑b
それではbが 00の時があったかどうかを確認してみましょう。
[->>-
[<]-[>]<<+[->+>>>+<<<<]>
<<]
...|NN|00|NN|00|00|ZZ|...
↑a ↑b ↑未満なら01、それ以外は00
さて、このコードを実行するともともとaの値が入っていた場所には00が、bの値が入っていた時には元の値からaの値だけ減らした値が入っています。
これではもう一度比較する時に不都合が生じます。
そのため、再度aの値だけaとbの双方に加算する必要があります。
[->>-
>>+<<
[<]-[>]<<+[->+>>>+<<<<]>
<<]
>>>>
[-<<+<<+>>>>]
ソート実装
メインのソートを行う部分です。
とりあえず構造はこんな感じにします
...|rf|NN|00|NN|...|NN|00|NN|00|00|...
rfはループフラグです。
rfがある限りバブルソートは動き続けます。
{入力部}
>>+[->>,----------]<<[+++++++++++<<]>
+[-
>[
{比較する値を移動}
>>
{比較}
[<<->>->>>+<<<<<[<]-[>]<<+[->+>>>+<<<<]>>>]
{値を復元}
>>>[-<<<+<<+>>>>>]<<
{swapしないフラグを退避}
[->>+<<]
{swapの対象が00ではないかを確認}
<[<]-[>]<<+[
{00の場合、swapしないフラグに値を有効にする}
->+>>>+<<<<
]>>>>
{swapする}
-[
+<<<[-<+>]<<[->>+<<]>[-<+>]<<<<
{swapをしたというフラグ}
+
>>>>>>>>
]
<<<<<<<<
{フラグを移動}
[[-]>>+<<]
>>>>>
]
<<
{整列済みの値の切断を行う}
[->>+<<]
<<
{swapをしたというフラグを先頭付近まで持っていく}
[>[-<<+>>]<<<]
>
{swapを1度でもしてたら繰り返す}
]
>
{切断場所に移動}
[>>]
>>
{切断したデータを再度くっつける}
[[-<<+>>]>>]
<<<<
{ソートする配列の先頭に戻る}
[<<]>>
{結果を出力}
[.>>]
コメントなし
>>+[->>,----------]<<[+++++++++++<<]>+[[-]>[>>[<<->>->>>+<<<<<[<]-[>]<<+[->+>>>+<<<<]>>>]>>>[-<<<+<<+>>>>>]<<[->>+<<]<[<]-[>]<<+[->+>>>+<<<<]>>>>-[+<<<[-<+>]<<[->>+<<]>[-<+>]<<<<+>>>>>>>>]<<<<<<<<[[-]>>+<<]>>>>>]<<[->>+<<]<<[>[-<<+>>]<<<]>]>[>>]>>[[-<<+>>]>>]<<<<[<<]>>[.>>]