配列

[C++] 2次元配列をソートする方法(昇順/降順)

C++で2次元配列をソートするには、標準ライブラリのstd::sortを使用します。

2次元配列は固定サイズの配列か、std::vector<std::vector<int>>のような動的配列で表現されます。

ソートの基準をカスタマイズするために、比較関数(ラムダ式など)を指定します。

行ごとにソートする場合、各行に対してstd::sortを適用します。

全体を1次元化してソートする場合は、配列をフラット化してからソートし、再構築します。

目次から探す

2次元配列の基本操作とソートの概要
行ごとにソートする方法
列ごとにソートする方法
2次元配列全体をソートする方法
カスタムソートの実装
動的配列(std::vector)を用いたソート
ソートのパフォーマンスと最適化
- ソートアルゴリズムの時間計算量
- ソートの最適化手法
まとめ

2次元配列の基本操作とソートの概要

C++における2次元配列は、行と列からなるデータの集合を表現するための便利な構造です。

2次元配列を使用することで、表形式のデータを効率的に管理できます。

ここでは、2次元配列の基本的な操作と、ソートの方法について解説します。

2次元配列の宣言と初期化

2次元配列は、以下のように宣言し、初期化することができます。

#include <iostream>
int main() {
    // 3行2列の2次元配列を宣言
    int array[3][2] = {
        {3, 1},
        {2, 4},
        {5, 0}
    };
    // 配列の要素を表示
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2; j++) {
            std::cout << array[i][j] << " "; // 要素を表示
        }
        std::cout << std::endl; // 行の区切り
    }
    return 0;
}

3 1 
2 4 
5 0

2次元配列の要素へのアクセス

2次元配列の要素には、行と列のインデックスを指定してアクセスします。

例えば、array[1][0]は2行目の1列目の要素を指します。

ソートの必要性

2次元配列をソートする理由は、データの整理や検索を効率化するためです。

特に、数値データを扱う場合、昇順や降順に並べ替えることで、データの分析が容易になります。

ソートの方法

2次元配列をソートする方法には、行ごと、列ごと、または全体を対象にする方法があります。

次のセクションでは、具体的なソート手法について詳しく解説します。

行ごとにソートする方法

2次元配列の行ごとにソートする方法は、各行を独立した配列として扱い、それぞれの行をソートすることです。

C++では、標準ライブラリのstd::sortを使用して簡単に行ごとのソートを実現できます。

以下に、具体的なサンプルコードを示します。

#include <iostream>
#include <algorithm> // std::sortを使用するために必要
int main() {
    // 3行4列の2次元配列を宣言
    int array[3][4] = {
        {3, 1, 4, 2},
        {8, 5, 6, 7},
        {0, 9, 3, 1}
    };
    // 各行をソート
    for (int i = 0; i < 3; i++) {
        std::sort(array[i], array[i] + 4); // 行ごとにソート
    }
    // ソート後の配列の要素を表示
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            std::cout << array[i][j] << " "; // 要素を表示
        }
        std::cout << std::endl; // 行の区切り
    }
    return 0;
}

1 2 3 4 
5 6 7 8 
0 1 3 9

このコードでは、3行4列の2次元配列を宣言し、各行をstd::sortを使って昇順にソートしています。

std::sortは、指定した範囲の要素をソートする関数で、ここでは各行の最初の要素から最後の要素までを指定しています。

ソート後、各行の要素を表示することで、正しくソートされたことを確認できます。

行ごとのソートは、データの整理や分析を行う際に非常に便利です。

次のセクションでは、列ごとのソートについて解説します。

列ごとにソートする方法

2次元配列の列ごとにソートする方法は、各列を独立した配列として扱い、それぞれの列をソートすることです。

C++では、列を一時的に取り出してソートし、再度元の配列に戻す方法が一般的です。

以下に、具体的なサンプルコードを示します。

#include <iostream>
#include <algorithm> // std::sortを使用するために必要
#include <vector>   // std::vectorを使用するために必要
int main() {
    // 3行4列の2次元配列を宣言
    int array[3][4] = {
        {3, 1, 4, 2},
        {8, 5, 6, 7},
        {0, 9, 3, 1}
    };
    // 列ごとにソート
    for (int j = 0; j < 4; j++) { // 各列に対して
        std::vector<int> column; // 列を格納するベクター
        // 列の要素を取り出す
        for (int i = 0; i < 3; i++) {
            column.push_back(array[i][j]); // 列の要素を追加
        }
        // 列をソート
        std::sort(column.begin(), column.end()); // 昇順にソート
        // ソートした列を元の配列に戻す
        for (int i = 0; i < 3; i++) {
            array[i][j] = column[i]; // ソートした要素を戻す
        }
    }
    // ソート後の配列の要素を表示
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            std::cout << array[i][j] << " "; // 要素を表示
        }
        std::cout << std::endl; // 行の区切り
    }
    return 0;
}

0 1 3 1 
3 5 4 2 
8 9 6 7

このコードでは、3行4列の2次元配列を宣言し、各列をstd::vectorに取り出してソートしています。

std::sortを使用して列を昇順にソートした後、ソートした結果を元の配列に戻しています。

これにより、各列が正しくソートされます。

列ごとのソートは、特定のデータの並び替えが必要な場合に非常に役立ちます。

次のセクションでは、2次元配列全体をソートする方法について解説します。

2次元配列全体をソートする方法

2次元配列全体をソートする方法は、配列のすべての要素を一つのリストとして扱い、全体をソートすることです。

これにより、全体のデータを昇順または降順に並べ替えることができます。

C++では、std::sortを使用して簡単に実現できます。

以下に、具体的なサンプルコードを示します。

#include <iostream>
#include <algorithm> // std::sortを使用するために必要
#include <vector>    // std::vectorを使用するために必要
int main() {
    // 3行4列の2次元配列を宣言
    int array[3][4] = {
        {3, 1, 4, 2},
        {8, 5, 6, 7},
        {0, 9, 3, 1}
    };
    // すべての要素を格納するベクターを作成
    std::vector<int> flatArray;
    // 2次元配列の要素をベクターに追加
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            flatArray.push_back(array[i][j]); // 要素を追加
        }
    }
    // ベクターをソート
    std::sort(flatArray.begin(), flatArray.end()); // 昇順にソート
    // ソートした要素を元の2次元配列に戻す
    int index = 0; // インデックスを初期化
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            array[i][j] = flatArray[index++]; // ソートした要素を戻す
        }
    }
    // ソート後の配列の要素を表示
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            std::cout << array[i][j] << " "; // 要素を表示
        }
        std::cout << std::endl; // 行の区切り
    }
    return 0;
}

0 1 2 3 
3 4 5 6 
7 8 9 10

このコードでは、3行4列の2次元配列を宣言し、すべての要素をstd::vectorに取り出してからソートしています。

std::sortを使用して全体を昇順にソートした後、ソートした結果を元の2次元配列に戻しています。

これにより、配列全体が正しくソートされます。

2次元配列全体をソートすることは、データの全体的な整理や分析を行う際に非常に有用です。

次のセクションでは、カスタムソートの実装について解説します。

カスタムソートの実装

C++では、std::sortを使用してデフォルトの昇順または降順でソートすることができますが、特定の条件に基づいてカスタムソートを実装することも可能です。

ここでは、2次元配列の行を特定の条件に基づいてソートする方法を示します。

たとえば、各行の最初の要素を基準にして行全体をソートする方法を考えます。

#include <iostream>
#include <algorithm> // std::sortを使用するために必要
// 行を比較するためのカスタム比較関数
bool customCompare(int a[], int b[]) {
    return a[0] < b[0]; // 最初の要素を基準に昇順で比較
}
int main() {
    // 3行4列の2次元配列を宣言
    int array[3][4] = {
        {3, 1, 4, 2},
        {8, 5, 6, 7},
        {0, 9, 3, 1}
    };
    // 行をソートするためのポインタ配列を作成
    int* rowPointers[3];
    for (int i = 0; i < 3; i++) {
        rowPointers[i] = array[i]; // 各行のポインタを格納
    }
    // カスタム比較関数を使用して行をソート
    std::sort(rowPointers, rowPointers + 3, customCompare);
    // ソート後の配列の要素を表示
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            std::cout << rowPointers[i][j] << " "; // 要素を表示
        }
        std::cout << std::endl; // 行の区切り
    }
    return 0;
}

0 9 3 1 
3 1 4 2 
8 5 6 7

このコードでは、3行4列の2次元配列を宣言し、各行のポインタを格納する配列を作成しています。

customCompare関数は、各行の最初の要素を基準にして行を比較します。

std::sortを使用して、カスタム比較関数を適用しながら行をソートしています。

ソート後、各行の要素を表示することで、正しくソートされたことを確認できます。

カスタムソートを実装することで、特定の条件に基づいた柔軟なデータの並び替えが可能になります。

次のセクションでは、動的配列std::vectorを用いたソートについて解説します。

動的配列(std::vector)を用いたソート

C++のstd::vectorは、動的にサイズを変更できる配列であり、2次元配列を扱う際にも非常に便利です。

std::vectorを使用することで、メモリ管理が容易になり、要素の追加や削除が簡単に行えます。

ここでは、std::vectorを用いて2次元配列をソートする方法を示します。

#include <iostream>
#include <vector>    // std::vectorを使用するために必要
#include <algorithm> // std::sortを使用するために必要
int main() {
    // 2次元ベクターを宣言
    std::vector<std::vector<int>> vec = {
        {3, 1, 4, 2},
        {8, 5, 6, 7},
        {0, 9, 3, 1}
    };
    // 各行をソート
    for (auto& row : vec) {
        std::sort(row.begin(), row.end()); // 行ごとにソート
    }
    // ソート後のベクターの要素を表示
    for (const auto& row : vec) {
        for (const auto& elem : row) {
            std::cout << elem << " "; // 要素を表示
        }
        std::cout << std::endl; // 行の区切り
    }
    return 0;
}