【><>】難解プログラミング言語><>でソートを実装する方法

はじめに

こんにちは，競技プログラミング(AtCoder)を難解プログラミング言語の><>で解いている者です．

競技プログラミングをやっていると，入力された数値をソートして解く問題がたくさんあります．
そこで，今回の記事では><>でソートを実装する方法を解説します．
紹介するのはバブルソート，計数ソートです．

それぞれ$O(N^2)$，$O(N+A)$なアルゴリズムであり，AtCoderをやるうえで必須な$O(N \log N)$のソートのアルゴリズムは実装できていません．
（私の実力的にスタック指向言語における早いソートの実装の仕方がまだわかりません泣，実力が付いたら第2段を投稿するかもしれません．）

なお，今回の記事ではソートアルゴリズムの仕組みそのものは解説しないです．
ソートアルゴリズムは以下の記事が大変分かりやすいので，こちらを参照してください．

バブルソート

まずは実装が簡単なバブルソートの実装方法を以下に示します．
以下のプログラムはスタックの数字を降順に並び替えます(スタックの先頭を数列の最後尾と考えた時の降順です．つまりスタックの先頭が最小値になります)．昇順にソートするバージョンは作成していないですが，ソートした後にrすればいいだけなので問題ないと考えています．

ちなみにバブルソートは平均計算量が$O(n^2)$なソートなのでかなり遅いです．手元の環境（Rust製のインタープリタfishr）で動かしてみた感じ$N=2000$ぐらいが限界です．
しかし，以下に列挙したように位置に寄らず動作するため，取り回しは非常に良いです．

• ジャンプ命令なし
• 現在のレジスタの値を変更しない
• g p命令なし
• スタックの数字は正負，整数・小数問わずソート可能

バブルソート

>l[0&>l1=?vl1-v-1}$@@$?(@<
vv?&<&!<<<<   >:?!v@$:@$:^
v>] ^^[-1l+1&:&}~ <
>

左上の>から始まって，左下の>で終了します．

上の図が命令ポインタの動きです．かなり効率よくコードをかけているのが分かるでしょうか．

使用例

0 ~ 9 の数字をソートする例です．
outputは昇順になっていますが，これはスタックの先頭から順に出力しているためです．

バブルソートの使用例

36005190782442v
v             <
>l[0&>l1=?vl1-v-1}$@@$?(@<
vv?&<&!<<<<   >:?!v@$:@$:^
v>] ^^[-1l+1&:&}~ <
> >l?!;nv
  ^ o" "<

output

0 0 0 1 2 2 3 4 4 5 6 7 8 9 

計数ソート

次に計数ソートの実装です．これも同様に降順にソートします．
計数ソートはあまりメジャーなソートアルゴリズムではないですが，><>的に実装しやすかったので作ってみました．
計算量は$O(n+A)$になっています．（$A:=$データの最大値）
そのためデータの最大値が小さく，データ数が$2 \times 10^5$程度ならば実時間内にソートをすることができ，実用的です．

しかし，AtCoderのABCのC問題以降はほとんどデータ数$2 \times 10^5$，データの範囲$0 \le A \le 10^{18}$とされている場合が多いので，使いどころは少ないかもしれません．

また，以下に書いた通り，g p命令を使用します．具体的にはコードブロック上の16行目（f 行目）にデータを書き込みながらソートしていきます．
そのため，16行目には何も書き込まないようにする必要があります．

• ジャンプ命令なし
• 現在のレジスタの値を変更しない
• g p命令あり（16行目に値を書き込みます）
• スタックの数字は（0を含む）正の整数だけの場合のみソート可能

計数ソート

>l[0&>l?!v:fg1+$:&$:v
     ^pf~&!&$?)@:$@ <
         >:0(?v:fgv$@:$-<
             > :fg>:?!v1^
             ^v?(0:-1~<
              >~>

16行目が使えないとプログラムしにくい場合もあるので，226行目（f*f 行目）にデータを書き込むバージョンも用意しました．
実行時間は大して変わらないので，こちらを使うべきですね．

計数ソート（226行目に書き込むバージョン）

>l[0&>l?!v:ff*g1+$:&$:v
     ^p*f&!f~&$?)@:$@ <
         >:0(?v:ff*gv$@:$-<
             > :ff*g>:?!v1^
             ^v?(0:-1~  <
              >~>

使用例

0 ~ 9 の数字をソートする例です．

係数ソートの使用例

36005190782442v
v             <
>l[0&>l?!v:ff*g1+$:&$:v
     ^p*f&!f~&$?)@:$@ <
         >:0(?v:ff*gv$@:$-<
             > :ff*g>:?!v1^
             ^v?(0:-1~  <
              >~>l?!;nv
                ^ o" "<

output

0 0 0 1 2 2 3 4 4 5 6 7 8 9 

おわりに

私事ですが，ついにAtCoderのABC001~ABC100までのA問題を全て><>で解き終わりました．
近々解説記事を投稿する予定なので，お楽しみに．