一、アルゴリズムの基本手順
- 初期化：配列を整列済み領域（空）と未整列領域（全要素）に分割
- 最小値検出：未整列領域内で最小値の位置を探索
- 交換処理：検出された最小値と未整列領域の先頭要素を交換
- 範囲更新：整列済み領域を1要素拡大、未整列領域を1要素縮小
- 繰り返し：未整列領域が1要素になるまで手順2～4を実行
二、C++実装例
#include <iostream>
using namespace std;
void sortSelection(int array[], int length) {
for (int boundary = 0; boundary < length - 1; boundary++) {
int candidate = boundary;
for (int probe = boundary + 1; probe < length; probe++) {
if (array[probe] < array[candidate]) {
candidate = probe;
}
}
swap(array[boundary], array[candidate]);
}
}
int main() {
int array[] = {5, 3, 1, 4, 2};
int length = sizeof(array) / sizeof(array[0]);
sortSelection(array, length);
cout << "Sorted array: ";
for (int i = 0; i < length; i++) {
cout << array[i] << " ";
}
return 0;
}
コードのポイント：
| コード | 説明 |
|---|---|
| for (int boundary = 0; boundary < length - 1; boundary++) | 整列済み領域の終端を管理し、各反復で1要素追加 |
| int candidate = boundary | 未整列領域の先頭を仮の最小値として初期化 |
| probe = boundary + 1 | 整列済み領域を無視し、未整列領域のみを探索 |
| swap(array[boundary], array[candidate]) | 最小要素を未整列領域の先頭と交換し、整列を1段階進める |
三、性能分析
| 特性 | 説明 |
|---|---|
| **時間計算量** | O(n²)（データの順序に関わらず全要素を比較） |
| **空間計算量** | O(1)（追加メモリを必要としないインプレース処理） |
| **安定性** | 不安定（同一値の要素の相対位置が変化する可能性あり） |
| **最適な利用ケース** | 小規模データ処理 / 交換回数を最小限に抑えたい場合 |
四、動作の可視化
初期状態：|5 3 1 4 2
1回目： 1 |3 5 4 2
2回目： 1 2 |5 4 3
3回目： 1 2 3 |4 5
4回目： 1 2 3 4 |5
五、改善方向
- 最大最小同時探索：1回の走査で最小値と最大値を同時に検出
- 再帰実装：残りの未整列領域を再帰的に処理
- 並列化対応：整列状態をチェックし、不要な処理を省略