【C++】選択ソートのアルゴリズムと実装コードをわかりやすく解説

選択ソート（Selection Sort）は、シンプルで理解しやすいソートアルゴリズムの一つです。この手法では、リストを「ソート済みの部分」と「未ソートの部分」の2つの領域に分けて扱います。

まず、未ソートの領域から最大値（または最小値）を探し出します。ここでは最小値を基準に説明します。最小値が見つかったら、未ソート部分の先頭にあるデータと入れ替えることで、その値をリストの先頭へ移動します。この処理を1回行うごとにソート済みの領域が1つずつ拡大していき、最終的にリスト全体が昇順に並べ替えられます。

選択ソートの計算量

• 時間計算量：O(n²)

• 空間計算量：O(1)

選択ソートは追加のメモリをほとんど必要としない一方で、要素数が増えると比較回数が要素数の2乗に比例して増加するため、大規模なデータには不向きです。また、同じ値の相対的な順序が保持されない「非安定ソート」である点にも注意が必要です。

入力 − ソートされていないリスト: 5 9 7 23 78 20
出力 − ソート後の配列: 5 7 9 20 23 78

アルゴリズム

selectionSort(array, size)

入力：データの配列と、配列内の要素の総数

出力：ソート済みの配列

Begin
    for i := 0 to size-2 do //i番目以降の範囲から最小値を探す
        iMin := i;
        for j := i+1 to size-1 do
            if array[j] < array[iMin] then
                iMin := j
        done
        array[i] と array[iMin] を入れ替える
    done
End

C++による実装例

#include<iostream>
using namespace std;
void swapping(int &a, int &b) {          //aとbの内容を入れ替える
    int temp;
    temp = a;
    a = b;
    b = temp;
}
void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}
void selectionSort(int *array, int size) {
    int i, j, imin;
    for(i = 0; i<size-1; i++) {
        imin = i;   //最小値のインデックスを取得
        for(j = i+1; j<size; j++)
            if(array[j] < array[imin])
                imin = j;
            //最小値を正しい位置へ配置
            swap(array[i], array[imin]);
    }
}
int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];   //指定された要素数で配列を作成
    cout << "Enter elements:" << endl;
    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    selectionSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

このプログラムでは、まず要素数と各要素の値を入力として受け取り、ソート前の配列を表示します。その後、selectionSort()関数で選択ソートを実行し、ソート後の配列を出力します。

実行結果

Enter the number of elements: 6
Enter elements:
5 9 7 23 78 20
Array before Sorting: 5 9 7 23 78 20
Array after Sorting: 5 7 9 20 23 78