[解決済み】古典的なソートアルゴリズムを最新のC++で実装する方法とは？

質問

質問 std::sort アルゴリズム (およびその同系列の std::partial_sort と std::nth_element ) は、C++ 標準ライブラリのほとんどの実装で より初歩的なソートアルゴリズムの複雑で混成されたものです。 選択ソート、挿入ソート、クイックソート、マージソート、ヒープソートのような、より初歩的なソートアルゴリズムの複雑なハイブリッドです。

ここや次のような姉妹サイトには、多くの質問があります。 https://codereview.stackexchange.com/ などで、これらの古典的なソートアルゴリズムの実装のバグ、複雑さ、および他の側面に関する多くの質問があります。提供された実装のほとんどは、生のループで構成され、インデックス操作と具象型を使用し、一般に、正しさと効率性の観点から分析することは自明ではありません。

質問 上記の古典的なソートアルゴリズムは、最新のC++を使用してどのように実装することができますか？

• 生のループはありません。 しかし、標準ライブラリのアルゴリズム構成要素である <algorithm>
• イテレータインターフェース を使用し テンプレート インデックス操作や具象型の代わりに
• C++14スタイル のような構文的なノイズを軽減するものだけでなく、完全な標準ライブラリを含む auto テンプレートエイリアス、透過型コンパレータ、ポリモーフィックラムダなどです。

注意事項 :

• ソートアルゴリズムの実装に関するさらなる参考文献は ウィキペディア , ロゼッタコード または http://www.sorting-algorithms.com/
• によると ショーン・ペアレントの規約 (スライド39)にあるように、生のループは for -ループです。つまり f(g(x)); または f(x); g(x); または f(x) + g(x); のループは生のループではありません。 selection_sort と insertion_sort 以下になります。
• 私は Scott Meyers の用語法に従って、現在の C++1y をすでに C++14 と表記し、C++98 と C++03 の両方を C++98 と表記しているので、そのことで私を非難するのはやめてください。
• Mehrdad 氏のコメントで提案されたように、私は回答の最後に Live Example として 4 つの実装を提供しています。C++14、C++11、C++98、および Boost と C++98 です。
• 回答自体は、C++14 の観点からのみ提示されています。関連する場合、さまざまな言語バージョンが異なる場合、構文およびライブラリの違いを示しています。

どのように解決するのですか?

アルゴリズムの構成要素

まず、標準ライブラリからアルゴリズムのビルディングブロックを組み立てることから始めます。

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

• 非メンバーなどのイテレータツール std::begin() / std::end() と同様に std::next() は、C++11以降でのみ利用可能です。C++98では、自分で書く必要があります。Boost.Rangeの代用品として boost::begin() / boost::end() で、Boost.Utility からは boost::next() .
• は std::is_sorted アルゴリズムは、C++11 以降で利用可能です。C++98 では、これを実装するために std::adjacent_find と手書きの関数オブジェクトで実装できます。また、Boost.Algorithmは、C++11以降では boost::algorithm::is_sorted を代用することができます。
• は std::is_heap アルゴリズムは、C++11 以降で利用可能です。

構文上の利点

C++14 では 透明な比較演算子 フォームの std::less<> といった形で、引数に対して多義的に作用するものです。これにより、イテレータの型を提供する必要がなくなります。これは、C++11の デフォルトの関数テンプレート引数 を作成します。 単一のオーバーロード を取るソートアルゴリズムに対して < を比較とするソートアルゴリズムと、 ユーザ定義の比較関数オブジェクトを持つソートアルゴリズムのための、 一つのオーバーロードです。

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

C++11では、再利用可能な テンプレートエイリアス を使ってイテレータの値の型を抽出することができます。これはソートアルゴリズムの署名に小さな混乱を追加します。

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

C++98では、2つのオーバーロードを書く必要があり、冗長な typename xxx<yyy>::type 構文

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

• もう 1 つの構文的な利点は、C++14 ではユーザー定義の比較演算子のラップが ポリモーフィック ラムダ (でラップすることができます（ただし auto パラメータは関数テンプレートの引数のように推論されます)。
• C++11 には単相ラムダのみがあり、上記のテンプレート エイリアスを使用する必要があります。 value_type_t .
• C++98では、スタンドアロン関数オブジェクトを書くか、冗長な std::bind1st / std::bind2nd / std::not1 のようなタイプの構文です。
• Boost.Bindはこれを改善するために boost::bind と _1 / _2 プレースホルダー構文。
• C++11 以降では std::find_if_not が必要なのに対し、C++98 では std::find_if を使用し std::not1 を関数オブジェクトの周囲に置く。

C++スタイル

一般に受け入れられる C++14 のスタイルはまだありません。良くも悪くも、私は Scott Meyers の ドラフト Effective Modern C++ と Herb Sutter の を刷新した GotW . 私は以下のスタイル勧告を使用しています。

• ハーブ・サッターの "Almost Always Auto" とスコット・マイヤーズの "Prefer auto to specific type declarations" という勧告があり、その簡潔さは比類がありませんが、その明快さは時に 論争になる .
• スコット・マイヤーズの と () オブジェクトを作成するとき"。 で、一貫して中括弧付きの初期化を選択します。 {} の代わりに中括弧で囲まれた初期化を使用します。 {} (一般的なコードで最もvexing-parseな問題をすべて横取りするために)。
• Scott Meyers の "Prefer alias declarations to typedefs" . テンプレートでは、これはとにかく必須で、あらゆるところで () の代わりにあらゆる場所で使用することで、時間を節約し、一貫性を持たせることができます。
• を使うのは typedef パターンを使っていますが、これはすでにソートされたサブレンジの ループ不変性チェックを可能にするためです。実運用コードでは for (auto it = first; it != last; ++it) と while (first != last) をループの内側のどこかで使用すると、少し良くなるかもしれません。

選択ソート

選択ソート はデータに一切適応しないので、その実行時間は常に ++first . しかし、選択ソートは スワップ回数を最小にする . アイテムを交換するコストが高いアプリケーションでは、選択ソートは非常によく、選択アルゴリズムであるかもしれません。

標準ライブラリを使って実装するには、繰り返し O(N²) で残りの最小要素を探し std::min_element を使って所定の位置に入れ替えます。

iter_swap

なお template<class FwdIt, class Compare = std::less<>> void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { for (auto it = first; it != last; ++it) { auto const selection = std::min_element(it, last, cmp); std::iter_swap(selection, it); assert(std::is_sorted(first, std::next(it), cmp)); } } は、すでに処理された範囲 selection_sort をループ不変量としてソートする。最小限の要件は 前方イテレータ と比較して [first, it) のランダムアクセスイテレータと比較して

詳細省略 :

• 選択ソートは早期テストで最適化できる std::sort (あるいは、前方/双方向イテレータのために if (std::distance(first, last) <= 1) return; ).
• については 双方向イテレータ である場合、上記のテストは区間上のループと組み合わせることができます。 if (first == last || std::next(first) == last) return; 最後の要素は最小の残りの要素であることが保証され、入れ替えを必要としないためです。

挿入ソート

という初歩的なソートアルゴリズムのひとつですが [first, std::prev(last)) の最悪時間です。 挿入ソート は、データがほぼソートされているときに選択されるアルゴリズムです（なぜなら、それは 適応的 であるため）、あるいは問題サイズが小さい場合（オーバーヘッドが小さいため）に選択されるアルゴリズムです。これらの理由と、また 安定 であるため、挿入ソートはしばしば、マージソートやクイックソートなどの高オーバーヘッドの分割統治型ソートアルゴリズムの再帰的ベースケースとして（問題サイズが小さいときに）使用される。

実装方法 O(N²) を標準ライブラリで実装するには、繰り返し insertion_sort を使って現在の要素が行く必要のある場所を見つけ std::upper_bound を使って残りの要素を入力範囲の上方に移動させます。

std::rotate

なお template<class FwdIt, class Compare = std::less<>> void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { for (auto it = first; it != last; ++it) { auto const insertion = std::upper_bound(first, it, *it, cmp); std::rotate(insertion, it, std::next(it)); assert(std::is_sorted(first, std::next(it), cmp)); } } は、すでに処理された範囲 insertion_sort をループ不変量としてソートします。挿入ソートは前方イテレータでも動作します。

詳細省略 :

• 挿入ソートは早期テストで最適化できる [first, it) (あるいは、前方/双方向イテレータのために if (std::distance(first, last) <= 1) return; ) と区間をループする if (first == last || std::next(first) == last) return; というのは、最初の要素は所定の位置にあることが保証されており、ローテートを必要としないためです。
• については 双方向イテレータ の場合、挿入点を見つけるためのバイナリサーチは 逆線形探索 を使うことで、標準ライブラリの [std::next(first), last) アルゴリズムを使っています。

4つの ライブの例 ( C++14 , C++11 , C++98 と Boost , C++98 ) を使って、以下のような断片を作成します。

std::find_if_not

• ランダム入力の場合、次のようになります。 using RevIt = std::reverse_iterator<BiDirIt>; auto const insertion = std::find_if_not(RevIt(it), RevIt(first), [=](auto const& elem){ return cmp(*it, elem); } ).base(); という比較になりますが、これが O(N²) の比較に改善される。バイナリサーチは常に O(N) 比較を使用します。
• 小さな入力範囲では、線形探索のより良いメモリ局所性 (キャッシュ、プリフェッチ) はバイナリ探索を支配するかもしれません (もちろん、これをテストする必要があります)。

クイックソート

丁寧に実装すると クイックソート は堅牢で O(N log N) が期待される複雑さを持っていますが O(N log N) の複雑さを持つことになります。安定したソートが必要でない場合、クイックソートは優れた汎用ソートです。

最も単純なバージョンであっても、クイックソートは、他の古典的なソートアルゴリズムよりも標準ライブラリを使用して実装することがかなり複雑です。以下のアプローチでは、いくつかのイテレータユーティリティを使って 中間要素 入力範囲の O(N²) をピボットとし、2回の呼び出しで [first, last) (を呼び出します（これは std::partition ) を用いて，入力範囲を選択されたピボットより小さい要素，等しい要素，大きい要素にそれぞれ三分割します．最後に、ピボットより小さい要素と大きい要素を持つ外側の2つのセグメントが再帰的にソートされます。

O(N)

しかし、クイックソートは、上記の各ステップを慎重にチェックし、プロダクションレベルのコードに最適化する必要があるため、正しく効率的に行うのはかなり難しいです。特に template<class FwdIt, class Compare = std::less<>> void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { auto const N = std::distance(first, last); if (N <= 1) return; auto const pivot = *std::next(first, N / 2); auto const middle1 = std::partition(first, last, [=](auto const& elem){ return cmp(elem, pivot); }); auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ return !cmp(pivot, elem); }); quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp)); quick_sort(middle2, last, cmp); // assert(std::is_sorted(middle2, last, cmp)); } の場合、ピボットは入力データをバランスよく分割する必要があります。 O(N log N) の場合は一般に保証されませんが、 ピボットを O(1) を入力範囲の中央値として設定すれば保証されます。

詳細省略 :

• 上記の実装は、特殊な入力に対して特に脆弱です。例えば、この実装には O(N) に対して複雑で、" オルガンパイプ 入力 O(N^2) (真ん中は常に他のすべての要素より大きいため)。
• 中央値-3 からのピボット選択 ランダムに選ばれた要素 に悪化してしまうような、ほとんどソートされた入力に対して、入力範囲からガードします。 1, 2, 3, ..., N/2, ... 3, 2, 1 .
• 3ウェイパーティショニング の2つの呼び出しで示されるように、(ピボットより小さい要素、等しい要素、大きい要素を分離する) O(N^2) は最も効率的ではない std::partition アルゴリズムは、この結果を達成するために最も効率的ではありません。
• については ランダムアクセスイテレータ の場合、保証された O(N) により、複雑さを保証することができます。 中央ピボット選択 を使うことで O(N log N) という再帰的な呼び出しが続きます。 std::nth_element(first, middle, last) と quick_sort(first, middle, cmp) .
• の定数ファクターが小さくなるため、この保証には代償が伴います。 quick_sort(middle, last, cmp) の複雑さは O(N) よりも高くなることがあります。 std::nth_element の場合、中央値-3 ピボットに続く O(1) への呼び出し O(N) を呼び出します (これはデータに対するキャッシュフレンドリーなシングルフォワードパスです)。

マージソート

もし std::partition を使っても問題ないのであれば マージソート は素晴らしい選択です：それは唯一の 安定した O(N) ソートアルゴリズムです。

標準アルゴリズムを使って実装するのは簡単です。いくつかのイテレータユーティリティを使って、入力範囲の中央を見つけることができます。 O(N log N) で再帰的にソートされた 2 つのセグメントを組み合わせます。 [first, last) :

std::inplace_merge

マージソートは双方向のイテレータを必要としますが、そのボトルネックとなるのが template<class BiDirIt, class Compare = std::less<>> void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{}) { auto const N = std::distance(first, last); if (N <= 1) return; auto const middle = std::next(first, N / 2); merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp)); merge_sort(middle, last, cmp); // assert(std::is_sorted(middle, last, cmp)); std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp)); } . リンクリストをソートする場合、マージソートで必要なのは std::inplace_merge のスペースしか必要としないことに注意してください（再帰のため）。後者のアルゴリズムは O(log N) によって標準ライブラリに実装されています。

ヒープソート

ヒープソート は実装が簡単で std::list<T>::sort を実行しますが、安定ではありません。

最初のループは O(N log N) heapify"フェーズでは、配列をヒープ順序に並べます。2番目のループである O(N) ) "sortdown" フェーズでは、繰り返し最大値を抽出し、ヒープ順序を復元します。標準ライブラリはこれを非常に簡単にしてくれます。

O(N log N

を使うのはズルイと思うかもしれません。 template<class RandomIt, class Compare = std::less<>> void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{}) { lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp)); lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp)); } と std::make_heap のような関数であれば、一段深く掘り下げて、自分で std::sort_heap と std::push_heap のように、それぞれ

std::pop_heap

標準ライブラリでは namespace lib { // NOTE: is O(N log N), not O(N) as std::make_heap template<class RandomIt, class Compare = std::less<>> void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{}) { for (auto it = first; it != last;) { std::push_heap(first, ++it, cmp); assert(std::is_heap(first, it, cmp)); } } template<class RandomIt, class Compare = std::less<>> void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{}) { for (auto it = last; it != first;) { std::pop_heap(first, it--, cmp); assert(std::is_heap(first, it, cmp)); } } } // namespace lib と push_heap を複雑化すると pop_heap . しかし、外側のループが範囲 O(log N) の結果 [first, last) の複雑さは O(N log N) であるのに対し make_heap には std::make_heap のみの複雑さです。全体としては O(N) の複雑さは O(N log N) は重要ではありません。

詳細省略 : heap_sort の実装 O(N)

テスト

ここでは、4つの ライブの例 ( C++14 , C++11 , C++98 と Boost , C++98 ) は、さまざまな入力で 5 つのアルゴリズムすべてをテストしています (網羅的または厳密であることを意図していません)。C++11/C++14 は約 130 LOC、C++98 と Boost は 190 (+50%) 、C++98 は 270 以上 (+100%) を必要とします。