dropsortをC++で実装してみた

dropsortとは

dropsortとは O(n)で配列がis_sortedになるソートアルゴリズムである

dropsort([1,2,5,4,3,7])
> [1,2,5,7]

……つまり、「前後の要素を比較して、前要素 > 後要素 なら 後要素をdropする」を繰り返すアルゴリズムである
例えば
入力が [0,1] なら 出力は [0,1] (in[0]<in[1]になりdropが発生しない)
入力が [1,0] なら 出力は [1]となる　(in[0]>in[1]になりin[1]をdropするのでin[0] のみが残る)

O(N)でsortedになる。正しい。
アルゴリズムとしては入力の単調増加を保証したいときとか便利そうだが、コレをsortと呼ぶのなのかはについては若干引っかかる

参考：
http://www.dangermouse.net/esoteric/dropsort.html

C++で実装してみた

要素の削除を伴うアルゴリズムなのでremoveにインタ－フェースを寄せてみた

template <class Iter, class Comp>
Iter dropsort(Iter begin, Iter end, Comp comp) 
{
    if (begin == end){
        return end;
    }

    auto sorted_last = begin;
    begin++;
    
    for ( ; begin != end; ++begin)
    {
        if (comp(*sorted_last, *begin)){
            sorted_last++;
            if(sorted_last != begin){
                *sorted_last=std::move(*begin);
            }
        }
    }

    sorted_last++;
    return sorted_last;
}

イテレータ（と比較関数）を渡すとイテレータの要素がsortされ、
(removeと同様に)戻り値としてsort済み要素の終端が返る

これを適当にeraseすればよい

main.cpp

int main()
{
    std::vector<int> v = {0, 1, 6, 7, 2, 3, 4, 5};
    auto it = dropsort(v.begin(),v.end(),[](auto lhs,auto rhs){return lhs<rhs;});
    v.erase(it,v.end());
    
    for(auto e:v){
        std::cout<<e<<" ";
    }
}

> 0 1 6 7 

参考：

http://www.dangermouse.net/esoteric/dropsort.html
https://metacpan.org/pod/Acme::Rautavistic::Sort