古典的なソートアルゴリズムを現代の C++ で実装するにはどうすればよいでしょうか? 質問する

ただし、クイック ソートは、上記の各ステップを慎重にチェックし、実稼働レベルのコードに合わせて最適化する必要があるため、正確かつ効率的に行うのがかなり難しいです。特に、O(N log N)複雑さに関しては、ピボットは入力データのバランスの取れたパーティションになる必要がありますが、これは一般にピボットでは保証できませんが、ピボットを入力範囲の中央値O(1)として設定すれば保証できます。O(N)

詳細は省略：

• O(N^2)上記の実装は、特殊な入力に対して特に脆弱です。たとえば、 「オルガンパイプ」入力に対しては複雑になります1, 2, 3, ..., N/2, ... 3, 2, 1(中央の要素が常に他のすべての要素よりも大きいため)。
• 3 の中央値ピボットの選択ランダムに選択された要素入力範囲から、複雑性が に低下することになるほぼソートされた入力から保護しますO(N^2)。
• 3ウェイパーティショニング(ピボットより小さい、等しい、大きい要素を分離する) は、 の 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)の複雑さの定数係数は、の呼び出し(これは、データに対するキャッシュ フレンドリーな単一のフォワード パスです)が続く 3 の中央値ピボットの複雑さstd::nth_elementの定数係数よりもコストがかかる可能性があるからです。O(1)O(N)std::partition

マージソート

余分なスペースを使うことにO(N)問題がなければ、マージソートは優れた選択肢です。これは唯一の安定した O(N log N)ソートアルゴリズムです。

標準アルゴリズムを使用して実装するのは簡単です。いくつかの反復ユーティリティを使用して入力範囲の中央を見つけ[first, last)、再帰的にソートされた 2 つのセグメントを次のように結合します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));
}

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));
}

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