選択ソート（Selection Sort）とは？仕組み・計算量・C++実装例を徹底解説

選択ソート（Selection Sort）は、リストを「整列済みの部分」と「未整列の部分」の2つに分けて処理するシンプルなソートアルゴリズムです。まず配列の中から最大値または最小値を探し出します。ここでは最小値を取り上げると、見つけた最小値を先頭の要素と入れ替えることで、リストの先頭に配置します。

この操作を1回行うごとに、整列済みの部分が1つずつ増え、未整列の部分は徐々に小さくなっていきます。これを繰り返すことで、最終的に配列全体が昇順（または降順）に並び替えられます。

選択ソートの計算量

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

データ数nに対して比較を繰り返すため、時間計算量はO(n²)となります。一方、入れ替えはその場で行うため、追加のメモリは不要で、空間計算量はO(1)です。選択ソートは交換回数が少ないという特徴があり、単純なアルゴリズムながら実装も容易です。

入力と出力の例

入力：
未ソートのリスト：5 9 7 23 78 20

出力：
ソート前の配列：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
      swap array[i] with array[iMin]. // 最小値をi番目と交換
   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);
}

実行結果

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

このプログラムでは、まずユーザーから要素数と各要素の値を入力として受け取ります。その後、selectionSort関数が未整列部分から毎回最小値を選んで先頭側へ移動させることで、配列全体を昇順に並べ替えます。実行結果から、ソート前にバラバラだった配列が正しく整列されていることが確認できます。