堕(惰)プログラマ開発記録

クイックソートしてみた

C++

なんか適当なアルゴリズムを書いてみたいなと思ったので、

私流、クイックソート関数を書いてみました。

テンプレート周りはstd::sortを真似して、後は自己流の組み方。

最後オーバーロードできる用にboost::lambdaを使用していますが、

そこを消せばboostを使わず、std::sortのような使い方ができると思います。

namespace algorithm{
  //イテレータの型をもらう
  template<class RandomAccessIterator, class Compare>
  int quick_sort(RandomAccessIterator start,RandomAccessIterator end,const Compare comp)
  {
    //全要素数を数え、要素数2に満たなければreturnする(比較必要がないため)
    int total = distance(start,end);
    if(total<2) return 0;

    //真ん中あたりの数値をピボットに設定
    RandomAccessIterator p = start + (int)total/2 ;
    
    RandomAccessIterator i = start;
    RandomAccessIterator j = start+total-1;

    while(true){
      while(comp(*i,*p)) ++i; //ピボット以上のiを見つける
      while(comp(*p,*j)) --j; //ピボット以下のjを見つける
      
      if(i<j)
      {
        //iがjより左にあれば交換処理
        iter_swap(i,j);
        ++i;
        --j;
      }
      else
      {
        //それ以外なら二つに分割し次に渡す
        algorithm::quick_sort<RandomAccessIterator,Compare>(start,i,comp);
        algorithm::quick_sort<RandomAccessIterator,Compare>(i,end,comp);
        break;
      }
    }
    return 0;
  }

  template<class RandomAccessIterator>
  int quick_sort(RandomAccessIterator start,RandomAccessIterator last)
  {
    return quick_sort(start,last,(boost::lambda::_1 < boost::lambda::_2));
  }
}

こんなコードで。

そんでもって使用は

template<class It>
void disp(It it,It end)
{
  while(it != end)
  {
    std::cout << *it << std::endl;
    ++it;
  }
}

int main()
{
  std::vector<int> v;
  v.push_back(7);
  v.push_back(6);
  v.push_back(5);
  v.push_back(3);
  v.push_back(8);
  v.push_back(5);
  v.push_back(8);
  v.push_back(15);
  v.push_back(60);
  v.push_back(30);
  v.push_back(55);
  v.push_back(88);
  v.push_back(60);
  v.push_back(12);
  v.push_back(16);

  disp(v.begin(),v.end());
  std::cout << "\n\n";

  algorithm::quick_sort(v.begin(),v.end());
  disp(v.begin(),v.end());

}

こんなものでどうでしょか。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 21:39