[C++] 配列を降順にソートする方法
C++で配列を降順にソートするには、標準ライブラリのalgorithmヘッダに含まれる関数を利用するのが一般的です。
具体的には、std::sort
関数を使用し、第三引数にstd::greater<int>()
を指定することで、配列を降順に並べ替えることができます。
この方法は、配列の要素が整数型である場合に特に有効です。
また、std::vector
などのSTLコンテナでも同様の手法で降順ソートが可能です。
このように、C++の標準ライブラリを活用することで、効率的かつ簡潔に配列のソートを行うことができます。
- 降順ソートの基本的なアルゴリズム
- C++標準ライブラリを使った効率的な降順ソート
- 2次元配列や構造体配列を降順にソートする応用例
- カスタム比較関数を用いたソートの実装方法
降順ソートの基本的なアルゴリズム
配列を降順にソートするための基本的なアルゴリズムには、バブルソート、選択ソート、挿入ソートがあります。
これらのアルゴリズムは、シンプルで理解しやすいですが、効率が高くないため、小規模なデータセットに適しています。
バブルソート
バブルソートは、隣接する要素を比較し、必要に応じて交換することで配列をソートします。
降順にソートする場合、より大きな要素を前に移動させます。
#include <iostream>
#include <vector>
void bubbleSortDescending(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] < arr[j + 1]) {
// 要素を交換
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
bubbleSortDescending(data);
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
8 6 5 3 2
このコードは、バブルソートを用いて配列を降順にソートします。
隣接する要素を比較し、必要に応じて交換することで、最も大きな要素が前に移動します。
選択ソート
選択ソートは、未ソート部分から最大の要素を選び、先頭に移動させることで配列をソートします。
#include <iostream>
#include <vector>
void selectionSortDescending(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int maxIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
// 最大要素を先頭に移動
std::swap(arr[i], arr[maxIndex]);
}
}
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
selectionSortDescending(data);
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
8 6 5 3 2
このコードは、選択ソートを用いて配列を降順にソートします。
未ソート部分から最大の要素を選び、先頭に移動させることでソートを行います。
挿入ソート
挿入ソートは、配列を部分的にソートしながら、未ソートの要素を適切な位置に挿入することでソートを行います。
#include <iostream>
#include <vector>
void insertionSortDescending(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// 適切な位置に挿入
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
insertionSortDescending(data);
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
8 6 5 3 2
このコードは、挿入ソートを用いて配列を降順にソートします。
未ソートの要素を適切な位置に挿入することで、配列を部分的にソートしながら進めます。
C++標準ライブラリを使った降順ソート
C++標準ライブラリを使用することで、効率的に配列を降順にソートすることができます。
ここでは、std::sort関数
とstd::greater
、std::reverse
を用いた方法を紹介します。
std::sort関数の使い方
std::sort
は、C++標準ライブラリに含まれる汎用的なソート関数で、デフォルトでは昇順にソートします。
降順にソートするためには、カスタムの比較関数を指定する必要があります。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
// 昇順にソート
std::sort(data.begin(), data.end());
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
2 3 5 6 8
このコードは、std::sort
を用いて配列を昇順にソートします。
デフォルトの動作では、要素は小さい順に並べられます。
std::greaterを使った降順ソート
std::greater
を使用することで、std::sort関数
を降順にソートするようにカスタマイズできます。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort, std::greater
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
// 降順にソート
std::sort(data.begin(), data.end(), std::greater<int>());
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
8 6 5 3 2
このコードは、std::greater
を比較関数として指定することで、std::sort
を用いて配列を降順にソートします。
std::greater
は、要素を大きい順に並べるための比較関数です。
std::reverseを使ったソート結果の反転
std::reverse
を使用することで、既に昇順にソートされた配列を降順に反転させることができます。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort, std::reverse
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
// 昇順にソート
std::sort(data.begin(), data.end());
// ソート結果を反転
std::reverse(data.begin(), data.end());
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
8 6 5 3 2
このコードは、まずstd::sort
で配列を昇順にソートし、その後std::reverse
を用いてソート結果を反転させることで、降順に並べ替えています。
std::reverse
は、指定された範囲の要素を逆順に並べ替える関数です。
降順ソートの実装例
ここでは、降順ソートの具体的な実装例をいくつか紹介します。
バブルソート、std::sort
とstd::greater
、そしてstd::reverse
を用いた方法をそれぞれ見ていきます。
バブルソートによる実装例
バブルソートは、隣接する要素を比較し、必要に応じて交換することで配列をソートします。
以下は、バブルソートを用いて配列を降順にソートする実装例です。
#include <iostream>
#include <vector>
void bubbleSortDescending(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] < arr[j + 1]) {
// 要素を交換
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
bubbleSortDescending(data);
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
8 6 5 3 2
この実装では、バブルソートを用いて配列を降順にソートしています。
隣接する要素を比較し、必要に応じて交換することで、最も大きな要素が前に移動します。
std::sortとstd::greaterを使った実装例
std::sort
とstd::greater
を組み合わせることで、簡単に降順ソートを実現できます。
以下はその実装例です。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort, std::greater
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
// 降順にソート
std::sort(data.begin(), data.end(), std::greater<int>());
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
8 6 5 3 2
この実装では、std::sort
にstd::greater
を比較関数として渡すことで、配列を降順にソートしています。
std::greater
は、要素を大きい順に並べるための比較関数です。
std::reverseを使った実装例
std::reverse
を用いることで、既に昇順にソートされた配列を降順に反転させることができます。
以下はその実装例です。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort, std::reverse
int main() {
std::vector<int> data = {5, 3, 8, 6, 2};
// 昇順にソート
std::sort(data.begin(), data.end());
// ソート結果を反転
std::reverse(data.begin(), data.end());
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
8 6 5 3 2
この実装では、まずstd::sort
で配列を昇順にソートし、その後std::reverse
を用いてソート結果を反転させることで、降順に並べ替えています。
std::reverse
は、指定された範囲の要素を逆順に並べ替える関数です。
応用例
降順ソートは、さまざまなデータ構造に応用することができます。
ここでは、2次元配列、構造体配列、カスタム比較関数を用いたソートの例を紹介します。
2次元配列の降順ソート
2次元配列を降順にソートする場合、特定の行や列を基準にソートすることが一般的です。
以下は、各行を降順にソートする例です。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort, std::greater
int main() {
std::vector<std::vector<int>> matrix = {
{5, 3, 8},
{6, 2, 7},
{4, 9, 1}
};
for (auto& row : matrix) {
// 各行を降順にソート
std::sort(row.begin(), row.end(), std::greater<int>());
}
for (const auto& row : matrix) {
for (int num : row) {
std::cout << num << " ";
}
std::cout << std::endl;
}
return 0;
}
8 5 3
7 6 2
9 4 1
このコードは、2次元配列の各行を降順にソートします。
std::sort
とstd::greater
を用いて、各行の要素を大きい順に並べ替えています。
構造体配列の降順ソート
構造体配列を降順にソートする場合、特定のメンバ変数を基準にソートします。
以下は、構造体のage
メンバを基準に降順ソートする例です。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort
struct Person {
std::string name;
int age;
};
// 比較関数
bool compareByAgeDescending(const Person& a, const Person& b) {
return a.age > b.age;
}
int main() {
std::vector<Person> people = {
{"Alice", 30},
{"Bob", 25},
{"Charlie", 35}
};
// ageを基準に降順にソート
std::sort(people.begin(), people.end(), compareByAgeDescending);
for (const auto& person : people) {
std::cout << person.name << ": " << person.age << std::endl;
}
return 0;
}
Charlie: 35
Alice: 30
Bob: 25
このコードは、構造体配列をage
メンバを基準に降順にソートします。
カスタムの比較関数compareByAgeDescending
を用いて、std::sort
を実行しています。
カスタム比較関数を使ったソート
カスタム比較関数を用いることで、特定の条件に基づいてソートを行うことができます。
以下は、文字列の長さを基準に降順ソートする例です。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort
// 比較関数
bool compareByLengthDescending(const std::string& a, const std::string& b) {
return a.length() > b.length();
}
int main() {
std::vector<std::string> words = {"apple", "banana", "kiwi", "strawberry"};
// 文字列の長さを基準に降順にソート
std::sort(words.begin(), words.end(), compareByLengthDescending);
for (const auto& word : words) {
std::cout << word << " ";
}
return 0;
}
strawberry banana apple kiwi
このコードは、文字列の長さを基準に降順にソートします。
カスタムの比較関数compareByLengthDescending
を用いて、std::sort
を実行しています。
よくある質問
まとめ
この記事では、C++における配列の降順ソートについて、基本的なアルゴリズムから標準ライブラリを用いた効率的な方法、さらには応用例までを詳しく解説しました。
これにより、さまざまなデータ構造に対して適切なソート手法を選択し、実装するための具体的な方法を学ぶことができたでしょう。
これを機に、実際のプログラムでこれらのソート手法を試し、さらに自分のプロジェクトに応用してみてください。