最速と最遅のソートアルゴリズム

前回はMBAくれとかクソみたいなエントリ書いてますね。ちなみに木曜日は僕の誕生日なのでMBAくれてもいいですよ。

ソートアルゴリズムについて調べて同僚と話していたらクソみたいなソートアルゴリズムについて知ることができたのでまとめてみます。

オーダーはなんとO(0)！素晴らしいですね。
気持ちとしては、ソート出来てるものが来ればソートしなくてもいいんだし最速じゃね？

vector<int> LuckySort(vector<int> a) { return a; }

うーん、実にひどい。天和で上がった気分でしょうか。

オーダーはなんとO(n*n!)！どれだけかかるのか見当もつきませんね。
毎回の繰り返しでソートされてるのを祈り続けるアルゴリズム。スピリチュアルソート。

擬似コードは以下の通り。

vector<int> BogoSort(vector<int> a) {
  while(std::is_sorted(a.begin(), a.end()) {
    std::random_suffle(a.begin(), a.end());
  }
  return a;
}

うーん、実にひどい。延々と天和になるまで待ち続ける。

Bogo Sortは可視化したものをjsdo.itで発見しました。-id:cou929_laがグラフで可視化してカオスになるやつを教えてくれたんですが失念しました。

クソみたいなソートアルゴリズムでしたが面白かったのでまとめてみました。今回色々調べてみて知らないアルゴリズムがたくさんあったので面白かったです。真面目に調べたのもあるので、割と当たり前な内容なんですがいずれまとめてみようと思います。