C++でデータを並び替える場合、基本的には標準ライブラリに用意されているソート機能を使います。
数値の小さい順・大きい順だけでなく、文字列、配列、複数の値を持つデータ、構造体やクラスのような独自データもソートできます。
C++のソートで特に重要なのは、「どの順番で並べたいのか」を明確にすることです。
単純な数値の昇順であれば簡単ですが、実務では「点数が高い順」「価格が安い順」「日付が新しい順」「同じ点数なら名前順」といった複数条件のソートもよく使われます。
C++でソートするときの基本的な考え方
C++のソートでは、データの先頭から最後までの範囲を指定して並び替えます。
たとえば、配列やリストのようなデータの集合に対して、「この範囲を小さい順に並べる」「この範囲を大きい順に並べる」といった形で指定します。
C++では、デフォルトでは昇順、つまり小さいものから大きいものへ並べるのが基本です。
数値であれば小さい順、文字列であれば文字コードに基づいた順番、複数の値を持つデータであれば最初の値から順番に比較されます。
昇順ソートとは
昇順ソートとは、小さい値から大きい値へ並べることです。
たとえば、次のような数値があるとします。
5、2、9、1、7
これを昇順にソートすると、次のようになります。
1、2、5、7、9
C++の標準的なソートでは、特に条件を指定しなければ基本的に昇順になります。
そのため、単純に数値を小さい順に並べたい場合は、特別な比較条件を用意しなくても問題ありません。
降順ソートとは
降順ソートとは、大きい値から小さい値へ並べることです。
たとえば、次のような数値があるとします。
5、2、9、1、7
これを降順にソートすると、次のようになります。
9、7、5、2、1
降順にしたい場合は、「大きいものを前に置く」という比較ルールを指定します。
昇順とは逆の順番に並べるため、単純なソートとは別に条件を指定する必要があります。
配列のソート
C++では、通常の配列もソートできます。
配列をソートする場合は、配列の先頭と末尾を指定して並べ替えます。
数値配列であれば、小さい順や大きい順に並べることができます。
たとえば、次のような配列があるとします。
5、1、4、2、3
昇順にソートすると、次のようになります。
1、2、3、4、5
配列の場合、要素数を正しく把握しておくことが重要です。
範囲の指定を間違えると、意図しない部分までソートしたり、逆に一部しかソートされなかったりする可能性があります。
vectorのソート
C++でデータを扱うときは、配列よりも vector を使う場面が多いです。
vector は要素数を柔軟に増減できるため、実務や競技プログラミングでもよく使われます。
vector のソートでは、先頭から最後までの範囲を指定して並び替えます。
整数の vector なら数値順、文字列の vector なら文字列順に並べることができます。
特に初心者のうちは、配列よりも vector を使ったソートから覚えると理解しやすいです。
文字列のソート
文字列もソートできます。
ただし、文字列をソートする場合には2つの意味があります。
文字列そのものの中の文字を並べ替える場合
たとえば、dbca という文字列がある場合、文字単位で並び替えると abcd のようになります。
これは、文字列を1文字ずつ見て、文字の順番に並べ替える処理です。
複数の文字列を並べ替える場合
たとえば、複数の名前や単語をリストとして持っている場合、それらを辞書順のように並べ替えることもできます。
ただし、C++の標準的な文字列比較は、人間が考える自然な辞書順と完全に同じとは限りません。
特に、大文字と小文字が混ざる場合、日本語を含む場合、ロケールを考慮する場合には注意が必要です。
英数字だけの単純なソートであれば、標準機能で十分対応できます。
pairのソート
C++では、2つの値をセットで扱う pair というデータ型があります。
pair をソートする場合、基本的には1つ目の値を基準に並べます。
1つ目の値が同じ場合は、2つ目の値を見て順番を決めます。
たとえば、次のようなデータがあるとします。
- 2, 3
- 1, 5
- 2, 1
- 1, 2
これを標準的にソートすると、次のような順番になります。
- 1, 2
- 1, 5
- 2, 1
- 2, 3
このように、まず1つ目の値で比較し、同じ場合に2つ目の値で比較する方式を「辞書順」と考えると分かりやすいです。
構造体やクラスのソート
実務では、単なる数値や文字列だけでなく、複数の情報を持つデータをソートすることがよくあります。
たとえば、学生データであれば、名前と点数を持っているかもしれません。
商品データであれば、商品名、価格、在庫数、登録日などを持っているかもしれません。
このようなデータをソートする場合は、「どの項目を基準に並べるか」を指定する必要があります。
点数順に並べる場合
学生データを点数の低い順に並べたい場合は、点数を基準に昇順でソートします。
一方、成績ランキングのように点数が高い順に並べたい場合は、点数を基準に降順でソートします。
価格順に並べる場合
商品データを扱う場合、価格の安い順や高い順に並べることがあります。
ECサイトの商品一覧であれば、「価格が安い順」「価格が高い順」「新着順」「人気順」といった並び替えがよくあります。
これらも基本的には、どの項目を基準にするかを決めてソートしているだけです。
複数条件でソートする方法
ソートでは、1つの条件だけでなく複数の条件を組み合わせることもできます。
たとえば、学生データを次の条件で並べたいとします。
まず点数が高い順に並べる。
点数が同じ場合は、名前の順に並べる。
このような場合は、最初に点数を比較します。
点数が違えば、点数の高い方を前に置きます。
点数が同じであれば、次に名前を比較して順番を決めます。
複数条件ソートの考え方
複数条件ソートでは、優先順位が重要です。
たとえば、次のような条件があるとします。
1番目の条件は、点数が高い順。
2番目の条件は、名前が辞書順。
3番目の条件は、年齢が若い順。
この場合、まず点数を見ます。
点数が違えば、そこで順番が決まります。
点数が同じ場合だけ、名前を見ます。
名前も同じ場合だけ、年齢を見ます。
つまり、上から順番に条件を確認していき、違いが見つかったところで順番を決めるという考え方です。
比較関数の考え方
C++のソートで非常に重要なのが、比較関数の考え方です。
比較関数とは、「2つのデータを比べたとき、どちらを前に置くべきか」を決めるルールです。
たとえば、昇順であれば、小さい方を前に置きます。
降順であれば、大きい方を前に置きます。
この考え方を理解しておくと、構造体や複数条件のソートも分かりやすくなります。
比較関数でやってはいけないこと
比較関数では、「小さいか等しい」「大きいか等しい」という条件を使わないようにする必要があります。
つまり、同じ値同士を比較したときに、「前に置くべき」と判断してはいけません。
同じ値であれば、どちらが前であるべきかは比較関数としては決めない、という扱いにします。
これを守らないと、ソートのルールが矛盾して、正しく並び替えられない可能性があります。
C++のソートでは、比較ルールが一貫していることが非常に重要です。
安定ソートとは
通常のソートでは、同じ値を持つデータの元の順番が保たれるとは限りません。
たとえば、次のような学生データがあるとします。
- Alice、90点
- Bob、80点
- Charlie、90点
- David、80点
これを点数が高い順にソートしたとき、Alice と Charlie はどちらも90点です。
通常のソートでは、Alice と Charlie の元の順番が保たれるとは限りません。
一方、安定ソートを使うと、同じ点数のデータについては元の順番が維持されます。
この場合、90点の中では Alice が先、Charlie が後のままになります。
80点の中でも Bob が先、David が後のままになります。
安定ソートを使うべき場面
安定ソートは、同じ値を持つデータの順番に意味がある場合に使います。
たとえば、先に登録されたデータを優先したい場合や、すでに別の条件で並び替えた結果を維持したい場合に便利です。
ただし、安定ソートは通常のソートより追加のメモリを使う場合があります。
そのため、同じ値の順番を保つ必要がない場合は、通常のソートで十分です。
一部だけソートする方法
C++では、データ全体ではなく一部だけをソートすることもできます。
たとえば、6個のデータがあるうち、2番目から4番目までだけを並べ替える、といったことが可能です。
この場合、ソート対象の範囲を正しく指定する必要があります。
C++の範囲指定では、終了位置そのものは含まれません。
つまり、「ここからここまで」と指定したとき、最後に指定した位置の直前までが対象になります。
この考え方は少し慣れが必要ですが、C++の多くの標準ライブラリで共通して使われる重要なルールです。
上位N件だけを取り出すソート
すべてのデータを完全に並べ替える必要がない場合もあります。
たとえば、100万人分のデータから上位10件だけ欲しい場合、全体を完全にソートするのは無駄が多いことがあります。
このような場合には、上位N件だけを効率よく取り出す方法があります。
上位N件だけ並べる場合
上位N件だけを正しく並べたい場合は、部分的なソートを使います。
たとえば、点数が高い上位3人だけを知りたい場合、先頭3件だけを正しく並べ、それ以降のデータは完全には並べ替えないという処理ができます。
この方法を使うと、全体を完全にソートするより効率的になることがあります。
ただし、注意点があります。
上位N件は正しく並びますが、それ以外の部分は完全にはソートされません。
そのため、全体がきれいに並んでいると思って使うと間違いになります。
N番目の要素だけを知りたい場合
「3番目に大きい値だけ知りたい」「中央値だけ知りたい」といった場合、全体をソートする必要はありません。
このような場合は、指定した位置に来る要素だけを効率よく求める方法があります。
たとえば、完全にソートしたときに3番目に来る値を知りたい場合、その値だけを正しい位置に置く処理を行います。
N番目だけを求める方法の注意点
この方法では、N番目の要素は正しく求められます。
しかし、データ全体が完全にソートされるわけではありません。
N番目より前には、それより優先順位の高い要素が集まります。
N番目より後ろには、それより優先順位の低い要素が集まります。
ただし、それぞれの内部順序はバラバラです。
つまり、「N番目の値だけ知りたい」ときには便利ですが、「全体を順番に表示したい」ときには通常のソートを使う必要があります。
sortとstable_sortの違い
C++でよく使うソートには、通常のソートと安定ソートがあります。
通常のソートは、基本的に高速で、最もよく使われます。
単純にデータを並び替えたいだけなら、通常のソートで十分です。
一方、安定ソートは、同じ値を持つデータの元の順番を保ちます。
同点の人の順番や、同じ価格の商品に対する登録順などを維持したい場合に使います。
通常のソートが向いている場面
通常のソートは、単純に順番だけ整えたい場合に向いています。
たとえば、数値を小さい順に並べる、商品を価格順に並べる、日付を新しい順に並べるといったケースです。
同じ値のデータ同士の順番に意味がないなら、通常のソートで問題ありません。
安定ソートが向いている場面
安定ソートは、同じ値のデータの順番にも意味がある場合に向いています。
たとえば、点数順に並べたとき、同じ点数なら入力順を維持したい場合です。
また、すでに別の条件で並べたあと、さらに別の条件でソートしたい場合にも使われます。
partial_sortとnth_elementの違い
上位N件を扱う場合、部分的なソートとN番目の要素を求める方法は似ていますが、目的が違います。
partial_sortが向いている場面
上位N件を順番付きで欲しい場合に向いています。
たとえば、売上上位10商品を1位から10位まで順番に表示したい場合です。
この場合、上位10件は正しく並んでいる必要があります。
そのため、部分的なソートが適しています。
nth_elementが向いている場面
N番目の値だけを知りたい場合に向いています。
たとえば、100万人のスコアから中央値だけを知りたい場合や、3番目に大きい値だけを知りたい場合です。
この場合、上位の要素を完全に順番通りに並べる必要はありません。
そのため、N番目の要素だけを確定させる方法の方が効率的です。
実務でよくあるソートの例
C++のソートは、実務でも幅広く使われます。
商品データのソート
ECサイトや在庫管理システムでは、商品データをソートする場面が多くあります。
たとえば、次のような並び替えです。
- 価格が安い順。
- 価格が高い順。
- 在庫数が多い順。
- 登録日が新しい順。
- 売上数が多い順。
このような処理は、すべて「どの項目を基準に並べるか」を決めることで実現できます。
ユーザーデータのソート
ユーザー情報を扱う場合も、ソートはよく使われます。
たとえば、登録日が新しい順、最終ログイン日が新しい順、購入回数が多い順、スコアが高い順などです。
複数条件のソートもよく使われます。
たとえば、会員ランクが高い順に並べ、同じランクなら購入金額が高い順に並べる、といった処理です。
ランキングデータのソート
ゲーム、テスト、売上、アクセス数などのランキングでもソートは重要です。
ランキングでは、単純にスコアが高い順に並べるだけでなく、同点の場合の扱いも考える必要があります。
同点なら登録順を優先するのか、名前順にするのか、達成日時が早い方を上にするのか、といったルールを決めておくことが大切です。
ソートでよくあるミス
C++のソートでは、初心者がつまずきやすいポイントがあります。
比較条件に等号を入れてしまう
最もよくあるミスの1つが、比較条件に等号を入れてしまうことです。
昇順なら「小さい場合」、降順なら「大きい場合」を条件にします。
「小さいか等しい」「大きいか等しい」という条件にすると、同じ値同士の比較で矛盾が起きる可能性があります。
これはソート結果が不安定になる原因になるため、避けるべきです。
範囲指定を間違える
C++のソートでは、開始位置と終了位置を指定します。
このとき、終了位置はソート対象に含まれません。
このルールを理解していないと、思ったより1つ少ない範囲だけがソートされたり、逆に意図しない範囲を指定してしまったりします。
全体がソートされたと勘違いする
部分的なソートやN番目の要素を求める処理では、全体が完全にソートされるわけではありません。
上位N件だけ、またはN番目の要素だけが正しく処理されます。
全体を順番に表示したい場合は、通常のソートを使う必要があります。
安定ソートと通常ソートを混同する
通常のソートでは、同じ値の元の順番は保証されません。
同じ値の順番を維持したい場合は、安定ソートを使う必要があります。
この違いを理解していないと、同点のデータの並び順が想定と変わることがあります。
C++のソートで押さえるべき重要ポイント
C++のソートを正しく使うには、次のポイントを押さえておくとよいです。
まず、単純な数値の昇順であれば、標準のソートをそのまま使えば問題ありません。
降順にしたい場合は、大きいものを前に置く比較ルールを指定します。
構造体やクラスをソートする場合は、どのメンバを基準にするかを決めます。
複数条件でソートする場合は、条件の優先順位を明確にします。
また、比較関数では等号を含めないことが重要です。
同じ値同士を比較したときは、どちらを前に置くべきとも判断しないようにします。
さらに、同じ値の元の順番を保ちたい場合は安定ソートを使います。
上位N件だけ欲しい場合や、N番目の値だけ欲しい場合は、通常のソート以外の方法を使うと効率的です。
まとめ
C++のソートは、標準ライブラリを使えば簡単に実装できます。
基本は昇順ソートです。
数値であれば小さい順、文字列であれば標準の比較ルールに基づいた順番で並びます。
降順にしたい場合は、大きいものを前に置く条件を指定します。
構造体やクラスのような独自データをソートする場合は、どの項目を基準にするかを明確にします。
複数条件で並べたい場合は、最初の条件で比較し、同じ場合だけ次の条件を見るという流れで考えます。
また、通常のソートは同じ値の順番を保証しません。
同じ値の元の順番を保ちたい場合は、安定ソートを使います。
上位N件だけ欲しい場合や、N番目の要素だけ知りたい場合は、全体を完全にソートしない方法もあります。
C++のソートで特に重要なのは、比較ルールを正しく作ることです。
「前に置くべきかどうか」を明確にし、同じ値のときに矛盾した判定をしないようにすれば、数値、文字列、構造体、複数条件のデータまで幅広く正しく並び替えられます。
以上、C++のデーターのソートのやり方についてでした。
最後までお読みいただき、ありがとうございました。
