選択ソート

選択ソートは、シンプルながら効率的とは言えないソートアルゴリズムの一つです。基本的な考え方と実装について説明します。

1. 選択ソートの仕組み

配列の中から最小値（または最大値）を見つける
その値を配列の先頭（または末尾）と交換する
ソート済みの部分を除いた残りの配列で、再び同じ処理を繰り返す

2. 特徴

時間計算量: O(n²) – どのような入力データでも常に同じ計算量
空間計算量: O(1) – 追加の記憶領域をほとんど必要としない（インプレース）
安定性: 安定ソートではない（同じ値の要素の相対的な順序が保存されない場合がある）

3. 実装例

以下に、Javaと疑似コードによる選択ソートの実装例を示します：

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // 配列を順番に走査
        for (int i = 0; i < n - 1; i++) {
            // 現在の位置から最小値のインデックスを見つける
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 見つけた最小値と現在の位置を交換
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
    
    // テスト用のメインメソッド
    public static void main(String[] args) {
        int[] array = {64, 25, 12, 22, 11};
        
        System.out.println("ソート前の配列:");
        for (int num : array) {
            System.out.print(num + " ");
        }
        
        selectionSort(array);
        
        System.out.println("\n\nソート後の配列:");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

4. アルゴリズムの詳細な動作

配列 [64, 25, 12, 22, 11] をソートする例で考えてみましょう：

最初のパス：
- 配列全体から最小値 11 を見つける
- 11 と最初の要素 64 を交換
- 配列は [11, 25, 12, 22, 64] になる
2番目のパス：
- 残りの部分 [25, 12, 22, 64] から最小値 12 を見つける
- 12 と 25 を交換
- 配列は [11, 12, 25, 22, 64] になる
3番目のパス：
- 残りの部分 [25, 22, 64] から最小値 22 を見つける
- 22 と 25 を交換
- 配列は [11, 12, 22, 25, 64] になる
4番目のパス：
- 残りの部分 [25, 64] から最小値 25 を見つける
- 25 はすでに正しい位置にあるので交換しない
- 配列は [11, 12, 22, 25, 64] のまま

これで配列はソートされました。

5. 選択ソートの利点と欠点

5.1. 利点

実装がシンプル
メモリ使用量が少ない（インプレース）
交換回数が少ない（最大でも n-1 回）

5.2. 欠点

時間計算量が O(n²) と効率が悪い
大きなデータセットでは非効率
安定ソートではない

6. 他のソートアルゴリズムとの比較

バブルソート: 隣接する要素を比較・交換するため、交換回数が多い
挿入ソート: 部分的にソート済みの配列に対して効率的
クイックソート: 平均的に O(n log n) と高速だが、最悪の場合 O(n²)
マージソート: 常に O(n log n) で安定だが、追加のメモリを必要とする

選択ソートは教育用や小さな配列に対しては適していますが、実用的なアプリケーションでは通常、より効率的なアルゴリズム（クイックソートやマージソートなど）が使用されます。