すとぅーじ・そーと [C++]

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>
#include <sstream>

#include <cstdlib>
#include <time.h>

#ifdef USE_BOOST_PROGRAM_OPTIONS
#include <boost/program_options.hpp>
#endif

bool display_inout;

int call_count = 0;
int swap_count = 0;

template<typename Iter>
void stooge_sort(Iter beg, Iter end);

template<typename Iter>
void stooge_sort_(Iter beg, Iter end)
{
    typedef typename Iter::difference_type diff_t;
    const diff_t d = std::distance(beg, end);

    if ( d < 2 ) return;

    Iter last = end-1;

    if ( *beg > *last ) {
        ++swap_count;
        std::swap(*beg, *last);
    }

    if ( d >= 3 ) {
        const diff_t dt = d/3;
        stooge_sort(beg, beg + dt*2);
        stooge_sort(beg + dt, end);
        stooge_sort(beg, beg + dt*2);
    }
}

template<typename Iter>
void stooge_sort(Iter beg, Iter end)
{
    ++call_count;

    if ( display_inout ) {
        std::cout << "in:[";
        std::copy(beg, end, std::ostream_iterator<typename Iter::value_type>(std::cout, ","));
        std::cout << "]\n";
    }

    stooge_sort_(beg, end);

    if ( display_inout ) {
        std::cout << "out:[";
        std::copy(beg, end, std::ostream_iterator<typename Iter::value_type>(std::cout, ","));
        std::cout << "]\n";
    }
}

int get_random(int num)
{
    return std::rand()%num;
}

int main(int c, char** v)
{
#ifdef USE_BOOST_PROGRAM_OPTIONS
    int num;
    namespace po = boost::program_options;
    po::options_description desc("options");
    desc.add_options()
        ( "num",
          po::value<int>(&num)->default_value(100),
          "number of elements to be sorted (default 100)" )
        ( "verbose",
          "display in/out data on each recursive call of stooge_sort");
    po::variables_map vm;
    po::store(po::parse_command_line(c, v, desc), vm);
    po::notify(vm);
    display_inout = vm.count("verbose");
#else
    (void)c; (void)v;
    const int num = 100;
    display_inout = false;
#endif


    time_t t = time(NULL);
    std::srand((int)t);

    std::vector<int> hoge;
    for ( int i = 0; i < num; ++i ) hoge.push_back(i);

    std::random_shuffle(hoge.begin(), hoge.end(), get_random);

    stooge_sort(hoge.begin(), hoge.end());

    std::cout <<
        "number of elements = " << num << "\n" <<
        "call count = " << call_count << "\n" <<
        "swap count = " << swap_count << "\n";
}

まぁ、こんな感じでいいかな。 では、ソートの様子を出力するようにして いざ！

.... 遅いｗ しかしちゃんとソートされてる。すげぇ。

後、 N=1000 とかでソートの様子を出力してたら全然終わらんかったので、出力無しで試したら stooge_sort()の呼び出し回数は 14230861 回 だった。 そりゃぁ、まぁ...