もっと遅いソート

# これは何？

2014年に [遅いソート]( https://nabetani.hatenadiary.com/entry/20140816/p1 ) という記事を書いた。
もっと遅くできるなと以前から思っていたんだけど、それを記事にした。

## 遅いソートの例

[Wikipedia の ボゴソート](https://en.wikipedia.org/wiki/Bogosort) に書いてある例、有名なもの、そして私案を挙げる

### bubble sort

遅いソートアルゴリズムとして、おそらく最も有名。

```ruby:ruby
def bubblesort!(s)
  (s.size).times do |i|
    (1...s.size).each do |j|
      s[j], s[j-1] = s[j-1], s[j] if s[j]<s[j-1]
    end
  end
  s
end
```

一般的には実用にならないぐらい遅いソートアルゴリズムの代表のような扱いだけれど、今回扱うアルゴリズムの中ではぶっちぎりに速い。1000件の整列が瞬きする間に終わるなんて、夢のようだ。

### slow sort

Wikipedia に [記事]( https://en.wikipedia.org/wiki/Slowsort ) がある。

1. 領域を前半と後半に分ける。
1. 前半と後半をそれぞれ slow sort。
1. 前半の末尾と後半の末尾を、必要なら入れ替える → 末尾が最大値となることが保証される。
1. 末尾を除いた領域を slow sort。

というもの。末尾再帰でなければスタックをたくさん使うが、スタック・オーバーフローするようなデータ量だと計算が終わらないので問題にならないと思う。

ruby で書くとこんな感じ。

```ruby:ruby
def slowsort!(s)
  impl = ->(i,j){
    return if j<=i
    m=(i+j)/2
    impl[i,m]
    impl[m+1,j]
    s[j],s[m] = s[m],s[j] if s[j]<s[m]
    impl[i,j-1]
  }
  impl[0,s.size-1]
  s
end
```

わりとひどいアルゴリズムに見えるけど、今回扱うアルゴリズムでは二番目に速い。

### bogo sort

非実用的な遅いソートアルゴリズムとして、おそらく最も有名。
「適当に混ぜて、整列されていたら終了」というシンプルなアイディア。

ruby の場合とても簡単に書ける。

```ruby:ruby
def bogosort(x)
  loop do
    s = x.shuffle
    return s if s.each_cons(2).all?{ |a,b| a<=b }
  end
end
```

乱数の質によっては整列できない（つまり、無限ループとなる）可能性がある。
ワーストケースは無限。

### bozo sort

「整列していなければ、ランダムな2要素を入れ替える」を繰り返すだけというこちらもシンプルなアイディア。
こちらは C 言語などでも簡単に書けると思うけど、下記は ruby。

```ruby:ruby
def bozosort!(x)
  loop do
    return s if s.each_cons(2).all?{ |a,b| a<=b }
    a,b = rand(x.size), rand(x.size)
    s[a], s[b] = s[b], s[a]
  end
end
```

bogo sort と同じく、乱数の質によっては整列できない（つまり、無限ループとなる）可能性がある。
直感的には bogo sort より遅そうだけど、動かしてみるとわりと同じぐらいに見える。

### 拙作(2014)

2014年に私が考えた計算。
もっと前に誰かが考えていると思うけど、探してないので私より先に発見した人がいるかどうかは知らない。

並べ方を全部列挙して、整列済みならそれを返すというもの。
bogo sort と似ているけど、 bogo sort と違って有限の時間で終わる。

ruby で書くと簡単。

```ruby:ruby
def nabesort_2014(s)
  s.permutation(s.size){ |x|
    return x if x.each_cons(2).all?{ |a,b| a<=b }
  }
end
```

平均的な計算時間は bogo sort と同じだと思う。

### 拙作(2022)

2014年の記事を書いた後、 `repeated_permutation` にしたらもっと遅くなるよね、と誰かに言われたのか自分で気づいたのか覚えてない。

で、書いた。

```ruby:ruby
def nabesort_2022(s)
  s.repeated_permutation(s.size){ |x|
    return x if (
      x.each_cons(2).all?{ |a,b| a<=b } && 
      x.all?{ |e| x.count(e)==s.count(e) }
    )
  }
end
```

終了条件として、できた列が整列済みか否かの他に、各要素の個数が入力の列と同じかどうもチェックする必要がある。
そのチェックに 最悪 $O(n^2)$ の計算を入れている。

もっと遅くすることはできるんだと思うけど、今回紹介する中では一番遅い。

# オーダー

真剣に検討してないけど、下表ぐらいだと思う。

|名前|typical case　　　　　　|best case　　|worst case　　|n=100　|
|:--|:--|:--|:--|:--:|
|bubble|$O(n^2)$ |同左 |同左| $10^4$|
|slow|$O(exp(6n^{1/6}))$ ぐらいかな| 同左 | 同左| $10^6$|
|bogo|$O(n!)$ ぐらい|$O(n)$|$O(∞)$| $10^{160}$|
|bozo|$O(n!)$ ぐらいかな|$O(n)$|$O(∞)$| $10^{160}$|
|鍋2014|$O(n!)$ ぐらい|$O(n)$ ぐらい|$O(n!)$ ぐらい| $10^{160}$|
|鍋2020|$O(n^n)$ ぐらい|$O(n^2)$ ぐらい|$O(n^n)$ ぐらい|$10^{200}$|

たとえば。「$O(n^n)$ ぐらい」は、適当なあまりおおきくない定数 A があれば「$O(n^n)$」と「$O((n+A)^{n+A})$」の間のどこかじゃないかな、ぐらいの気持ち。

slow のオーダーはよくわからないんだけど、雑にフィットしてこれぐらい。
bozo もよくわからないんだけど、bogo と同じぐらいかなと思っている。

# 実測

シャッフル済みの要素数 9 の配列を 1回だけ整列するという、かなりしょぼい計算をした。
最初、要素数 10 にしたんだけど、10分たっても終わらなかったので 9 にした。

```text
               user     system      total        real
    bubble   0.000012   0.000000   0.000012 (  0.000011)
      slow   0.000019   0.000001   0.000020 (  0.000020)
      bogo   1.092641   0.006429   1.099070 (  1.099211)
      bozo   1.069077   0.004266   1.073343 (  1.073448)
 nabe 2014   0.178649   0.001577   0.180226 (  0.180302)
 nabe 2022 185.339007   1.285942 186.624949 (186.634422)
```

nabe 2022 だと、9要素の整列に3分以上を要した模様。人間のほうが速い。
この調子だと、10要素は40分ぐらいかな。

# まとめ

軽い気持ちで書いてみたら、思ったよりだいぶ遅くなった。

あと、[Wikipedia の bogosort のページ](https://en.wikipedia.org/wiki/Bogosort) に、Worstsort というもっと遅そうなのがあったけど、試せないほど遅そうなので試してない。

それと。
もし、もっと遅いアルゴリズムがあるという場合は、この記事のコメント欄でそのアルゴリズムを紹介するのではなく、別の記事を起こすことをおすすめする。