Overview
選択ソート（Selection Sort）は、リストの最小（または最大）の要素を選び、順番に並べていく基本的なソートアルゴリズム。バブルソートよりは効率的。
1.選択ソートの基本
2.選択ソートの改良
3.選択ソートの特徴
4.典型問題を解いてみる
1. 選択ソートの基本
数列の中から最小値を検索し、左端の数字と入れ替える操作を繰り返す。数列の中から最小値を探す際は、線形探索を行っている。
＜アルゴリズムの流れ＞
1.未ソート部分の中から線形探索し、最小値を探す
2.その最小値を先頭の要素と交換
3.次の未ソート部分で同じ操作を繰り返す
4.最後まで繰り返し、リストをソート
＜基本実装＞
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 = [5, 3, 8, 4, 2]
print(selection_sort(arr)) # 出力: [2, 3, 4, 5, 8]
＜降順の選択ソート＞
def selection_sort_desc(arr):
n = len(arr)
for i in range(n):
max_index = i
for j in range(i + 1, n):
if arr[j] > arr[max_index]: # 最大値を探す
max_index = j
arr[i], arr[max_index] = arr[max_index], arr[i]
return arr
2. 選択ソートの改良
＜二方向選択ソート>
通常の選択ソートでは、最小値のみを見つけて前に移動するが、最小値と最大値を同時に選択することで、ループ回数を半減できる。
def bidirectional_selection_sort(arr):
n = len(arr)
for i in range(n // 2):
min_index = i
max_index = i
for j in range(i, n - i):
if arr[j] < arr[min_index]:
min_index = j
if arr[j] > arr[max_index]:
max_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
if max_index == i: # 交換した場合は max_index を更新
max_index = min_index
arr[n - 1 - i], arr[max_index] = arr[max_index], arr[n - 1 - i]
return arr
3. 選択ソートの特徴
時間計算量 : 最悪・平均・最良: $O(N^2)$
空間計算量 : $O(1)$ (追加メモリ不要）
安定ソート : No（同じ値の順番が入れ替わる）
交換回数 : 最大$N-1$回（バブルソートより少ない）
有効な場面 : メモリ制約が厳しい環境、データの移動回数を抑えたい場合
4. 典型問題を解いてみる
例題1. バブルソートの基本実装
問題: N 個の整数が与えられる。それらをバブルソートで昇順に並べ替えよ。
回答
N = int(input())
A = list(map(int, input().split()))
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(*bubble_sort(A))
例題1. 選択ソートの基本
問題: N 個の整数が与えられる。それらを選択ソートで昇順に並べ替えよ。
回答
N = int(input())
A = list(map(int, input().split()))
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
print(*selection_sort(A))
例題2. 選択ソートの交換回数
問題: N 個の整数が与えられる。それらを選択ソートで並べ替える際の「交換回数」を出力せよ。
回答
N = int(input())
A = list(map(int, input().split()))
def selection_sort_count(arr):
n = len(arr)
swap_count = 0
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
swap_count += 1
return swap_count
print(selection_sort_count(A))
例題3. 降順の選択ソート
問題: N 個の整数が与えられる。それらを選択ソートで降順（大きい順）に並べ替えよ。
回答
N = int(input())
A = list(map(int, input().split()))
def selection_sort_desc(arr):
n = len(arr)
for i in range(n):
max_index = i
for j in range(i + 1, n):
if arr[j] > arr[max_index]: # 最大値を探す
max_index = j
arr[i], arr[max_index] = arr[max_index], arr[i]
return arr
print(*selection_sort_desc(A))
例題4. K 回だけ選択ソートを適用
問題: N 個の整数が与えられ、選択ソートを K 回だけ適用した時点の配列を出力せよ。
回答
N, K = map(int, input().split())
A = list(map(int, input().split()))
def partial_selection_sort(arr, k):
n = len(arr)
for i in range(min(k, n)): # 最大K回までループ
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
print(*partial_selection_sort(A, K))
例題5. 選択ソート後の k 番目の要素を出力
問題: N 個の整数が与えられ、それを選択ソートした後、K 番目の要素を出力せよ。
回答
N, K = map(int, input().split())
A = list(map(int, input().split()))
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
sorted_A = selection_sort(A)
print(sorted_A[K-1])