《アルゴリズムを学ぶ》5.選択ソート

# Overview
選択ソート（Selection Sort）は、リストの最小（または最大）の要素を選び、順番に並べていく基本的なソートアルゴリズム。バブルソートよりは効率的。
[1.選択ソートの基本](#1-選択ソートの基本)
[2.選択ソートの改良](#2-選択ソートの改良)
[3.選択ソートの特徴](#3-選択ソートの特徴)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. 選択ソートの基本
数列の中から最小値を検索し、左端の数字と入れ替える操作を繰り返す。数列の中から最小値を探す際は、線形探索を行っている。

**＜アルゴリズムの流れ＞**
1.未ソート部分の中から線形探索し、最小値を探す
2.その最小値を先頭の要素と交換
3.次の未ソート部分で同じ操作を繰り返す
4.最後まで繰り返し、リストをソート


**＜基本実装＞**
```python
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
```
実行例
```Python
arr = [5, 3, 8, 4, 2]
print(selection_sort(arr))  # 出力: [2, 3, 4, 5, 8]
```

**＜降順の選択ソート＞**
```python
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. 選択ソートの改良
**＜二方向選択ソート>**
通常の選択ソートでは、最小値のみを見つけて前に移動するが、最小値と最大値を同時に選択することで、ループ回数を半減できる。

```python
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](https://atcoder.jp/contests/abc333/tasks/abc333_b)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題1. 選択ソートの基本
**問題: N 個の整数が与えられる。それらを選択ソートで昇順に並べ替えよ。**
> [参考： ABC321 B - Selection Sort](https://atcoder.jp/contests/abc321/tasks/abc321_b)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題2. 選択ソートの交換回数
**問題: N 個の整数が与えられる。それらを選択ソートで並べ替える際の「交換回数」を出力せよ。**
> [参考： ABC314 D - Selection Swap Count](https://atcoder.jp/contests/abc314/tasks/abc314_d)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題3. 降順の選択ソート
**問題: N 個の整数が与えられる。それらを選択ソートで降順（大きい順）に並べ替えよ。**
> [参考： ABC303 B - Reverse Selection Sort](https://atcoder.jp/contests/abc303/tasks/abc303_b)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題4. K 回だけ選択ソートを適用
**問題: N 個の整数が与えられ、選択ソートを K 回だけ適用した時点の配列を出力せよ。**
> [参考： ABC317 C - Partial Selection Sort](https://atcoder.jp/contests/abc317/tasks/abc317_c)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題5. 選択ソート後の k 番目の要素を出力
**問題: N 個の整数が与えられ、それを選択ソートした後、K 番目の要素を出力せよ。**
> [参考： ABC316 B - Find K-th Element](https://atcoder.jp/contests/abc316/tasks/abc316_b)
<details><summary> 回答　</summary>

```python
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])
```
</details>