2009-11-26

insertion sortをジェネリックに実装してみた

namespace hito {

namespace detail {

template < typename Iterator >
void rotate( Iterator first, Iterator last )
{
    using namespace std ;

    for ( Iterator i = first ; i != last ; ++i )
    {
        swap( *first, *i ) ;
    }
}

}

template < typename Iterator, typename Compare >
void insertion_sort(
    Iterator first,
    Iterator last,
    Compare comp  )
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type ;

    Iterator i = first ;
    for ( ++i ; i != last ; ++i )
    {
        Iterator iter =
            std::find_if( first, i,
                [&](value_type const & value){ return comp( *i, value ) ; }
            ) ;

        if ( iter != i )
        {
            Iterator last = i ;
            ++last ;
            detail::rotate( iter, last ) ;
        }
    }
}

}

やりすぎたかもしれない。

調べたら、広く知られているinsertion sortのコードは駄目すぎる - やねうらお-よっちゃんイカを食べながら年収1億円稼げる(かも知れない)仕事術よりちょっぴり遅かった。

ただ、insertion sortは、ほとんどソートされた配列に提供するのが筋である。だから、逆から追っていくのが普通の実装だ。bidirectionalにしていいなら、もうすこし早くなるのかも。

追記:std::move()のイテレーターは、オーバーラップできないので、自前で書いた。

2 comments:

やねうらお said...

> insertion sortは、ほとんどソートされた配列に提供するのが筋である。
> だから、逆から追っていくのが普通の実装だ。

この部分、意味がよくわかりません。

例えば、完全にソートされた配列 a[] = {3,4,5} に、完全にソートされた配列かb = {1,2}をappendした配列 c[] = {3,4,5,1,2} やソートされていない配列 b'={2,1}をappendした配列 a'= {3,4,5,2,1}に対して、逆が追っていくと、前から辿るよりメモリコピーの回数が増えます。

こういう意味ではないのでしょうか・・。

「ほとんどソートされた配列」、たとえば a'' = { 1,2,3,0,4 }に対しても前から追ったほうが速いです。もちろん逆から追ったほうが速い、「ほとんどソートされた配列」も作ることは出来ますが、要するに「ほとんどソートされて」いることと前から辿るか後ろから追うかは何の関係もないように思えます。

結局、前から辿っても逆から追っても平均すれば同じ処理量であるなら、後ろから追うとメモリハザードが生じる可能性が高いぶんだけ損ではないかと思うのですが。

hito said...

ですよね。勘違いしてました。