プログラミング

C++における完全なソートガイド

最終更新： 23/03/2025
1分未満

C++における「ソート（並べ替え）」は、プログラミングにおいて非常に重要な技術であり、さまざまなアルゴリズムと方法があります。ソートを適切に使用することで、データの効率的な操作や処理が可能となり、プログラムのパフォーマンス向上に繋がります。本記事では、C++でのソートの基本的な概念から、主要なソートアルゴリズムまでを包括的に説明します。

1. ソートとは？

ソート（並べ替え）とは、あるデータセット（配列やリストなど）の要素を特定の順序に並べる操作を指します。一般的には「昇順」や「降順」で並べ替えることが多いです。例えば、整数の配列を昇順に並べ替えることがソートに該当します。

関連記事

C++におけるソートは、主に標準ライブラリに組み込まれた関数やアルゴリズムを使用して実現されます。そのため、効率的にソートを行うことが可能です。

2. C++におけるソートの基本

C++でのソートを行うためには、標準ライブラリのヘッダファイルに含まれるstd::sort関数を使用するのが一般的です。std::sort関数は、コンテナ内の要素を並べ替えるために非常に強力で使いやすい関数です。

例1：std::sortを使った昇順ソート

cpp
#include 
#include 
#include 

int main() {
    std::vector<int> vec = {5, 3, 8, 1, 2};

    std::sort(vec.begin(), vec.end());  // 昇順に並べ替え

    for(int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

上記のコードでは、std::sortを使ってvecというstd::vectorを昇順に並べ替えています。vec.begin()とvec.end()は、それぞれベクターの先頭と末尾を示し、この範囲の要素がソートされます。

例2：降順でのソート

昇順以外の順序で並べ替える場合、比較関数を指定することができます。降順に並べ替える場合は、std::greater()を使います。

cpp
#include 
#include 
#include 
#include 

int main() {
    std::vector<int> vec = {5, 3, 8, 1, 2};

    std::sort(vec.begin(), vec.end(), std::greater<int>());  // 降順に並べ替え

    for(int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

このコードでは、std::greater()という関数オブジェクトを比較関数として指定し、降順でソートしています。

3. ソートアルゴリズムの種類

C++で使用できるソートアルゴリズムには、いくつかの種類があります。それぞれのアルゴリズムは、時間計算量や安定性（並べ替えの結果、元の順序が保たれるかどうか）に違いがあります。代表的なアルゴリズムをいくつか紹介します。

3.1. バブルソート（Bubble Sort）

バブルソートは、隣接する要素を比較し、順番が逆であれば交換するという単純なアルゴリズムです。最も簡単ですが、計算量が大きいため、効率的ではありません。

  • 計算量：最悪の場合O(n²)

cpp
#include 
#include 

void bubbleSort(std::vector<int>& vec) {
    int n = vec.size();
    for (int i = 0; i < n-1; ++i) {
        for (int j = 0; j < n-i-1; ++j) {
            if (vec[j] > vec[j+1]) {
                std::swap(vec[j], vec[j+1]);
            }
        }
    }
}

int main() {
    std::vector<int> vec = {5, 3, 8, 1, 2};
    bubbleSort(vec);

    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.2. 挿入ソート（Insertion Sort）

挿入ソートは、各要素を適切な位置に挿入していくアルゴリズムです。小規模なデータセットにおいては効率的に動作しますが、大きなデータセットに対しては遅くなります。

  • 計算量：最悪の場合O(n²)

cpp
#include 
#include 

void insertionSort(std::vector<int>& vec) {
    int n = vec.size();
    for (int i = 1; i < n; ++i) {
        int key = vec[i];
        int j = i - 1;
        while (j >= 0 && vec[j] > key) {
            vec[j + 1] = vec[j];
            --j;
        }
        vec[j + 1] = key;
    }
}

int main() {
    std::vector<int> vec = {5, 3, 8, 1, 2};
    insertionSort(vec);

    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.3. クイックソート（Quick Sort）

クイックソートは、分割統治法を使ってデータをソートする効率的なアルゴリズムです。一般的に、他のソートアルゴリズムよりも速く動作します。

  • 計算量：最悪の場合O(n²)、平均O(n log n)

cpp
#include 
#include 

int partition(std::vector<int>& vec, int low, int high) {
    int pivot = vec[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (vec[j] <= pivot) {
            ++i;
            std::swap(vec[i], vec[j]);
        }
    }
    std::swap(vec[i + 1], vec[high]);
    return i + 1;
}

void quickSort(std::vector<int>& vec, int low, int high) {
    if (low < high) {
        int pi = partition(vec, low, high);
        quickSort(vec, low, pi - 1);
        quickSort(vec, pi + 1, high);
    }
}

int main() {
    std::vector<int> vec = {5, 3, 8, 1, 2};
    quickSort(vec, 0, vec.size() - 1);

    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.4. マージソート（Merge Sort）

マージソートは、リストを再帰的に分割し、分割された部分を順番にマージしていくアルゴリズムです。安定したソートを提供し、大きなデータセットにも対応可能です。

  • 計算量：O(n log n)

cpp
#include 
#include 

void merge(std::vector<int>& vec, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> leftVec(n1), rightVec(n2);

    for (int i = 0; i < n1; ++i) {
        leftVec[i] = vec[left + i];
    }
    for (int j = 0; j < n2; ++j) {
        rightVec[j] = vec[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftVec[i] <= rightVec[j]) {
            vec[k] = leftVec[i];
            ++i;
        } else {
            vec[k] = rightVec[j];
            ++j;
        }
        ++k;
    }

    while (i < n1) {
        vec[k] = leftVec[i];
        ++i;
        ++k;
    }
    while (j < n2) {
        vec[k] = rightVec[j];
        ++j;
        ++k;
    }
}

void mergeSort(std::vector<int>& vec, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(vec, left, mid);
        mergeSort(vec, mid + 1, right);
        merge(vec, left, mid, right);
    }
}

int main() {
    std::vector<int> vec = {5, 3, 8, 1, 2};
    mergeSort(vec, 0, vec.size() - 1);

    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

4. まとめ

C++におけるソートは、標準ライブラリのstd::sortを使用することで簡単に実行できますが、アルゴリズムの理解と選択も重要です。ソートのアルゴリズムは、データのサイズや特性に応じて使い分けるべきです。例えば、クイックソートやマージソートは大規模なデータセットに向いており、バブルソートや挿入ソートは小規模なデータセットに適しています。

適切なソートアルゴリズムを選択することで、プログラムのパフォーマンスを大幅に向上させることができます。

最終更新： 23/03/2025
1分未満
Back to top button