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: 単純選択ソート
単純選択ソートのアルゴリズムは非常に単純です。
- x[0] .. x[N-1] の中から最小の要素 x[i] を見つけ、それと x[0] を交換する
- x[1] .. x[N-1] の中から最小の要素 x[i] を見つけ、それと x[1] を交換する
- x[2] .. x[N-1] の中から最小の要素 x[i] を見つけ、それと x[2] を交換する
…これをN回繰り返せばソート完了です。
要素の比較回数はN2に比例し、交換回数はNに比例します。
buble_sort: バブルソート
最も有名かつ最も遅いソートです。
- x[0] と x[1] を比較し x[0] > x[1] なら、この2つを交換する
- x[1] と x[2] を比較し x[1] > x[2] なら、この2つを交換する
- x[2] と x[3] を比較し x[2] > x[3] なら、この2つを交換する
…これをN回繰り返すと、X[N-1]には最大要素が格納されることになります。
そしてこの一連の処理の中で一度でも交換が行なわれたら最大要素を除く(要素数はひとつ少ない)列に対し再度繰り返します。
要素の比較回数/交換回数共にN2に比例します。
comb_sort: コムソート
バブルソートは、"非常に近い2つの要素間で比較/交換を行なう"ことが遅い原因です。もっと離れた要素の間で比較/交換を行なえばもっと速くなるはずです。すなわち、バブルソートのアルゴリズムを少しだけアレンジした:
- x[0] と x[0+gap] を比較し x[0] > x[0+gap] なら、この2つを交換する
- x[1] と x[2+gap] を比較し x[1] > x[2+gap] なら、この2つを交換する
- 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