スローソート

スローソートはソートアルゴリズムです。ユーモラスな性質を持ち、実用的ではありません。乗算と降伏の原理（分割統治の反対をとったパロディ）に基づいた、消極的なアルゴリズムです。1984年にアンドレイ・ブローダーとホルヘ・ストルフィによって論文「ペシマルアルゴリズムとシンプレクシティ分析」^[¹^] （最適アルゴリズムと複雑性分析のパロディ）で発表されました

アルゴリズム

スローソートは再帰アルゴリズムです。

インプレースでソートします
これは不安定なソートです。(同じ値のキーの順序が変わる可能性があります。)

擬似コードの実装を以下に示します。

手順slowsort ( A [] , start_idx , end_idx ) // 配列範囲 A[start ... end] をインプレースでソートします。start_idx ≥ end_idxの場合はreturnmiddle_idx := floor ( ( start_idx + end_idx ) / 2 ) slowsort ( A , start_idx , middle_idx ) // (1.1) slowsort ( A , middle_idx + 1 , end_idx ) // (1.2) if A [ end_idx ] < A [ middle_idx ] then swap ( A , end_idx , middle_idx ) // (1.3)slowsort ( A , start_idx , end_idx - 1 ) // (2)

前半部分を再帰的にソートする。(1.1)
後半部分を再帰的にソートする。(1.2)
1.1と1.2の結果を比較して配列全体の最大値を求め、それをリストの最後に配置します。(1.3)
リスト全体を（最後にある最大値を除いて）再帰的にソートします。（2）

Haskellでの最適化されていない実装(純粋関数型) は次のようになります。

slowsort :: ( Ord a ) => [ a ] -> [ a ] slowsort xs | length xs <= 1 = xs |それ以外の場合= slowsort xs' ++ [ max llast rlast ] -- (2)ここでm = length xs ` div ` 2 l = slowsort $ take m xs -- (1.1) r = slowsort $ drop m xs -- (1.2) llast = last l rlast = last r xs' = init l ++ min llast rlast : init r

計算量分析

スローソートの時間計算量は関数で与えられます。これは、最初の再帰呼び出し(1.1)と(1.2)の再帰関係をそれぞれ作成し、最後の再帰呼び出し(2)を合計し、この場合、他の操作を定数(+1)としてモデル化することで求められます。これにより、ランダウ記法におけるの下側漸近界は、任意のに対してとして与えられます。したがって、スローソートは多項式時間ではありません $T(n)=2T(n/2)+T(n-1)+1$ $T(n)$ $\Omega \left(n^{\log_{2}(n)/(2+\epsilon)}\right)$ $\epsilon >0$