ボゴソートできたよー
SleepSortのTLにボゴソートが見え隠れしてたので(主におたっくすさん(@otaks21)辺りに)皆がSleepSort実装している間に何となくやってました
#include<iostream> #include<random> #include<algorithm> #include<boost/array.hpp> template<class RandomGen> class RandomGenerator { public: RandomGenerator(const RandomGen & gen) : gen_(gen) { } unsigned int operator()(const unsigned int & max) { return gen_(); } private: RandomGen gen_; }; template<class T,class RandomGen> bool bogo_sort(T & t,RandomGen & random_gen) { std::random_shuffle(t.begin(),t.end(),random_gen); return std::is_sorted(t.begin(),t.end()); } int main() { const std::size_t size = 10; const unsigned long seed = 12; std::mt19937 engine(seed); RandomGenerator<std::mt19937> gen(engine); boost::array<int,size> array = {0,7,14,8,12, 41,15,32,4,1}; while(!bogo_sort(array,gen)); for(auto it = array.begin();it < array.end();++it) std::cout << *it << std::endl; return 0; }
地味にコンパイルエラーに悩まされましたが無事完成。途中で@nagoya313さんからもアドバイスをもらったりしてseedも設定できるようにしました.
auto使ってないのはほぼ最終段階までideoneで開発してたからです(0xだとboostが使えない)
追記:少しだけ0xに・・・・
更に追記:wikipedia見るとis_sortというのがあるらしい・・・とするともうちょい最適化するとこんな感じかな http://ideone.com/TtQrg