第54回ソート系アルゴリズム ★目玉

<algorithm> のソート関連関数を用途別に整理。全体ソート、安定ソート、部分ソート、k 番目だけ確定、ソート済み判定、分割。ラムダと組み合わせて自作30行を1行に圧縮する威力を見ます。

このページで押さえること

✅ 最低限ここだけ覚える

std::sort ― 全体ソート（既定）
std::stable_sort ― 同順位の順を保つ
std::partial_sort ― トップ N だけ
std::nth_element ― N 番目だけ正しい位置に

⭐ 余裕があれば読む

std::is_sorted / is_sorted_until
std::partition / stable_partition
比較関数のカスタマイズ（ラムダ）
計算量の違い

1. 一覧表

関数	用途	計算量
`std::sort`	全体を並べ替え（既定）	O(n log n)
`std::stable_sort`	同順位の相対順序を保つソート	O(n log² n) または O(n log n)
`std::partial_sort`	先頭 k 個だけソート（残りは未定順）	O(n log k)
`std::nth_element`	k 番目の要素だけ正しい位置に	O(n) 平均
`std::is_sorted`	ソート済みか判定	O(n)
`std::partition`	述語で 2 つに分ける	O(n)

2. std::sort ― 全体ソート

基本と降順sort

std::vector<int> v = {5, 2, 8, 1, 9}; std::sort(v.begin(), v.end()); // {1, 2, 5, 8, 9} std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; }); // {9, 8, 5, 2, 1} // 構造体の特定フィールドでソート struct User { std::string name; int age; }; std::vector<User> us; std::sort(us.begin(), us.end(), [](auto& a, auto& b){ return a.age < b.age; });

3. stable_sort ― 同順位の順を保つ

点数でソートするが、同じ点数なら入力順を保ちたい、という場合。

安定ソートstable

std::vector<std::pair<int, std::string>> v = { {90, "Alice"}, {80, "Bob"}, {90, "Carol"} }; std::stable_sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.first > b.first; }); // {{90,Alice}, {90,Carol}, {80,Bob}} ← Alice と Carol の順が維持される // std::sort を使うと同点の順序が保証されない

4. partial_sort / nth_element ― 部分的な整列

partial_sortトップ K

std::vector<int> v = {5,2,8,1,9,3,7}; std::partial_sort( v.begin(), v.begin() + 3, v.end()); // 先頭 3 個だけソート // [1, 2, 3, ...] (残りは未定順)

nth_elementk 番目のみ

std::vector<int> v = {5,2,8,1,9,3,7}; size_t k = v.size() / 2; std::nth_element( v.begin(), v.begin() + k, v.end()); // v[k] が中央値（の位置）になる // 他の要素は未定順だが、k より小は左に

使い分け：

トップ 10 だけ表示したい → partial_sort
中央値／パーセンタイルを一発で → nth_element
全部並べる必要がない → sort より高速

5. partition / stable_partition

条件で 2 分割partition

std::vector<int> v = {1,2,3,4,5,6}; auto mid = std::partition(v.begin(), v.end(), [](int x){ return x % 2 == 0; }); // 偶数が前、奇数が後（順序は保証されない） // [2, 4, 6 | 1, 3, 5] など // mid は仕切り位置のイテレータ // 順序を保ちたければ stable_partition

⭐

ここまででソート系は OK

次章は探索系（find / binary_search / lower_bound）。

6. 実行可能デモ

▶ アルゴリズムを切り替えて結果を見る

v = {5, 2, 8, 1, 9, 3, 7, 4, 6}

確認クイズ

ソート系を 4 問で確認。

Q1. 同じ値の要素の入力順を保ちたいソートは？

std::sort

std::stable_sort

std::partial_sort

std::nth_element

std::sort は不安定、stable_sort は安定（同順位の相対順序を保つ）。

Q2. 配列から最大の 3 個だけ取り出したい。使うアルゴリズムは？

sort 全体

partial_sort または nth_element

stable_sort

partition

全ソートは無駄。partial_sort なら先頭 3 個だけ正確に、他は未定順。nth_element ならさらに速く（ただし先頭 3 個も未定順）。

Q3. std::sort の平均計算量は？

O(n)

O(n log n)

O(n²)

O(log n)

規格で O(n log n) が要求され、多くの実装は introsort で最悪も O(n log n)。

Q4. 配列を「偶数」と「奇数」に分けたい（順序は問わない）。

sort