【解説】 選択ソート
アルゴリズムの仕組み
考え方は非常にシンプルで、**「まだ並び替えていない部分から一番小さいものを探し、左に詰めていく」**という流れです。
-
リスト全体の中から、最小値を探します。
-
見つかった最小値と、未整列部分の先頭の要素を入れ替えます。
-
「最小値が確定した部分」を一つ右へ進め、残りの部分で再び最小値を探します。
-
これを未整列の要素がなくなるまで繰り返します。
特徴と性能
バブルソートと同様に、仕組みは簡単ですが、データの量が増えると時間がかかるタイプです。
-
時間計算量: O(n^2)
-
どんなデータ状態（既に整列されていても、逆順でも）であっても、必ず最後まで比較を行うため、常にこの時間がかかります。
-
-
空間計算量: O(1)
-
安定性: 不安定なソート
-
離れた場所にある要素同士を入れ替えるため、同じ値の要素の前後関係が崩れる可能性があります。
-
# 選択ソートのコード
def selection_sort(arr):
n = len(arr)
for i in range:
# 未整列部分の先頭を暫定の最小値とする
min_idx = i
# 残りの要素から最小値を探す
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 見つかった最小値を先頭（i番目）と入れ替える
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 使用例
data = [29, 10, 14, 37, 13]
sorted_data = selection_sort(data)
print(f"ソート後: {sorted_data}")