0Pricing
C++ Academy · レッスン

ソートとパーティション：sort、stable_partition

std::sortとstd::stable_partitionでコンテナをソート・分割します。

「ソートとパーティション：sort、stable_partition」はCoddyKit上の無料C++ Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC++ Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C++ Academyコースには全4レッスンが含まれています。

std::sort

汎用的なソートアルゴリズムです。平均計算量は O(N log N) です。その場で実行され、安定ソートは保証されません。

#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascending

カスタム比較関数

比較関数（ラムダまたはファンクター）を渡すと、別の基準でソートできます。

std::sort(v.begin(), v.end(),
    [](int a, int b) { return a > b; });   // descending

カスタム型のソート

特定のメンバーを比較する比較関数を用意するか、その型に operator< を定義します。

struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.age < b.age; });

std::stable_sort

sort と同様ですが、等しい要素同士の相対的な順序を保持します。やや低速で、通常は追加メモリとして O(N log^2 N) が必要です。

std::partial_sort

最小の k 個の要素を先頭に配置してソートします。残りの要素の順序は未規定です。上位 k 個だけが必要な場合は、完全なソートより高速です。

std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sorted

std::nth_element

nth の位置の要素が、範囲全体をソートした場合の位置に来るように分割します。その前の要素はすべて nth 以下、その後の要素はすべて nth 以上になります。平均計算量は O(N) です。

std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest element

std::is_sorted

範囲がすでにソート済みかどうかを確認します。

if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "already sorted";
}

std::partition

述語を満たす要素が先頭に来るように範囲を並べ替えます。述語を満たさない最初の要素を指すイテレータを返します。安定ではありません。

std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });
// even numbers come first, then odd

std::stable_partition

partition と同様ですが、各グループ内の相対的な順序を保持します。

複数のキーによるソート

主キーを比較し、主キーが等しい場合は副キーを比較する比較関数を使用します。

std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    });

ソート済み範囲での二分探索

ソート後は、std::lower_bound、std::upper_bound、std::binary_search を使用して O(log N) で検索できます。

理解度チェック

ソート後も等しい要素同士の相対的な順序を保持するアルゴリズムはどれですか。

まとめ

一般的なソートには std::sort、等しい要素の順序が重要な場合には std::stable_sort、上位 k 個の抽出には std::partial_sort、要素の選択には std::nth_element、グループ分けには std::partition/std::stable_partition を使用します。

よくある質問

「ソートとパーティション：sort、stable_partition」レッスンは無料ですか？

はい。「ソートとパーティション：sort、stable_partition」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C++ Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C++ Academyコースには全4レッスンが含まれています。

「ソートとパーティション：sort、stable_partition」で何を学びますか？

std::sortとstd::stable_partitionでコンテナをソート・分割します。 ブラウザで直接実行するハンズオンコードでC++ Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C++ Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC++ Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「ソートとパーティション：sort、stable_partition」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC++ Academyレッスンでコードを書いて実行できますか？

はい。すべてのC++ Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 非変更アルゴリズム：find、count、all_of
  2. 変更アルゴリズム：transform、copy_if、replace
  3. ソートとパーティション：sort、stable_partition
  4. 数値アルゴリズム：accumulate、reduce、transform_reduce
← C++ Academyに戻る