選択ソートは、未ソート部分の中で最小（または最大）の要素を探して、それを順番に並べる ソートアルゴリズムです。
配列を部分的にソート済みの部分と未ソートの部分に分け、未ソートの中から最小の要素を選び、ソート済み部分の末尾と交換していくのが特徴です。

1. リストの中で最小の要素を探す。
2. その最小要素をリストの先頭（ソート済み部分の末尾）と交換する。
3. 未ソート部分を1つ減らし、未ソート部分で最小の要素を探して交換する。
4. これをリストの全要素に対して繰り返す。

SelectionSort(A, n)
  for i = 0 to n-1 do
    min_index = i
    for j = i+1 to n-1 do
      if A[j] < A[min_index] then
        min_index = j
    swap(A[i], A[min_index])

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        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

# 実行例
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr)  # [11, 12, 22, 25, 64]

このコードでは、毎回未ソート部分の最小値を探して、ソート済み部分の末尾と交換 することでリストを整列させています。

• 全体で (n) 回の走査を行う（最小値を探すためのループ）
• 各走査で残りの (n-1), (n-2), ..., (1) 要素を比較する
• これを合計すると、(O(n^2)) となる

✅ 実装が簡単（初心者でも理解しやすい）
✅ 追加のメモリをほとんど使わない（in-place ソート）
✅ 安定した動作（ループ回数が固定で、他の条件に影響されない）

❌ 処理が遅い（バブルソートと同じく (O(n^2)) で、効率が悪い）
❌ 安定ソートではない（同じ値の順序が保持されない）
❌ データがすでにソートされていても (O(n^2)) の時間がかかる

選択ソートは交換回数が少ない（最大 (O(n)) 回）ため、交換コストが高い場合にはバブルソートよりも有利です。

選択ソートを高速化するための方法の1つとして、ヒープソート（Heap Sort） があります。

• 選択ソートでは、最小値を探すために (O(n)) の時間がかかる
• ヒープ（Heap）を使うと、最小値の取得が (O(\log n)) になる
• その結果、選択ソートの (O(n^2)) が (O(n \log n)) に改善される

Pythonでのヒープソート

import heapq

def heap_sort(arr):
    heapq.heapify(arr)  # リストをヒープに変換（O(n)）
    return [heapq.heappop(arr) for _ in range(len(arr))]  # 最小値を順番に取り出す（O(n log n)）

# 実行例
arr = [64, 25, 12, 22, 11]
sorted_arr = heap_sort(arr)
print(sorted_arr)  # [11, 12, 22, 25, 64]

このように、ヒープを使うと選択ソートを高速化できます。

✅ 小規模データのソート（100個以下）
✅ メモリをほとんど使わずにソートしたい場合（追加メモリ不要）
✅ 書き込みコストが高い環境（フラッシュメモリなどでは書き換え回数が少ない方が良い）
❌ 大量データのソートには向かない（クイックソートやマージソートを使うべき）

• 選択ソートは、未ソート部分から最小値を選んで順番に並べるアルゴリズム。
• 時間計算量は (O(n^2)) で、バブルソートと同じくらい遅い。
• 交換回数が少ないため、書き換えコストが高い環境ではバブルソートより有利。
• 実用的には、クイックソートやヒープソートを使う方が高速。