Elegant Access

今日のトピック (Today's Topic)

トピック: Selection Sort
難易度: beginner
カテゴリー: Sorting Algorithms
時間計算量: O(n^2)
空間計算量: O(1)

概念学習 (Concept Learning)

核心概念

選択ソート（Selection Sort） は、入力配列を2つの部分に分割するシンプルな比較ベースのソートアルゴリズムです：最初のソート済み部分と最後の未ソート部分です。このアルゴリズムは、未ソート部分から最小（または最大）の要素を繰り返し選択し、ソート済み部分の末尾に移動します。

「選択ソート」という名前は、未ソート部分から最小要素を繰り返し選択することに由来します。隣接する要素を交換するバブルソートとは異なり、選択ソートは交換回数が少なく（最悪の場合でもちょうどn-1回の交換）、常にO(n²)の比較が必要です。

重要ポイント

インプレースソート: O(1)の追加メモリ空間のみが必要
安定ではない: 等しい要素の相対順序が保持されない場合がある（修正により安定化可能）
最小交換回数: 最大でもn-1回の交換を実行（交換ベースのアルゴリズムとして最適）
適応的ではない: 部分的にソート済みのデータでもパフォーマンスは向上しない
パフォーマンスが悪い: すべてのケース（最良、平均、最悪）でO(n²)の時間計算量
シンプルな論理: 理解と実装が容易

アルゴリズムステップ

初期化: 最初の位置をソート済み部分と未ソート部分の境界として開始
最小値を見つける: 未ソート部分全体をスキャンして最小要素を見つける
交換: 見つけた最小要素を未ソート部分の最初の要素と交換
境界を移動: 境界を1つ右に移動し、ソート済み部分を拡大
繰り返し: ステップ2-4を配列全体がソートされるまで続ける
完了: 未ソート部分に1つの要素のみが残ったら、配列はソート済み

実装 (Implementation)

JavaScript実装

function selectionSort(arr) {
    const n = arr.length;
    
    // 外側のループ：未ソート部分の境界を移動
    for (let i = 0; i < n - 1; i++) {
        // 未ソート部分の最小要素を見つける
        let minIndex = i;
        
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 見つけた最小要素を最初の未ソート要素と交換
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    
    return arr;
}

// 使用例
const array = [64, 25, 12, 22, 11];
console.log("元の配列:", array);
console.log("ソート後:", selectionSort([...array]));
// 出力: ソート後: [11, 12, 22, 25, 64]

Python実装

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n - 1):
        # 残りの未ソート配列から最小要素を見つける
        min_index = i
        
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # 見つけた最小値を最初の要素と交換
        arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr

# 使用例
array = [64, 25, 12, 22, 11]
print("元の配列:", array)
print("ソート後:", selection_sort(array.copy()))
# 出力: ソート後: [11, 12, 22, 25, 64]

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;
                }
            }
            
            // 見つけた最小要素を最初の要素と交換
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    
    public static void main(String[] args) {
        int[] array = {64, 25, 12, 22, 11};
        System.out.println("元の配列: " + Arrays.toString(array));
        selectionSort(array);
        System.out.println("ソート後: " + Arrays.toString(array));
        // 出力: ソート後: [11, 12, 22, 25, 64]
    }
}

計算量分析

時間計算量：

最良ケース: O(n²) - 配列がソート済みでも、すべての要素をチェックする
平均ケース: O(n²) - 典型的なパフォーマンス
最悪ケース: O(n²) - 逆順にソートされた配列
比較回数: 常に (n-1) + (n-2) + ... + 1 = n(n-1)/2 回の比較

空間計算量：

O(1): 変数のための定数量の追加空間のみを使用

交換回数：

最大n-1回の交換: バブルソートのO(n²)回の交換よりもはるかに優れている

ステップバイステップの例

[64, 25, 12, 22, 11] のソート過程を追跡してみましょう：

初期状態: [64, 25, 12, 22, 11]
          ↑ ここから開始

パス1: [64, 25, 12, 22, 11] の中から最小値を探す
       最小値は11（インデックス4）
       交換: [11, 25, 12, 22, 64]
             ↑↑ ソート済み

パス2: [25, 12, 22, 64] の中から最小値を探す
       最小値は12（インデックス2）
       交換: [11, 12, 25, 22, 64]
             ↑↑↑↑ ソート済み

パス3: [25, 22, 64] の中から最小値を探す
       最小値は22（インデックス3）
       交換: [11, 12, 22, 25, 64]
             ↑↑↑↑↑↑ ソート済み

パス4: [25, 64] の中から最小値を探す
       最小値は25（すでに正しい位置）
       交換なし: [11, 12, 22, 25, 64]
                ↑↑↑↑↑↑↑↑ ソート済み

結果: [11, 12, 22, 25, 64]

練習問題 (Practice Problems)

問題リスト

Sort Colors (LeetCode 75) - 選択ソートの概念を使用
Kth Smallest Element - 部分的な選択ソートを適用
Find K Closest Elements - 変更された選択ソートアプローチ

解法ノート

選択ソートを使用するとき：

小規模データセット（n < 20）
メモリ書き込みがコストが高い（交換を最小化）
シンプルな実装が必要
配列がソート済みかチェックする

使用すべきでないとき：

大規模データセット（クイックソート、マージソート、ヒープソートを使用）
安定したソートが必要（バブルソートまたは挿入ソートを使用）
適応的アルゴリズムが必要（挿入ソートを使用）

重要な詳細 (Important Details)

注意すべきエッジケース

空の配列 [] → 空の配列を返す
単一要素 [1] → すでにソート済み
2つの要素 [2, 1] → 1回の交換が必要
すべて同じ要素 [5, 5, 5] → 交換は不要
すでにソート済み [1, 2, 3] → それでもO(n²)時間

利点

✅ 理解と実装が簡単
✅ 小規模リストでパフォーマンスが良い
✅ 交換回数を最小化（書き込み操作が高価な場合に適している）
✅ インプレースソート（O(1)空間）
✅ 追加のメモリ割り当てが不要

欠点

❌ すべてのケースでO(n²)の時間計算量
❌ 適応的ではない（部分的にソート済みのデータの恩恵を受けない）
❌ 安定ではない（等しい要素の相対順序が変わる可能性がある）
❌ 大規模データセットでパフォーマンスが悪い
❌ 平均して挿入ソートよりも多くの比較

他のソートとの比較

アルゴリズム	時間（最良）	時間（平均）	時間（最悪）	空間	安定性
選択ソート	O(n²)	O(n²)	O(n²)	O(1)	❌
バブルソート	O(n)	O(n²)	O(n²)	O(1)	✅
挿入ソート	O(n)	O(n²)	O(n²)	O(1)	✅
クイックソート	O(n log n)	O(n log n)	O(n²)	O(log n)	❌
マージソート	O(n log n)	O(n log n)	O(n log n)	O(n)	✅

今日の振り返り (Daily Reflection)

関連アルゴリズム:

バブルソート: 同様のO(n²)計算量だが交換回数が多い
挿入ソート: 部分的にソート済みのデータに対してより優れている
ヒープソート: ヒープ構造を使用した類似の選択概念（O(n log n)）
クイックソート: 大規模データセット向けのより良い分割統治アプローチ

アルゴリズム日記

アルゴリズム日記 - Selection Sort