MENU
  1. ホーム
  2. C++
  3. 基礎構文
  4. 配列
  5. [C++] 配列を降順にソートする方法

[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を実行しています。

よくある質問

降順ソートと昇順ソートの違いは何ですか？

降順ソートと昇順ソートは、データの並べ替え順序が異なります。

降順ソートは、データを大きい順に並べ替える方法で、例えば数値データでは最大の値が最初に来るようにします。

一方、昇順ソートは、データを小さい順に並べ替える方法で、最小の値が最初に来るようにします。

例：std::sort(data.begin(), data.end(), std::greater<int>())は降順ソート、std::sort(data.begin(), data.end())は昇順ソートです。

ソートアルゴリズムの選び方はどうすれば良いですか？

ソートアルゴリズムの選び方は、データの特性やサイズ、必要なパフォーマンスに依存します。

小規模なデータセットでは、バブルソートや挿入ソートのようなシンプルなアルゴリズムが適していますが、大規模なデータセットでは、クイックソートやマージソートのような効率的なアルゴリズムが推奨されます。

また、データがほぼ整列されている場合は、挿入ソートが効率的です。

標準ライブラリのstd::sortは、一般的に効率的であり、特に特別な要件がない場合に使用するのが良いでしょう。

ソートのパフォーマンスを向上させる方法はありますか？

ソートのパフォーマンスを向上させるためには、以下の方法があります：

  • 適切なアルゴリズムの選択: データの特性に応じて最適なソートアルゴリズムを選ぶことが重要です。
  • データの前処理: データが部分的に整列されている場合、挿入ソートのようなアルゴリズムが効率的に動作します。
  • 並列処理の利用: 大規模なデータセットでは、並列処理を利用してソートを高速化することができます。

C++17以降では、std::sortに並列ポリシーを指定することが可能です。

  • メモリの効率的な使用: メモリ使用量を抑えることで、キャッシュ効率を向上させ、ソートの速度を改善できます。

まとめ

この記事では、C++における配列の降順ソートについて、基本的なアルゴリズムから標準ライブラリを用いた効率的な方法、さらには応用例までを詳しく解説しました。

これにより、さまざまなデータ構造に対して適切なソート手法を選択し、実装するための具体的な方法を学ぶことができたでしょう。

これを機に、実際のプログラムでこれらのソート手法を試し、さらに自分のプロジェクトに応用してみてください。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

C言語
C++
Python
HTML
Java
HTTP

関連カテゴリーから探す

配列
  • URLをコピーしました！

関連記事

目次から探す