【Python】最も効率の悪いソートを実装してみた

# 経緯
アルゴリズムの勉強をしていたら奇妙なソートに出会った。 
　
<iframe width="560" height="315" src="https://www.youtube.com/embed/kPRA0W1kECg?start=318" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>　　　　　

　
ソートしてるのかも怪しい。。

# ボゴソート（bogo sort）とは

ソートのアルゴリズムの一つ。
**非常に効率の悪い**アルゴリズムとして知られている。

> In computer science, bogosort(also known as permutation sort, stupid sort, or slowsort) is a sorting algorithm based on the generate and test paradigm.
（コンピュータ サイエンスでは、bogosort (順列ソート、愚かなソート、またはスローソートとも呼ばれます) は、生成とテストのパラダイムに基づくソートアルゴリズムです。）


この「ボゴ」は、英語の `bogus` から来ていて、**「偽物」「でっち上げ」** って意味があるらしい。
どんだけポンコツなんだろ。

https://en.wikipedia.org/wiki/Bogosort

なぜ英語wikiなのかというと、このボゴソートには**2種類**のバージョンがあるらしい。

1.  **randomized** version（ランダム化された）
2.  **deterministic** version（決定論的）


日本語版では `randomized` の方が紹介されているので本記事もそっちで扱います。

**効率の良いソート**としては[クイックソート](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88)などが知られてるけど、
**最も効率の悪いソート**が **「ボゴソート」** なんだね。

# アルゴリズム
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/777324/935a29e0-f2d6-3977-d5db-02febb845a77.png)

トランプを例にすると、
1. トランプ52枚の束を放り投げて、**バラバラ**にする。
2. 1枚ずつ**無作為**にすべてを拾い集める。
3. ソートされているか確認する。
4. 1から3までの手順を繰り返す。

らしい。これはもうアルゴリズムなのか。。？

**無作為**ってところが抽象的で、コードに起こすときは`random`モジュールを使うことで**無作為**を表現しようと思います

# 実装してみる

```python:bogosort.py
import random

# ソートされているかどうか
def isSorted(nums):
	for i in range(len(nums) - 1):
		if nums[i] > nums[i + 1]:
			return False
	return True

# ソートされるまで無限にシャッフルする
def bogoSort(nums):
	cnt = 0
	while not isSorted(nums):
		random.shuffle(nums)
		cnt += 1
	return cnt


def main():
    # 範囲1~10まで、長さ10の配列を作る（重複無し）
	nums = random.sample(range(10), k=10)
	cnt = bogoSort(nums)
	print(str(cnt) + " times shuffled.")

if __name__ == "__main__":
	main()

```

コードはすっきり書けますね。
`random` モジュールの `sample` で適当な配列を作り、`shuffle`で混ぜてます。

# 予想
10個くらいなら、1万回もループすれば終わりそう。
3秒くらいとみた！


# 実行してみる

### 環境
| System | Version |
| :-: | :-: |
| OS | MacOS Monterey(12.1) |
| python | 3.8.8 |
| bash | GNU bash, version 3.2.57(1)-release |
| zsh | zsh 5.8 (x86_64-apple-darwin21.0) |

### 前提条件

| 項目 | 条件 |
| :-: | :-: |
| 範囲(int) | 0 ~ 10 |
| 要素数(n) | 10 |
| 重複 | 無し |


```shell:zsh
time python bogosort.py
```

```python:結果
11450 times shuffled.
python bogosort.py  0.10s user 0.04s system 52% cpu 0.265 total
```
`0.10s`
あれ？意外と早いんじゃね？
再度実行

```python:結果
2289936 times shuffled.
python bogosort.py  10.33s user 0.04s system 97% cpu 10.685 total
```
`10.33s`
なんだ、たまたまか。
何回か試してみるためスクリプトを作ってみた。

```shell:keisoku.sh
touch log.txt
for i in `seq 5`
do
echo "<$i回目>" >> log.txt 
(time python bogosort.py) 2>&1 | tee -a log.txt
echo "" >> log.txt
done
```
（`time`コマンドは**標準エラー出力**だったことを知り、ファイルのリダイレクトがうまくいかず苦戦したのも良い勉強になった。。）

```shell:Terminal
zsh keisoku.sh
```

```python:log.txt
<1回目>
1528975 times shuffled.
python bogosort.py  8.59s user 0.12s system 92% cpu 9.421 total

<2回目>
849286 times shuffled.
python bogosort.py  4.72s user 0.04s system 98% cpu 4.840 total

<3回目>
3672885 times shuffled.
python bogosort.py  21.86s user 0.23s system 88% cpu 24.878 total

<4回目>
180921 times shuffled.
python bogosort.py  1.46s user 0.04s system 73% cpu 2.037 total

<5回目>
9826624 times shuffled.
python bogosort.py  63.35s user 0.59s system 89% cpu 1:11.69 total
```

ふむふむ、使えねぇソートだ。

# 計算量（オーダー）

| 最悪計算時間 | 最良計算時間 | 平均計算時間 |
| :-: | :-: | :-: |
| $O(∞)$ | $O(n)$ | $O(n*n!)$ or $O((n+1)!)$ |

平均計算時間の表記がいろんなサイトで違う書き方されてる。
条件によって異なるってことかな。

# 終わりに

ボゴソートを別言語で実装した人もいますね。

https://qiita.com/fuj1kky/items/b8650acfcc3adb01b270

https://qiita.com/kousukeex/items/e646d8933ac0815e59b5

従来のソートアルゴリズムの凄さを実感したってことにする。
今回は10個で試しましたが、それより多い数は言うまでもないです。

# 補足

「keisoku.sh」ファイルを実行するときに、`bash keisoku.sh`としてもよかったんだけど、なぜか文字化けしたので`zsh`で実行してました。

![スクリーンショット 2022-09-21 22.26.47.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/777324/6bc3a8b2-f62e-e14e-45c1-04bc2262af11.png)

`bash`と`zsh`とで変数の展開の仕方が違うからかな？とか考えてた。

> 変数の語尾に日本語がある場合は文字化けしてしまうため、ドル波括弧${t}で記述する必要ある。

https://iwb.jp/shellscript-var-braces-japanese-mojibake/

なるほど、書き方が違うのか。
でも文字化けする根本的な原因はイマイチわかってない。。

次回はこれも調べてみようかな。


# 参考にしたサイト

https://www.geeksforgeeks.org/python-program-for-bogosort-or-permutation-sort/