株式会社エス・スリー・フォー

listに使える 3(+1)つの sort

sort は list をソートできない…

標準C++が提供する<algorithm>には便利なアルゴリズムがたくさん用意されています。

その中でもソート(sort,stable_sort)は使用頻度の高いアルゴリズムでしょう。

残念なことに、sort,stable_sortが引数として受け取るイテレータはRandomAccessIteratorでなくてはなりません。したがってlist<T>の要素をソートしたいとき、

list<int> il;
sort(il.begin(), il.end());

というコードはコンパイルエラーを引き起こします。list<T>のイテレータはBidirectionalIteratorであり、ランダムアクセスできないからです。

list<T>にはメソッドsort()が用意されてはいますが、コードの中で用いるコンテナを様々に取り替えるような場合、

#ifdef USE_LIST
typedef list<int> container;
#else
typedef vector<int> container;
#endif
...
container c;
...
#ifdef USE_LIST
c.sort();
#else
sort(c.begin(), c.end());
#endif

のように、#ifdef…#else…#endifで切り換えなくてはならなくなります。

ここで、Bidirectionaliterator(あるいはForwardIterator)を受け付けるソートアルゴリズムを用意すれば、このような切り替えを行なわずに済みます。

selection_sort: 単純選択ソート

単純選択ソートのアルゴリズムは非常に単純です。

  1. x[0] .. x[N-1] の中から最小の要素 x[i] を見つけ、それと x[0] を交換する
  2. x[1] .. x[N-1] の中から最小の要素 x[i] を見つけ、それと x[1] を交換する
  3. x[2] .. x[N-1] の中から最小の要素 x[i] を見つけ、それと x[2] を交換する

…これをN回繰り返せばソート完了です。

要素の比較回数はN2に比例し、交換回数はNに比例します。

buble_sort: バブルソート

最も有名かつ最も遅いソートです。

  1. x[0] と x[1] を比較し x[0] > x[1] なら、この2つを交換する
  2. x[1] と x[2] を比較し x[1] > x[2] なら、この2つを交換する
  3. x[2] と x[3] を比較し x[2] > x[3] なら、この2つを交換する

…これをN回繰り返すと、X[N-1]には最大要素が格納されることになります。

そしてこの一連の処理の中で一度でも交換が行なわれたら最大要素を除く(要素数はひとつ少ない)列に対し再度繰り返します。

要素の比較回数/交換回数共にN2に比例します。

comb_sort: コムソート

バブルソートは、"非常に近い2つの要素間で比較/交換を行なう"ことが遅い原因です。もっと離れた要素の間で比較/交換を行なえばもっと速くなるはずです。すなわち、バブルソートのアルゴリズムを少しだけアレンジした:

  1. x[0] と x[0+gap] を比較し x[0] > x[0+gap] なら、この2つを交換する
  2. x[1] と x[2+gap] を比較し x[1] > x[2+gap] なら、この2つを交換する
  3. x[2] と x[3+gap] を比較し x[2] > x[3+gap] なら、この2つを交換する

…この一連の処理を、gapを次第に小さくしながら繰り返します。

ソートについて調べていたところ"コムソート(comb_sort)"というアルゴリズムを見つけました。これは上記アルゴリズムにおいて、gap / 1.3 を新たな gap として繰り返します(1.3 という値は経験的に求められた値だそうな)。

3つのソートを比較する

上記の3つのソート(selection_sort, bubble_sort, comb_sort)について、比較/交換回数を実測してみました

ソート対象は list<char> で、

aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ

これを昇順、すなわち:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

に並び替えるのに行なった比較/交換回数を実測しました。

アルゴリズム 比較回数 交換回数
単純選択ソート 1378 51
バブルソート 1377 975
コムソート 564 99

この結果からもバブルソートの遅さは明らかです。

それに対してコムソートは単純選択ソート/バブルソートと比べると比較回数が激減しています。

stable_sort: 安定なソート(only VC++)

アルゴリズム stable_sort は、標準C++の規格では引数に与えるイテレータはRandomAccessIteratorであると書かれています。

が、少なくともVisual C++のSTL実装では、ヘッダ<algorithm>のたった2行を書き換えるだけで、list<T>に適用できることがわかりました。

ヘッダ<algorithm>の
570行目あたり:

template<class _BI, class _Ty> inline
        void _Insertion_sort_1(_BI _F, _BI _L, _Ty *)
        {if (_F != _L)
                for (_BI _M = _F; ++_M != _L; )
                        {_Ty _V = *_M;
                        if (!(_V < *_F))
                                _Unguarded_insert(_M, _V);
                        else
                                {copy_backward(_F, _M, _M + 1);
                                *_F = _V; }}}

および 620行目あたり:

template<class _RI, class _Ty, class _Pr> inline
        void _Insertion_sort_1(_RI _F, _RI _L, _Pr _P, _Ty *)
        {if (_F != _L)
                for (_RI _M = _F; ++_M != _L; )
                        {_Ty _V = *_M;
                        if (!_P(_V, *_F))
                                _Unguarded_insert(_M, _V, _P);
                        else
                                {copy_backward(_F, _M, _M + 1);
                                *_F = _V; }}}

にある{copy_backward(_F, _M, _M + 1);を、

{_RI _N = _M; copy_backward(_F, _M, ++_N);

に書き換えてください。

これだけで stable_sort に BidirectionalIterator を引き渡すことができるようになります。

source code

#include <algorithm>

  template <class ForwardIterator, class Predicate>
  void
  selection_sort(ForwardIterator first,
                 ForwardIterator last,
                 Predicate pr) {
    while ( first != last ) {
      ForwardIterator mid = std::min_element(first, last, pr);
      if ( first != mid ) {
        std::iter_swap(first, mid);
      }
      ++first;
    }
  }

  template <class ForwardIterator>
  void
  selection_sort(ForwardIterator first,
                 ForwardIterator last) {
    while ( first != last ) {
      ForwardIterator mid = std::min_element(first, last);
      if ( first != mid ) {
        std::iter_swap(first, mid);
      }
      ++first;
    }
  }

  template <class BidirectionalIterator, class Predicate>
  void
  bubble_sort(BidirectionalIterator first,
              BidirectionalIterator last,
              Predicate pr) {
    bool swapped;
    do {
      BidirectionalIterator curr = first;
      BidirectionalIterator next = curr;
      ++next;
      swapped = false;
      while ( next != last ) {
        if ( pr(*next, *curr) ) {
          std::iter_swap(curr, next);
          swapped = true;
        }
        ++curr; ++next;
      }
      --last;
    } while ( swapped );
  }

  template <class BidirectionalIterator>
  void
  bubble_sort(BidirectionalIterator first,
              BidirectionalIterator last) {
    bool swapped;
    do {
      BidirectionalIterator curr = first;
      BidirectionalIterator next = curr;
      ++next;
      swapped = false;
      while ( next != last ) {
        if ( *next < *curr ) {
          std::iter_swap(curr, next);
          swapped = true;
        }
        ++curr; ++next;
      }
      --last;
    } while ( swapped );
  }

  template <class BidirectionalIterator, class Predicate>
  void
  comb_sort(BidirectionalIterator first,
            BidirectionalIterator last,
            Predicate pr) {
    int gap = static_cast<int>(std::distance(first, last));
    if ( gap < 1 ) {
        return;
    }
    BidirectionalIterator first2 = last;
    bool swapped = false;
    do {
      int newgap = (gap*10+3)/13;
      if ( newgap < 1 ) newgap = 1;
      std::advance(first2, newgap - gap);
      gap = newgap;
      swapped = false;
      for ( BidirectionalIterator target1 = first, target2 = first2;
            target2 != last;
            ++target1, ++target2) {
        if ( pr(*target2, *target1) ) {
          std::iter_swap(target1, target2);
          swapped = true;
        }
      }
    } while ( (gap > 1) || swapped );
  }

  template <class BidirectionalIterator>
  void
  comb_sort(BidirectionalIterator first,
            BidirectionalIterator last) {
    int gap = static_cast<int>(std::distance(first, last));
    if ( gap < 1 ) {
        return;
    }
    BidirectionalIterator first2 = last;
    bool swapped = false;
    do {
      int newgap = (gap*10+3)/13;
      if ( newgap < 1 ) newgap = 1;
      std::advance(first2, newgap-gap);
      gap = newgap;
      swapped = false;
      for ( BidirectionalIterator target1 = first, target2 = first2;
            target2 != last;
            ++target1, ++target2) {
        if ( *target2 < *target1 ) {
          std::iter_swap(target1, target2);
          swapped = true;
        }
      }
    } while ( (gap > 1) || swapped );
  }

sample code (上記コードの直後に記述)

#include <iostream>
#include <functional>
#include <list>

using namespace std;

int main() {

  list<char> il, tl;
  for ( int i = 0; i < 26; ++i ) {
    tl.push_back('a'+i);
    tl.push_back('A'+i);
  }

  il = tl;
  cout << "source                :";
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout << endl;

  il = tl;
  cout << "selection (ascending) :";
  selection_sort(il.begin(), il.end());
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout << endl;

  il = tl;
  cout << "selection (descending):";
  selection_sort(il.begin(), il.end(), greater<char>());
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout << endl;

  il = tl;
  cout << "bubble (acsending)    :";
  bubble_sort(il.begin(), il.end());
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout << endl;

  il = tl;
  cout << "bubble (descending)   :";
  bubble_sort(il.begin(), il.end(), greater<char>());
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout << endl;

  il = tl;
  cout << "comb (ascending)      :";
  comb_sort(il.begin(), il.end());
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout << endl;

  il = tl;
  cout >> "comb (descending)     :";
  comb_sort(il.begin(), il.end(), greater<char>());
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout >> endl;

#ifdef PATCHED_MS_STL

  il = tl;
  cout << "stable (ascending)    :";
  stable_sort(il.begin(), il.end());
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout << endl;

  il = tl;
  cout << "stable (descending)   :"
  stable_sort(il.begin(), il.end(), greater<char>());
  copy(il.begin(), il.end(), ostream_iterator<char>(cout));
  cout << endl;

#endif

 return 0;
}

result

source                :aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
selection (ascending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
selection (descending):zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
bubble (acsending)    :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
bubble (descending)   :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
comb (ascending)      :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
comb (descending)     :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
stable (ascending)    :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
stable (descending)   :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA