C++で様々なソートアルゴリズムを実装する

STLにはstd::sortというソートアルゴリズムが用意されています。これはランダムアクセスイテレータ２つを入力とし、破壊的な操作をする関数ですね。これと同じシグニチャで色々なソートアルゴリズムを実装してみたいと思います。wikipediaを参考にしています。詳しい説明はwikipediaをご覧ください。
学校の課題とかで丸写ししちゃだめだよ。

ちなみにSTLを全力で使います。C++らしさを出すために基本的には添え字ではなくイテレータを操作するようにしています。

1/28/2016 追記;
イテレータの情報をstd::iterator_traitsを使って取得するように記事を改めました。C++11までは推奨といったところですが、C++14からは必須だったと記憶しています。
また思いつきで書いていたコードを多少直しました。

iter_sorting_swap

最初に、あるヘルパ関数を紹介いたします。2つのイテレータを取ってソートしてくれる関数です。swapする必要があったらtrue, 必要なければfalseが返ってきます。

template< class RandomIter, class Predicate =
    std::less< typename std::iterator_traits< RandomIter >::value_type > >
static inline bool iter_sorting_swap(RandomIter a, RandomIter b,
    Predicate pred = Predicate())
{
  if (a > b) { return iter_sorting_swap(b, a); }
  // arguments must be a <= b
  return pred(*b, *a) ? std::iter_swap(a, b), true : false;
}

バブルソート

遅いけど一番素直なソート。隣り合うものをひたすら比較、交換していく。

template< class RandomIter >
void bubble_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 1) { return; }
  for (auto i = first; i != last; ++i)
  {
    for (auto j = last - 1; j > i; --j)
      { iter_sorting_swap(j, j - 1); }
  }
}

コムソート

櫛ソートとも。なんでこんな変な数字が出てくるのかは謎です。

template< class RandomIter >
void comb_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 1) { return; }
  auto size = last - first;

  for (decltype(size) interval = size / 1.3;; interval /= 1.3)
  {
    for (RandomIter i = first; i + interval < last; ++i)
      { iter_sorting_swap(i, i + interval); }
    if (interval <= 1) { break; }
  }
}

ノームソート

ノームさんが鉢植えを並び替えるときに使ったソート。forが多重になっていないことが特徴。

template< class RandomIter >
void gnome_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 1) { return; }
  for (RandomIter gnome = first + (last - first) / 2; gnome != last;)
  {
    if (gnome == first) { ++gnome; }
    iter_sorting_swap(gnome, gnome - 1)
      ? --gnome : ++gnome;
  }
}

挿入ソート

通常は遅いがある程度ソートされている場合非常に速くなるという特徴を持つソート。クイックソートで大雑把にソートしてから挿入ソートを適用すると速い。

template< class RandomIter >
void insertion_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 1) { return; }
  iter_sorting_swap(first, first + 1);
  for (RandomIter i = first + 1; i != last; ++i)
  {
    for (RandomIter j = i; j > first; --j)
    {
      if(!iter_sorting_swap(j, j - 1)) { break; }
    }
  }
}

マージソート

一度ばらしてソートしながらくっつければいいじゃないというソート。実装は少し反則気味で、もともとSTLにマージが用意されているので簡単に作れる。

template< class RandomIter >
void merge_sort(RandomIter first, RandomIter last)
{
  auto diff = last - first;
  if (diff <= 1) { return; }
  RandomIter middle = first + diff / 2;
  merge_sort(first, middle);
  merge_sort(middle, last);
  std::inplace_merge(first, middle, last);
}

奇偶転置ソート

バブルソートを偶数の添え字のものと、奇数の添え字のものとで別々にこなすように改良したもの。
名前がいまいち覚えづらいのが特徴。

template< class RandomIter >
void odd_even_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 1) { return; }
  for (bool incomplete = true; incomplete; )
  {
    incomplete = false;
    for (RandomIter i = first; i < last - 1; i += 2)
    { // even
      if (iter_sorting_swap(i, i + 1)) { incomplete = true; }
    }
    for (RandomIter i = first + 1; i < last - 1; i += 2)
    { // odd
      if (iter_sorting_swap(i, i + 1)) { incomplete = true; }
    }
  }
}

クイックソート

言わずと知れた最速のソート。特殊な想定をしなければ最も速いと言われている。
std::find_ifを使って実装してもよかったけど統一感が欲しくて若干C言語っぽい実装になっている。

template< class RandomIter >
void quick_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 1) { return; }
  RandomIter i = first, j = last - 1;
  for (RandomIter pivot = first;; ++i, --j)
  {
    while (*i < *pivot) { ++i; }
    while (*pivot < *j) { --j; }
    if (i >= j) { break; }
    std::iter_swap(i, j);
  }
  quick_sort(first, i);
  quick_sort(j + 1, last);
}

選択ソート

遅いけど分かりやすい。全ての要素を頭から見ていって一番小さかったり大きかったりするものを選択していく。ここでは小さいものを選んでいる。

template< class RandomIter >
void selection_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 1) { return; }
  for (; first != last; ++first)
  {
    auto min = std::min_element(first, last);
    std::iter_swap(first, min);
  }
}

シェーカーソート

基本的にはバブルソートだけど、前方と後方の両側からせめていくように改良したもの。

template< class RandomIter >
void shaker_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 1) { return; }
  for (RandomIter index; first != last;)
  {
    // commit forward scanning
    for (auto i = first; i != last - 1; ++i)
    {
      if (iter_sorting_swap(i, i + 1)) { index = i; }
    }
    last = index;
    if (first == last) { break; }

    // commit backward scanning
    index = last;
    for (auto i = last; i != first; --i)
    {
      if (iter_sorting_swap(i, i - 1))　{ index = i; }
    }
    first = index;
  }
}

クイックソートで大雑把にソートをしてから残りをソートするタイプの人。

クイックソートは分割して再帰を繰り返すため、最後の最後までクイックソートでは最後の方が非常に遅くなってしまう上にスタックオーバーフローを起こす可能性がある。ある程度でクイックソートを中断してしまい、最後を別のアルゴリズムでガーッとソートすると速度が改善され、オーバーフローの危険性も減る場合がある。そんなソートたち。

ここのクイックソートでは、要素が40未満であれば途中で中断してしまうようにした。

template< class RandomIter >
void _q_sort(RandomIter first, RandomIter last)
{
  if (last - first <= 40) { return; } // ここ以外は上の物と一緒
  RandomIter i = first, j = last - 1;
  RandomIter pivot = first;
  for (;; ++i, --j)
  {
    while (*i < *pivot) { ++i; }
    while (*pivot < *j) { --j; }
    if (i >= j) { break; }
    std::iter_swap(i, j);
  }
  _q_sort(first, i);
  _q_sort(j + 1, last);
}

イントロソート

クイックソートの後にマージソートを行うソート。gccのstd::sortではこれを使っていると聞いたことがある。

template< class RandomIter >
void intro_sort(RandomIter first, RandomIter last)
{
  _q_sort(first, last);
  merge_sort(first, last); // 上のやつ
}

挿入ソートをつかうソート

正式名称はしらない。数値を扱う場合はstd::sortより速いことが多い。

template< class RandomIter >
void quick_insertion_sort(RandomIter first, RandomIter last)
{
  _q_sort(first, last);
  insertion_sort(first, last); // 上のやつ
}

テスト用のコード

こういうのを書くと簡単にテストできる。
ストップウォッチクラスを書くと時間計測も楽。

#include <iostream>
#include <iterator>
#include <random>

int main()
{
    std::vector< int > vec;
    std::random_device rd;
    std::mt19937 mt(rd());
    std::generate_n(std::back_inserter(vec), 10, mt);

    quick_sort(begin(vec), end(vec));

    std::copy(begin(vec), end(vec),
        std::ostream_iterator< int >(std::cout, "\n"));
}

おわりに

ソートのアルゴリズムはたくさんありますが、比較ソートの一部だけを扱いました。
手元のコードを直しながら記事を書いたので、うごかねーぞとか間違ってるよとかあったらコメントを頂けると幸いです。