TeX でソート

ソートはソートでも単純なバブルソートです。バブルソートは、前から2つずつ要素を比べて大きいほうをどんどん後ろに送っていくという、かなり素朴な昇順並べ替えの方法です。Wikipedia にのっているアルゴリズムはこうです。

procedure bubbleSort( A : list of sortable items ) defined as:
  for each i in 1 to length(A) - 1 do:
       for each j in 2 to length(A) - i + 1 do:
         if A[ j ] < A[ j - 1 ] then
           swap( A[ j ],  A[ j - 1 ] )
         end if
       end for
  end for
end procedure

TeX でこれを実装したいのですが、いつものように「配列がない」という大きな問題でつまずきます。配列っぽいものを TeX で実現する手法はいくつか考えられますが、ここでは「TeX で brainfuck」のときと同じく count レジスタを使うことにします。バブルソートのアルゴリズムは配列をなめるループが2重になっているので、配列のインデックス用のレジスタも 2つ必要です。また、配列の全長（length）を格納しておくレジスタもあるとうれしい（これも 2つ必要）。そのほか、要素の入れ替え（swap）をする際に一時的に利用するレジスタもほしい（これも 2つ）。

%% count1からcount99を明示的に使うので\newcountで割り当てるわけにいかない。。
\countdef\p=0 \countdef\q=100
\countdef\length=200 \countdef\l=201  %% 配列の全長用
\countdef\i=202 \countdef\j=203       %% スワップ用

これだけ準備したら、冒頭のアルゴリズムを素直に書き下します。カウンタの値を増やしたり減らしたりするのに細心の注意が必要ですが、まあそのままです。

\length=0
\p=1

\def\sort#1{%
  \initArray#1\last
  \p=0 \q=1 \k=\length
  {\loop \advance\p by 1 \advance\k by -\p \advance\k by 1
    {\loop \advance\q by 1
           \i=\count\q \advance\q by -1 %% i = A[p]
           \j=\count\q \advance\q by 1  %% j = A[p-1]
           %% swap A[p] and A[p-1] when A[p] > A[p-1]
             \ifnum\i<\j \global\count\q=\j \advance\q by -1
                         \global\count\q=\i \advance\q by 1 \fi
           \ifnum\q<\k \repeat}
    \ifnum\p<\length \repeat}}

ここで、配列の初期化をする \initArray はこんな定義になっています。

\def\initArray#1{%
  \ifx#1\last
    \let\next=\relax
  \else
    \global\count\p=#1
    \global\advance\length by 1
    \advance\p by 1
    \let\next=\initArray
  \fi\next}

\initArray で \loop...\repeat を使っていない理由は特にありません。
結果を出力するマクロも必要ですね。

\def\showArray{%
  \p=1 \advance\length by 1
  {\loop
     \number\count\p\ \advance\p by 1
   \ifnum\p<\length
   \repeat}}

実装おしまい。上記のコードと以下の実行例を pdftex のプロンプトにコピペすれば（最初の \relax を忘れずに）……

\sort{{314} 4 8 1 2 3 {42}}
\showArray
\vfill\eject\end

こんな結果のPDFが得られるはず。

1 2 3 4 8 42 314

なお、ソートできるのは 1以上の自然数だけです。

---

まとめっぽいもの

TeXのプログラミングが難しい背景には、ろくなデータ構造がないという側面も大きい気がします。配列でもリストでもいいのですが、とにかくトークンの列だけでは面倒なことは多すぎる。

大事な話として、 count レジスタを配列に使ってしまうと別の目的に使えなくなり、これは実用上かなり無茶な制約なので、この記事はあくまでもネタでありトイプログラムです。ちなみに TeX で配列っぽいものを実現する別の方法としては、1以上の自然数 n を配列のインデックスに見立て、\n で値を表現する方法（\def\1{42} \def\2{314} ... といった具合）などが知られているようです。詳しく知りませんが検索したらそんな論文が出てきました（→ "Sorting within TeX"（PDF））。

ネタ元

マクロツイーター：TeX での末尾再帰 (5)の「問題 5」。バブルソートなら簡単ちゃうかなあと思ったら、案外と「実行制御」につまずきました。白状すると、\sort の実装はそんなに簡単ではなかったです。