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 個の整数が与えられる。それらをバブルソートで昇順に並べ替えよ。

参考： ABC333 B - Basic Bubble Sort

回答　

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 個の整数が与えられる。それらを選択ソートで昇順に並べ替えよ。

参考： ABC321 B - Selection Sort

回答　

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 個の整数が与えられる。それらを選択ソートで並べ替える際の「交換回数」を出力せよ。

参考： ABC314 D - Selection Swap Count

回答　

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 個の整数が与えられる。それらを選択ソートで降順（大きい順）に並べ替えよ。

参考： ABC303 B - Reverse Selection Sort

回答　

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 回だけ適用した時点の配列を出力せよ。

参考： ABC317 C - Partial Selection Sort

回答　

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 番目の要素を出力せよ。

参考： ABC316 B - Find K-th Element

回答　

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])