選択ソート - データサイエンス関連+αのメモ

選択ソート（selection sort） は未ソート部分から最小値を選んで先頭と交換する操作を繰り返すソートアルゴリズム。バブルソートの改良版。

	計算量
最悪時間計算量	$O(n^2)$
平均時間計算量	$O(n^2)$
最良時間計算量	$O(n^2)$
空間計算量	$O(1)$ （in-place）

特徴

非安定ソート（同じ値の相対順序が崩れる場合がある）
in-place
交換回数が最大でも $n-1$ 回と少ない（書き込みコストが高いメモリで有利）

アルゴリズム¶

未ソート部分 arr[i:] の最小値のインデックスを探す
最小値を arr[i] と交換する
i を進めて繰り返す

def selection_sort(arr: list) -> list:
    a = arr.copy()
    n = len(a)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]
    return a

import random

data = [64, 25, 12, 22, 11]
print("入力:", data)
print("出力:", selection_sort(data))

random.seed(0)
large = random.sample(range(1000), 20)
assert selection_sort(large) == sorted(large)
print("ランダム20件: OK")

入力: [64, 25, 12, 22, 11]
出力: [11, 12, 22, 25, 64]
ランダム20件: OK

ステップ可視化¶

def selection_sort_verbose(arr: list) -> list:
    a = arr.copy()
    n = len(a)
    for i in range(n - 1):
        min_idx = min(range(i, n), key=lambda j: a[j])
        a[i], a[min_idx] = a[min_idx], a[i]
        print(f"i={i}: 最小={a[i]} → {a}")
    return a

data = [5, 3, 8, 1, 4]
print("入力:", data)
selection_sort_verbose(data)

入力: [5, 3, 8, 1, 4]
i=0: 最小=1 → [1, 3, 8, 5, 4]
i=1: 最小=3 → [1, 3, 8, 5, 4]
i=2: 最小=4 → [1, 3, 4, 5, 8]
i=3: 最小=5 → [1, 3, 4, 5, 8]

[1, 3, 4, 5, 8]