配列

[C++] 配列のソート方法

2025-01-18更新日: 2025-01-18

C++で配列をソートするには、標準ライブラリのstd::sort関数を使用するのが一般的です。

この関数は、#include <algorithm>をインクルードすることで利用可能です。

std::sortは、配列の先頭ポインタと末尾の次のポインタを引数に取り、デフォルトでは昇順にソートします。

カスタムの比較関数を渡すことで、降順や特定の条件に基づいたソートも可能です。

目次から探す

C++で配列をソートする方法
カスタム比較関数を使ったソート
配列以外のデータ構造のソート
ソートアルゴリズムの選択肢
ソート時の注意点
実践例：配列ソートの応用
まとめ

C++で配列をソートする方法

C++では、配列をソートするためにさまざまな方法があります。

標準ライブラリを利用することで、簡単に配列をソートすることができます。

ここでは、基本的なソート方法とその実装例を紹介します。

標準ライブラリのsort関数を使用する

C++の標準ライブラリには、<algorithm>ヘッダに定義されているsort関数があります。

この関数を使うことで、簡単に配列をソートできます。

#include <iostream>
#include <algorithm> // sort関数を使用するために必要
int main() {
    int arr[] = {5, 2, 9, 1, 5, 6}; // ソートする配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列の要素数
    std::sort(arr, arr + n); // 配列を昇順にソート
    // ソート結果を表示
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

1 2 5 5 6 9

このコードでは、std::sortを使って配列arrを昇順にソートしています。

arrの最初の要素から最後の要素までを指定することで、全体をソートすることができます。

降順にソートする方法

降順にソートしたい場合は、std::greaterを使用することができます。

#include <iostream>
#include <algorithm> // sort関数を使用するために必要
#include <functional> // greaterを使用するために必要
int main() {
    int arr[] = {5, 2, 9, 1, 5, 6}; // ソートする配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列の要素数
    std::sort(arr, arr + n, std::greater<int>()); // 配列を降順にソート
    // ソート結果を表示
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

9 6 5 5 2 1

このコードでは、std::greater<int>()を指定することで、配列を降順にソートしています。

カスタム比較関数を使ったソート

独自の条件でソートしたい場合は、カスタム比較関数を作成することができます。

#include <iostream>
#include <algorithm> // sort関数を使用するために必要
// カスタム比較関数
bool customCompare(int a, int b) {
    return a % 10 < b % 10; // 10で割った余りで比較
}
int main() {
    int arr[] = {25, 12, 9, 34, 5, 6}; // ソートする配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列の要素数
    std::sort(arr, arr + n, customCompare); // カスタム比較関数を使用してソート
    // ソート結果を表示
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

25 5 34 6 12 9

この例では、配列の要素を10で割った余りを基準にしてソートしています。

カスタム比較関数を使うことで、柔軟なソートが可能になります。

カスタム比較関数を使ったソート

C++のstd::sort関数は、デフォルトでは昇順にソートしますが、カスタム比較関数を使用することで、独自の条件に基づいてソートすることができます。

ここでは、カスタム比較関数の作成方法とその使用例を紹介します。

カスタム比較関数の定義

カスタム比較関数は、2つの引数を受け取り、比較結果を真偽値で返す関数です。

引数が小さい場合はtrueを返し、大きい場合はfalseを返します。

この関数をstd::sortに渡すことで、ソートの基準を変更できます。

例：文字列の長さでソート

以下の例では、文字列の配列をその長さに基づいてソートします。

#include <iostream>
#include <algorithm> // sort関数を使用するために必要
#include <string>    // stringを使用するために必要
#include <vector>    // vectorを使用するために必要
// カスタム比較関数
bool compareByLength(const std::string &a, const std::string &b) {
    return a.length() < b.length(); // 文字列の長さで比較
}
int main() {
    std::vector<std::string> words = {"apple", "banana", "kiwi", "cherry", "blueberry"}; // ソートする文字列の配列
    std::sort(words.begin(), words.end(), compareByLength); // カスタム比較関数を使用してソート
    // ソート結果を表示
    for (const auto &word : words) {
        std::cout << word << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

kiwi apple banana cherry blueberry

このコードでは、compareByLength関数を使って、文字列の長さに基づいてソートしています。

結果として、短い文字列から長い文字列の順に表示されます。

例：構造体のメンバーでソート

カスタム比較関数は、構造体のメンバーを基準にしてソートする際にも使用できます。

以下の例では、学生の構造体を定義し、成績に基づいてソートします。

#include <iostream>
#include <algorithm> // sort関数を使用するために必要
#include <vector>    // vectorを使用するために必要
// 学生を表す構造体
struct Student {
    std::string name; // 名前
    int score;        // 成績
};
// カスタム比較関数
bool compareByScore(const Student &a, const Student &b) {
    return a.score > b.score; // 成績が高い順に比較
}
int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"David", 90}
    }; // ソートする学生の配列
    std::sort(students.begin(), students.end(), compareByScore); // カスタム比較関数を使用してソート
    // ソート結果を表示
    for (const auto &student : students) {
        std::cout << student.name << ": " << student.score << " "; // 各学生の名前と成績を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

Bob: 92 Alice: 85 David: 90 Charlie: 78

この例では、compareByScore関数を使って、学生の成績に基づいてソートしています。

成績が高い順に表示されるため、成績の良い学生が先に来るようになります。

カスタム比較関数を使用することで、さまざまな条件に基づいて配列やベクターをソートすることができます。

これにより、特定の要件に応じた柔軟なソートが可能になります。

配列以外のデータ構造のソート

C++では、配列以外にもさまざまなデータ構造が存在します。

ここでは、配列以外のデータ構造であるstd::vector、std::list、およびstd::setのソート方法について解説します。

std::vectorのソート

std::vectorは、動的にサイズを変更できる配列のようなデータ構造です。

std::sortを使用して簡単にソートできます。

#include <iostream>
#include <vector>    // vectorを使用するために必要
#include <algorithm> // sort関数を使用するために必要
int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9}; // ソートするベクター
    std::sort(vec.begin(), vec.end()); // ベクターを昇順にソート
    // ソート結果を表示
    for (const auto &num : vec) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

1 1 3 4 5 9

このコードでは、std::vectorを昇順にソートしています。

std::sortを使うことで、簡単にソートが可能です。

std::listのソート

std::listは、双方向リストを実装したデータ構造です。

std::listには、sortメンバ関数が用意されており、これを使ってソートできます。

#include <iostream>
#include <list>      // listを使用するために必要
int main() {
    std::list<int> lst = {4, 2, 5, 1, 3}; // ソートするリスト
    lst.sort(); // リストを昇順にソート
    // ソート結果を表示
    for (const auto &num : lst) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

1 2 3 4 5

このコードでは、std::listのsortメンバ関数を使用して、リストを昇順にソートしています。

std::setのソート

std::setは、重複を許さない順序付きのコレクションです。

std::setは常に要素がソートされた状態で保持されるため、特別なソート操作は必要ありません。

#include <iostream>
#include <set>       // setを使用するために必要
int main() {
    std::set<int> mySet = {5, 3, 1, 4, 2}; // ソートされた状態で保持されるセット
    // ソート結果を表示
    for (const auto &num : mySet) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

1 2 3 4 5

このコードでは、std::setを使用して、要素が自動的にソートされた状態で保持されることを示しています。

配列以外のデータ構造でも、C++の標準ライブラリを利用することで簡単にソートが可能です。

std::vectorやstd::listではsort関数を使用し、std::setでは自動的にソートされた状態で要素が保持されます。

これにより、さまざまなデータ構造に対して柔軟にソートを行うことができます。

ソートアルゴリズムの選択肢

C++では、さまざまなソートアルゴリズムが利用可能です。

各アルゴリズムには特性があり、データの特性やサイズに応じて適切なアルゴリズムを選択することが重要です。

ここでは、一般的なソートアルゴリズムのいくつかを紹介します。

バブルソート (Bubble Sort)

バブルソートは、隣接する要素を比較し、順序が逆であれば交換することを繰り返すシンプルなアルゴリズムです。

最も単純ですが、効率は良くありません。

時間計算量: O(n^2)
空間計算量: O(1)

#include <iostream>
#include <vector> // vectorを使用するために必要
void bubbleSort(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> arr = {64, 34, 25, 12, 22, 11, 90}; // ソートする配列
    bubbleSort(arr); // バブルソートを実行
    // ソート結果を表示
    for (const auto &num : arr) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

選択ソート (Selection Sort)

選択ソートは、未ソート部分から最小(または最大)の要素を選択し、先頭に移動させるアルゴリズムです。

シンプルですが、効率は良くありません。

時間計算量: O(n^2)
空間計算量: O(1)

#include <iostream>
#include <vector> // vectorを使用するために必要
void selectionSort(std::vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // 最小要素のインデックス
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 最小要素のインデックスを更新
            }
        }
        std::swap(arr[i], arr[minIndex]); // 要素を交換
    }
}
int main() {
    std::vector<int> arr = {64, 25, 12, 22, 11}; // ソートする配列
    selectionSort(arr); // 選択ソートを実行
    // ソート結果を表示
    for (const auto &num : arr) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

挿入ソート (Insertion Sort)

挿入ソートは、未ソート部分から要素を取り出し、ソート済み部分に適切な位置に挿入するアルゴリズムです。

小規模なデータに対しては効率的です。

時間計算量: O(n^2)
空間計算量: O(1)

#include <iostream>
#include <vector> // vectorを使用するために必要
void insertionSort(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> arr = {12, 11, 13, 5, 6}; // ソートする配列
    insertionSort(arr); // 挿入ソートを実行
    // ソート結果を表示
    for (const auto &num : arr) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

クイックソート (Quick Sort)

クイックソートは、分割統治法を用いた効率的なソートアルゴリズムです。

ピボットを選び、配列をそれより小さい部分と大きい部分に分けて再帰的にソートします。

時間計算量: O(n log n)(平均)、O(n^2)(最悪)
空間計算量: O(log n)

#include <iostream>
#include <vector> // vectorを使用するために必要
int partition(std::vector<int> &arr, int low, int high) {
    int pivot = arr[high]; // ピボットを選択
    int i = low - 1; // 小さい要素のインデックス
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]); // 要素を交換
        }
    }
    std::swap(arr[i + 1], arr[high]); // ピボットを正しい位置に移動
    return i + 1; // ピボットのインデックスを返す
}
void quickSort(std::vector<int> &arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // パーティションを実行
        quickSort(arr, low, pi - 1); // 左部分をソート
        quickSort(arr, pi + 1, high); // 右部分をソート
    }
}
int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5}; // ソートする配列
    quickSort(arr, 0, arr.size() - 1); // クイックソートを実行
    // ソート結果を表示
    for (const auto &num : arr) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

マージソート (Merge Sort)

マージソートも分割統治法を用いたアルゴリズムで、配列を半分に分けてそれぞれをソートし、最後にマージします。

安定したソートが可能です。

時間計算量: O(n log n)
空間計算量: O(n)

#include <iostream>
#include <vector> // vectorを使用するために必要
void merge(std::vector<int> &arr, int left, int mid, int right) {
    int n1 = mid - left + 1; // 左部分のサイズ
    int n2 = right - mid;    // 右部分のサイズ
    std::vector<int> L(n1), R(n2); // 左右の配列を作成
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i]; // 左部分をコピー
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j]; // 右部分をコピー
    int i = 0, j = 0, k = left; // インデックスの初期化
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i]; // 左部分の要素をコピー
            i++;
        } else {
            arr[k] = R[j]; // 右部分の要素をコピー
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i]; // 残りの左部分をコピー
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j]; // 残りの右部分をコピー
        j++;
        k++;
    }
}
void mergeSort(std::vector<int> &arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 中間点を計算
        mergeSort(arr, left, mid); // 左部分をソート
        mergeSort(arr, mid + 1, right); // 右部分をソート
        merge(arr, left, mid, right); // マージ
    }
}
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7}; // ソートする配列
    mergeSort(arr, 0, arr.size() - 1); // マージソートを実行
    // ソート結果を表示
    for (const auto &num : arr) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

C++では、さまざまなソートアルゴリズムが利用可能で、それぞれに特性があります。

データの特性やサイズに応じて、適切なアルゴリズムを選択することが重要です。

一般的には、クイックソートやマージソートが効率的で広く使用されていますが、特定の状況では他のアルゴリズムが適している場合もあります。

ソート時の注意点

ソートを行う際には、いくつかの注意点があります。

これらを理解しておくことで、より効率的かつ正確なソートを実現できます。

以下に、ソート時の主な注意点を挙げます。

データの特性を理解する

データのサイズ: 小規模なデータには単純なアルゴリズム(バブルソートや挿入ソート)が適している場合がありますが、大規模なデータには効率的なアルゴリズム(クイックソートやマージソート)を選ぶべきです。
データの分布: すでにソートされているデータやほぼソートされているデータに対しては、挿入ソートが非常に効率的です。

安定性の考慮

安定ソート: 同じ値を持つ要素の順序を保持するソートアルゴリズム(例：マージソート、挿入ソート)を選ぶことで、元のデータの順序を維持できます。

特に、複数のキーでソートする場合に重要です。

非安定ソート: 同じ値を持つ要素の順序が変わる可能性があるアルゴリズム(例：クイックソート、ヒープソート)を使用する場合は、注意が必要です。

メモリ使用量

空間計算量: 一部のソートアルゴリズム(例：マージソート)は追加のメモリを必要とします。

メモリ制約がある場合は、インプレースでソートできるアルゴリズム(例：クイックソート、ヒープソート)を選ぶと良いでしょう。

データ構造の選択: ソートするデータが大きい場合、適切なデータ構造(例：std::vectorやstd::list)を選ぶことも重要です。

ソートの安定性とパフォーマンス

最悪ケースのパフォーマンス: 一部のアルゴリズム(例：クイックソート)は、最悪の場合にO(n^2)の時間計算量になることがあります。

これを避けるために、適切なピボット選択や他のアルゴリズム(例：ヒープソート)を検討することが重要です。

平均ケースのパフォーマンス: 多くのアルゴリズムは、平均的なケースでO(n log n)のパフォーマンスを持っていますが、特定のデータに対しては異なる結果になることがあります。

ソートの前後処理

データの前処理: ソートを行う前に、データの整形やフィルタリングを行うことで、ソートの効率を向上させることができます。
ソート後の処理: ソート後にデータを利用する際、必要に応じて再構築や再配置を行うことが重要です。

ソートの実装とテスト

実装の確認: ソートアルゴリズムを実装したら、さまざまなケース(空の配列、すでにソートされた配列、重複要素を含む配列など)でテストすることが重要です。
パフォーマンスの測定: 実際のデータに対してソートのパフォーマンスを測定し、必要に応じてアルゴリズムを見直すことが推奨されます。

ソートを行う際には、データの特性やアルゴリズムの特性を理解し、適切な選択を行うことが重要です。

安定性、メモリ使用量、パフォーマンスなどの要素を考慮し、実装とテストを行うことで、より効果的なソートを実現できます。

これらの注意点を踏まえて、適切なソート手法を選択しましょう。

実践例：配列ソートの応用

配列のソートは、さまざまなアプリケーションで重要な役割を果たします。

ここでは、配列ソートの具体的な応用例をいくつか紹介します。

学生の成績管理

学生の成績を管理する際、成績を昇順または降順にソートすることで、成績の良い学生や悪い学生を簡単に特定できます。

以下の例では、学生の名前と成績を持つ構造体を定義し、成績に基づいてソートします。

#include <iostream>
#include <vector>
#include <algorithm> // sort関数を使用するために必要
// 学生を表す構造体
struct Student {
    std::string name; // 名前
    int score;        // 成績
};
// カスタム比較関数
bool compareByScore(const Student &a, const Student &b) {
    return a.score > b.score; // 成績が高い順に比較
}
int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"David", 90}
    }; // ソートする学生の配列
    std::sort(students.begin(), students.end(), compareByScore); // 成績でソート
    // ソート結果を表示
    for (const auto &student : students) {
        std::cout << student.name << ": " << student.score << " "; // 各学生の名前と成績を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

Bob: 92 Alice: 85 David: 90 Charlie: 78

このコードでは、学生の成績を降順にソートし、成績の良い学生から順に表示しています。

商品の価格リスト

オンラインストアなどで、商品の価格を昇順または降順にソートすることで、ユーザーが最も安い商品や高い商品を簡単に見つけられるようにします。

以下の例では、商品の価格をソートします。

#include <iostream>
#include <vector>
#include <algorithm> // sort関数を使用するために必要
// 商品を表す構造体
struct Product {
    std::string name; // 商品名
    double price;     // 価格
};
// カスタム比較関数
bool compareByPrice(const Product &a, const Product &b) {
    return a.price < b.price; // 価格が安い順に比較
}
int main() {
    std::vector<Product> products = {
        {"Laptop", 999.99},
        {"Smartphone", 499.99},
        {"Tablet", 299.99},
        {"Headphones", 199.99}
    }; // ソートする商品の配列
    std::sort(products.begin(), products.end(), compareByPrice); // 価格でソート
    // ソート結果を表示
    for (const auto &product : products) {
        std::cout << product.name << ": $" << product.price << " "; // 各商品の名前と価格を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

Headphones: $199.99 Tablet: $299.99 Smartphone: $499.99 Laptop: $999.99

このコードでは、商品の価格を昇順にソートし、最も安い商品から順に表示しています。

タスクの優先順位管理

タスク管理アプリケーションでは、タスクの優先順位に基づいてタスクをソートすることが重要です。

以下の例では、タスクの優先度を持つ構造体を定義し、優先度に基づいてソートします。

#include <iostream>
#include <vector>
#include <algorithm> // sort関数を使用するために必要
// タスクを表す構造体
struct Task {
    std::string name; // タスク名
    int priority;     // 優先度
};
// カスタム比較関数
bool compareByPriority(const Task &a, const Task &b) {
    return a.priority < b.priority; // 優先度が高い順に比較
}
int main() {
    std::vector<Task> tasks = {
        {"Finish report", 2},
        {"Email client", 1},
        {"Prepare presentation", 3},
        {"Update website", 2}
    }; // ソートするタスクの配列
    std::sort(tasks.begin(), tasks.end(), compareByPriority); // 優先度でソート
    // ソート結果を表示
    for (const auto &task : tasks) {
        std::cout << task.name << " (Priority: " << task.priority << ") "; // 各タスクの名前と優先度を表示
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

Email client (Priority: 1) Finish report (Priority: 2) Update website (Priority: 2) Prepare presentation (Priority: 3)

このコードでは、タスクの優先度を昇順にソートし、優先度の高いタスクから順に表示しています。

配列のソートは、さまざまな実践的なアプリケーションで重要な役割を果たします。

学生の成績管理、商品の価格リスト、タスクの優先順位管理など、ソートを活用することで、データの整理や分析が容易になります。

これらの例を参考に、実際のアプリケーションにおけるソートの活用方法を考えてみましょう。

まとめ

この記事では、C++における配列のソート方法やその応用について詳しく解説しました。

さまざまなソートアルゴリズムの特性や、データ構造に応じた適切な選択が重要であることがわかりました。

これを踏まえて、実際のアプリケーションにおいてソートを活用し、データの整理や分析を行うことを検討してみてください。

2025-01-18更新日: 2025-01-18

C++で配列をソートする方法

標準ライブラリのsort関数を使用する

降順にソートする方法

カスタム比較関数を使ったソート

カスタム比較関数を使ったソート

カスタム比較関数の定義

例：文字列の長さでソート

例：構造体のメンバーでソート

配列以外のデータ構造のソート

std::vectorのソート

std::listのソート

std::setのソート

ソートアルゴリズムの選択肢

バブルソート (Bubble Sort)

選択ソート (Selection Sort)

挿入ソート (Insertion Sort)

クイックソート (Quick Sort)

マージソート (Merge Sort)

ソート時の注意点

データの特性を理解する

安定性の考慮

メモリ使用量

ソートの安定性とパフォーマンス

ソートの前後処理

ソートの実装とテスト

実践例：配列ソートの応用

学生の成績管理

商品の価格リスト

タスクの優先順位管理

まとめ

関連記事