2

これを作成して、並べ替えアルゴリズムと汎用関数をよりよく理解できるようにします。基本的な挿入ソート アルゴリズムを実装し、それを複数のデータ構造 (少なくともリストと配列) で機能させようとしています。

list[N] のようなリストにアクセスして値を取得できるので、イテレータを使用する必要があると思います。だから私は自分のソリューションを変換しようとしています。私が変更しようとしている基本的な挿入ソートアルゴリズムは次のとおりです。

int *insertionsort(int *a)
{
  for (int i = 1; i<length(a); ++i)
  {
    int k = a[i];
    int j = i-1;
    {
      while (j>=0 && a[j] > k)
      { 
        a[j+1] = a[j--];
      }
    a[j+1] = k;
  }
  return a;
}

そして、これが私がこれまでにジェネリックバージョンで持っているものです:

template <class T>
T insertionsort(T a)
{
  for (auto i = a.begin()+1; i<a.end(); ++i)
  {
    auto k = i;
    auto j = i-1;
    while (j>=a.begin() && *j>*k)  
    {
      (j + 1) = j--; 
    }
    (j + 1) = k;
  }  
   return a;
}

残念ながら、この一般的な関数を正しく並べ替えることができないようです。私は運が悪いので、これをかなり長い間見てきました。アイデア？

4

3 に答える 3

8

OPの参照用にのみ投稿され、長生きする可能性は低い. C++11 を使用する傾向があり、タイピングが嫌いな場合は、これでうまくいくかもしれません。

template<typename Iter>
void insertion_sort(Iter first, Iter last)
{
    for (Iter it = first; it != last; ++it)
        std::rotate(std::upper_bound(first, it, *it), it, std::next(it));
}

使用される機能の関連リンク:

std::upper_bound、std::next、およびstd::rotate。楽しみ。

于 2013-08-26T22:57:45.670 に答える
3

イテレータ/ポインタの逆参照と混同していると思います。これはうまくいくはずです：

template <class T>
T insertionsort(T a)
{
    if(a.begin() == a.end()) // return a when it's empty
        return a;
    for(auto i = a.begin() + 1; i < a.end(); ++i)
    {
        auto k = *i; // k is the value pointed by i
        auto j = i - 1;
        while(j >= a.begin() && *j > k)  
        {
            *(j + 1) = *j; // writen in 2 lines for clarity
            j--;
        }
        *(j + 1) = k;
    }  
    return a;
}
于 2013-08-26T22:24:12.693 に答える