はじめに
slowsortというソートアルゴリズムをScalaで記述してみた．Scalaのバージョンは2.13.8，IntelliJ IDEA上で実行．できるだけ関数型っぽくなるように実装を心がけてみた．
slowsortとは
slowsortとは，[1]で発表された効率の悪いソートアルゴリズムである．
アルゴリズムを次に示す．
procedure slowsort (A, i, j) =
{This procedure sorts the subarray A_i, A_{i+1}, ..., A_j.}
if i >= j then
return
else
m = floor((i+j)/2)
slowsort(A, i, m)
slowsort(A, m+1, n)
if A_m > A_j then swap(A_m, A_j) fi
slowsort(A, i, j-1)
fi
erudecorp
（[1]より引用，一部改変．余談だけどprocedureを終わらせる所でerudecorpと逆向きに書くやり方があるんですね）
日本語にすると（たぶん上のように書いたほうがわかりやすいが），slowsortアルゴリズムは次のようになる．
- 配列長が1以下ならば配列をそのまま返す．
- そうでなければ，配列の前半に再帰的にslowsort．
- 配列の後半に再帰的にslowsort．
- 各配列の最後の値（この時点でソートされているため，各配列の最大値である）を比較し，前半の配列の最後の値の方が大きければ，後半の配列の最後の値と交換する．（この時点で，全体の配列の最大値が配列の最後の要素になる．）
- 配列の最後の値を除いた配列に再帰的にslowsort．
ただし，関数型プログラミングでは配列の最初の要素へのアクセスが一番早いと聞いたので，この記事では4. で最小値を配列の最初の要素にし，5. で配列の最初の要素を除いた配列をslowsortすることとする．
関数型っぽくするために，slowsortを数式に落とす．ソートする配列を$l$とすると，まず配列の前半および後半は次のように書ける．
first\_half = l.slice(0,floor(\frac{l.length}{2})) \\
second\_half = l.slice(floor(\frac{l.length}{2}),l.length) \\
ここで，$slice(n,m)$関数は配列の$n$番目から$m-1$番目までの配列を取り出す関数であるとする．（なお，この式をプログラムに落とす際は分数の部分はどちらも整数型であるため，$floor$関数は不要である．）
これらをslowsortした結果は次のように書ける．
s\_fst = slowsort(first\_half) \\
s\_scd = slowsort(second\_half) \\
ここで，これらの配列はソートされているため，先頭は各配列の最小値である．従って，それらの要素を比較すれば配列全体の最小値が求められる．その結果に応じて，最小値があった方の配列を先頭（つまりhead）と後尾（つまりtail）に分け，後尾と別の配列を連結した配列をslowsortし，その配列の先頭に最小値を追加すればよい．つまり，配列の先頭に要素を追加する演算子を$::$，配列同士を連結する演算子を$:::$とすると，次のように書ける．
slowsort(l) = \begin{cases}
{s\_fst.head :: slowsort(s\_fst.tail ::: s\_scd)\qquad (s\_fst.head < s\_scd.head)} \\
{s\_scd.head :: slowsort(s\_fst ::: s\_scd.tail)\qquad (otherwise)}
\end{cases}
slowsortの実装
折角なので，配列の要素をどう比較するかも関数を呼ぶ側に決めてもらう．（関数を引数にすると関数型っぽい気がするので．あと昇順にするとこか降順にするとかも呼ぶ側で決められる．）
slowsort関数の宣言は次のようになる．
def slowsort[T](l: List[T], f: (T, T) => Boolean): List[T] = {
slowsort[T]のTでは配列の要素の型を指定し，引数lには配列を，引数fには要素の比較に使用する関数を入れる．
配列lの要素数が1以下であれば，何もせずにそのまま返す．
if(l.length <= 1) l
そうでなければ，配列lの前半と後半をそれぞれソートし，結果を保存しておく．
val sorted_first_half = slowsort(l.slice(0,l.length/2), f)
val sorted_second_half = slowsort(l.slice(l.length/2,l.length), f)
各配列の先頭の要素を関数fによって比較し，その結果に応じていずれかの配列を返す．
if(f(sorted_first_half.head, sorted_second_half.head)) {
sorted_first_half.head :: slowsort(sorted_first_half.tail ::: sorted_second_half, f)
} else {
sorted_second_half.head :: slowsort(sorted_first_half ::: sorted_second_half.tail, f)
}
関数全体は次のようになる．
def slowsort[T](l: List[T], f: (T, T) => Boolean): List[T] = {
if(l.length <= 1) l
else {
val sorted_first_half = slowsort(l.slice(0,l.length/2), f)
val sorted_second_half = slowsort(l.slice(l.length/2,l.length), f)
if(f(sorted_first_half.head, sorted_second_half.head)) {
sorted_first_half.head :: slowsort(sorted_first_half.tail ::: sorted_second_half, f)
} else {
sorted_second_half.head :: slowsort(sorted_first_half ::: sorted_second_half.tail, f)
}
}
}
実行結果
次のプログラムを実行する．
Random.setSeed(0)
val array_before_sort = Random.shuffle((0 until 32).toList)
println("ソート前のリスト:")
println(array_before_sort.mkString("(",", ",")"))
println("昇順ソート:")
println(slowsort[Int](array_before_sort, _ < _).mkString("(",", ",")"))
println("降順ソート:")
println(slowsort[Int](array_before_sort, _ > _).mkString("(",", ",")"))
実行結果は次のようになる．
ソート前のリスト:
(22, 10, 8, 9, 6, 3, 26, 1, 5, 28, 12, 18, 24, 29, 0, 14, 16, 17, 25, 21, 30, 13, 31, 15, 27, 7, 20, 11, 4, 19, 2, 23)
昇順ソート:
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
降順ソート:
(31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
なお，使用したプログラムは次のリポジトリに上げている．
https://github.com/HidetaroTanaka/scala_slowsort_implementation/tree/194e6378b511c39ea2d75fbd90699e8ce8366c0a
今後の課題
もっと関数型っぽい書き方を調べてみる，処理時間を最初から用意してあるsortedメソッドと比較する等．
参考文献
[1] Andrei Broder and Jorge Stolfi. 1984. ``Pessimal algorithms and simplexity analysis.'' SIGACT News 16, 3 (Fall 1984), 49–53. https://doi.org/10.1145/990534.990536