キッカケ> ソートアルゴったーturuginaは『イントロソート』です。 と言われて、イントロソートってなんやねん って Wikipediaで調べてた
ら、ネタソートの内、ストゥージソート ってのが日本語版にはなくて、気になったので、さらに色々探し回って 英語版Wikipedia に Stooge sort の項を見つけて、割と簡単そうなんでじゃぁ実装してみるか。って実装してみた。 とかそんな感じ

#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";
}

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

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

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

トラックバック(0)

トラックバックURL: http://floralcompany.jp/mt/mt-tb.cgi/215

コメントする

AUTHOR

  • turugina (虎王 剱奈)
  • E-mail: turugina {at} floralcompany.jp
  • pixiv
  • ニジエ

2014年5月

        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

アーカイブ

OpenID対応しています OpenIDについて
Powered by Movable Type 5.2.10

- 警 告 -

本サイトにはいわゆる「18禁画像」(イラスト)へのリンクが存在します。 未成年の方や、その手の画像に不快感を覚える方は、 該当記事(「えちぃの」及び「ちょっとえちぃの」カテゴリ) をご覧にならないようお願いいたします。

上記を理解した上で非表示のブログパーツを表示する
あわせて読みたいブログパーツ
ついった
drawr/pixiv/twitpic