こんにちは！TechFUL でアルバイトをしている ia7ck です。
今回は、C++ で条件を指定したソートを行う方法について説明します。
シンプルな条件で並び替える
C++ の algorithm ヘッダに含まれている std::sort を使うと配列や std::vector を要素の昇順にソートしてくれます。たとえば
[6, 2, 5, 3, 8, 7]
という配列を
[2, 3, 5, 6, 7, 8]
と並び替えてくれます。
上の配列を降順にソートしたいときはどうしたらいいのでしょう。この場合は配列の要素を逆順にする std::reverse を使って、
- 配列を昇順にソートする (
std::sortを使う) - ソートした配列を逆順にする (
std::reverseを使う)
とすれば降順に並び替えられた配列
[8, 7, 6, 5, 3, 2]
が得られます。
複雑な条件で並び替える
さて、あなたは の倍数がとても好きだとします。なので配列をソートしたときに
の倍数はその他の数より前に来てほしいです。ただし
の倍数同士や
で割り切れない数同士は昇順に並べます。つまり、配列
[3, 6, 5, 2, 8, 7] を並び替えたあとは次のようになっていてほしいです。
[3, 6, 2, 5, 7, 8]
このような場合にはいくら std::reverse を上手に使っても目的を達成できそうにありません。また、今回のケース専用の関数が C++ に用意されているわけでもありません。
問題を解決する鍵はソート関数の引数にあります。std::sort の第3引数に比較関数を用いてソートの条件を指定してあげることで、好きな順序に並び替えることができます。
std::sort の基本的な使い方
比較関数を用いたソートを行う前に std::sort の基本的な使い方を確認します。要素を昇順にソートするには std::sort の第1引数と第2引数にソートする範囲を指定してあげればいいです。たとえば冒頭の問題のように、与えられた数値を降順にソートするプログラムは以下のようになります。
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { vector<int> values = {6, 2, 5, 3, 8, 7}; sort(values.begin(), values.end()); // 昇順にソートする reverse(values.begin(), values.end()); // 逆順にする for (auto val : values) { cout << val << " "; } // 8 7 6 5 3 2 // が出力される return 0; }
比較関数を用いたソート
次の問題を考えます。
N 人の生徒がいて、それぞれの生徒には出席番号が 1 から N まで振られています。
出席番号 i の生徒のテストの点数は scores[i] でした。
生徒の成績はテストの点数が高いほど良く、同じ点数であれば出席番号が小さいほど良いです。
K 番目に成績の良い生徒の出席番号はいくつですか。
たとえば N=5, K=2, scores=[89, 95, 82, 90, 95] の場合を考えます。生徒たちを成績の良い順に並べると次のようになります。
| 出席番号 | テストの点数 |
|---|---|
| 2 | 95 |
| 5 | 95 |
| 4 | 90 |
| 1 | 89 |
| 3 | 82 |
番目に成績の良い生徒の出席番号は
なので答えは
です。
以上の考察からこの問題は
- 出席番号・テストの点数の情報から、生徒を成績の良い順に並べる
- 前から K 番目の生徒の出席番号を見る
とすれば解けることが分かりました。1.の部分で条件を指定したソートを行う必要があります。比較関数を用いたソートは
bool cmp(const T &a, const T &b)
という形式を持つ関数を std::sort の第3引数に与えればいいです。関数の返り値は
aがbより (ソート後の配列で) 前に来てほしいならtrue- 後ろに来てほしいなら
false
とします。具体的に解答例のプログラムを見てみます。
解答例
#include <algorithm> #include <iostream> #include <vector> using namespace std; struct Student { int number; // 出席番号 int score; // テストの点数 }; bool comp(const Student &lhs, const Student &rhs) { // 比較関数の定義 if (lhs.score != rhs.score) { return lhs.score > rhs.score; } else { return lhs.number < rhs.number; } } int main() { int N, K; cin >> N >> K; vector<Student> students; for (int i = 1; i <= N; i++) { int score; cin >> score; students.push_back(Student{i, score}); } sort(students.begin(), students.end(), comp); // 第3引数に比較関数を与える cout << students[K - 1].number << endl; // 0-indexedに注意 return 0; }
bool comp(const Student &lhs, const Student &rhs) の部分が比較関数です。
2人の生徒の点数が異なる場合、
lhsの点数がrhsの点数より高いならば、つまり、lhs.score > rhs.scoreならばlhsがrhsより前に来てほしいです。したがってこのときはtrueを返します。- 逆に
lhs.score < rhs.scoreならばlhsはrhsより後ろに来てほしいのでfalseを返します。
2人の生徒の点数が同じ場合も同様に、それぞれの生徒の出席番号を比較して lhs が前に来てほしいなら true を、後ろに来てほしいなら false を返します。
ラムダ式を用いたソート
最後に、ラムダ式を用いたソートを紹介します。
とは言ってもすでに説明した比較関数を用いたソートと根本的な違いはありません。上のプログラムではソート関数 std::sort と比較関数 comp が離れていて少し見づらいと感じたかもしれません。ラムダ式を用いてソート部分を書き直すと次のようになります。
sort(students.begin(), students.end(), [](const Student &lhs, const Student &rhs) { if (lhs.score != rhs.score) { return lhs.score > rhs.score; } else { return lhs.number < rhs.number; }; });
ちょうどソート関数の途中で比較関数を書いたような格好になっています。ラムダ式を用いる利点の1つは、このようにソート対象となる students とソート基準を定めた比較関数とをひと目で確認できることだと思います。
おわりに
この記事では、C++ の std::sort による昇順ソート・降順ソートおよび比較関数 (ラムダ式) を用いて条件を指定したソートを行う方法を紹介しました。
比較関数さえ用意してしまえば C++ の高速なソート関数を用いて要素を並び替えることができるため、使いこなせると強い武器になるでしょう。
おまけ
いわゆる "読者への課題" です。今回の内容の復習にもなるかと思いますので挑戦してみてください。
1問目 (易しめ)
「std::sort の基本的な使い方」の章では std::sort と std::reverse を使って降順ソートを実現していました。ここでは、std::sort の第3引数に比較関数またはラムダ式を与えることで std::reverse を使わずに降順ソートを実現してみましょう。
解答例 (クリックで展開します)
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { vector<int> values = {6, 2, 5, 3, 8, 7}; sort(values.begin(), values.end(), [](const int &lhs, const int &rhs) { return lhs > rhs; // 大きい数が前に来るようにする }); for (auto val : values) { cout << val << " "; } // 8 7 6 5 3 2 // が出力される return 0; }
2問目 (やや難しめ)
冒頭に挙げた問題の2問目を解いてみましょう。問題を再掲します。
整数値の配列が与えられる。
の倍数とその他の数では
上の2つの条件を満たすように配列の要素を並び替えよ。
解答例 (クリックで展開します)
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { vector<int> values = {6, 2, 5, 3, 8, 7}; sort(values.begin(), values.end(), [](const int &lhs, const int &rhs) { if (lhs % 3 == 0 and rhs % 3 == 0) { return lhs < rhs; // 3の倍数同士は昇順 } else if (lhs % 3 != 0 and rhs % 3 != 0) { return lhs < rhs; // 3で割り切れない数同士も昇順 } else { return lhs % 3 == 0; // 3の倍数が前に来るようにする } }); for (auto val : values) { cout << val << " "; } // 3 6 2 5 7 8 // が出力される return 0; }
運営会社 / サービス
444株式会社
TechFUL
