C++で配列を並べ替える方法｜選択ソートの仕組みと実装例を解説

C++では、さまざまなソート（並べ替え）アルゴリズムを使って配列を整列できます。ソート済みの配列とは、数値の大小順やアルファベット順など、何らかの基準に従って要素が並び替えられた配列のことです。代表的なソートアルゴリズムには、バブルソート、挿入ソート、選択ソート、マージソート、クイックソート、ヒープソートなどがあります。
本記事では、その中でも構造がシンプルで理解しやすい「選択ソート」を取り上げ、実際のコード例とともに詳しく解説していきます。

選択ソートとは？

選択ソートは、未ソート部分の中から最小値を繰り返し探し出し、それを未ソート部分の先頭にある要素と交換することで、配列全体を昇順に整列させていくソート手法です。

選択ソートのサンプルコード

以下は、C++で選択ソートを実装して配列を並べ替えるプログラムの例です。

#include<iostream>
using namespace std;

void selectionSort(int a[], int n) {
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

int main() {
    int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
    int n = sizeof(a)/ sizeof(a[0]);
    int i;
    cout << "ソート前の配列:" << endl;
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    selectionSort(a, n);
    cout << "\nソート後の配列:" << endl;
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

実行結果

ソート前の配列:
22 91 35 78 10 8 75 99 1 67

ソート後の配列:
1 8 10 22 35 67 75 78 91 99

コードの解説

selectionSort() 関数の動作

上記プログラムでは、selectionSort() 関数が選択ソートによって配列 a[] を並べ替えています。関数内には2つのforループがあり、外側のループの各反復処理において、インデックス i 以降に残っている要素の中から最小値を探し、現在 i の位置にある要素と交換します。この操作を配列全体が整列するまで繰り返すのが、選択ソートの基本的な流れです。

void selectionSort(int a[], int n) {
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++) {
        min = i;                      // 最小値の位置を仮に設定
        for (j = i + 1; j < n; j++)   // 未ソート部分を走査
            if (a[j] < a[min])
                min = j;              // より小さい値があれば位置を更新
        temp = a[i];                  // 最小値と先頭要素を交換
        a[i] = a[min];
        a[min] = temp;
    }
}

main() 関数の動作

main() 関数では、まず配列 a[] を定義し、sizeof演算子を使ってその要素数 n を求めています。続いて、配列 a[] とサイズ n を引数として selectionSort() 関数を呼び出し、並べ替えが完了した配列を画面に出力します。

int main() {
    int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
    int n = sizeof(a)/ sizeof(a[0]);
    int i;
    cout << "ソート前の配列:" << endl;
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    selectionSort(a, n);
    cout << "\nソート後の配列:" << endl;
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

選択ソートの計算量

選択ソートの時間計算量は、入力データの初期状態にかかわらず常に O(n²) です。これは、外側のループが n−1 回、内側のループが平均して約 n/2 回実行されるためです。一方で、要素の交換回数は最大でも n−1 回と少なく、追加のメモリをほとんど必要としないという特長があります。小規模なデータの整列には手軽で有用ですが、大量のデータを扱う場合には、O(n log n) で動作するクイックソートやマージソートなどのアルゴリズムを選ぶ方が効率的です。