Pythonでわかる ~選択ソート~

## はじめに
こんにちは、鈴木です。データ構造とアルゴリズムの学習のアウトプットも兼ねて、誰かの役に立てばと思い、この記事を投稿するに至りました。ちなみに、言語はPythonを使います。ロジックのみに触れるため、計算量には触れません。（今後、計算量に関する記事は投稿していくつもりです）

今回は選択ソート(Selection Sort/Select Sort)について紹介したいと思います。

## 選択ソート(Selection Sort/Select Sort)とは
選択ソートとは端的に言えば、先頭の要素から変数に格納して、他の要素と大小比較する並べ替えの手法です。

これだけだと理解に苦しむと思うので、コードで見ていきましょう。

## コードで見る

```Python:selection_sort
def selection_sort(numbers: list[int]) -> list[int]:

    # 入力されたリストの長さを取得
    len_numbers = len(numbers)

    # 1. 変数を格納するインデックス番号を定めるループ
    for i in range(len_numbers):

        # 2. i番目(インデックス番号)をmin_idx(変数)に格納
        min_idx = i

        # 3-1. min_idxと比較するインデックス番号を定めるループ
        for j in range(i+1, len_numbers):

            # 4-1. numbers[min_idx] が numbers[j]よりも大きい場合
            if numbers[min_idx] > numbers[j]:

                # 4-2. 変数に格納するインデックス番号を変更
                min_idx = j

        # 3-2. 変数より、リストの値を更新する
        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]

    return numbers
```
それでは、具体例を見ていきましょう。
## 具体例
これは何の変哲もない長さが3のリストです。この要素が1, 2, 3と左から右へと昇順になっているように変更します。
```python:selection_sort
nums = [3, 2, 1]
```

リストの先頭、**3** のインデックス番号( **0** )を **min_idx** に格納します。
```python:selection_sort
# i = 0
# min_idx = 0
# numbers[min_idx] = 3
nums = [3, 2, 1]
#       ↑
#       i
#      *M
# *min_idx
```

**3**と**2** を比較します。
```python:selection_sort
# i = 0
# min_idx = 0
# numbers[min_idx] = 3
# j = 1
# numbers[j] = 2
nums = [3, 2, 1]
#       ↑  ↑
#       i  j
#      *M
# *min_idx
```

**3 > 2** であることから変数 **min_idx**の値を更新します。
```python:selection_sort
# i = 0
# min_idx = 1
# numbers[min_idx] = 2
# j = 1
# numbers[j] = 2
nums = [3, 2, 1]
#       ↑   ↑
#       i  *M
#           j
# *min_idx
```

**2**と**1**を比較します。
```python:selection_sort
# i = 0
# min_idx = 1
# numbers[min_idx] = 2
# j = 2
# numbers[j] = 1
nums = [3, 2, 1]
#       ↑  ↑  ↑
#       i *M  j
# *min_idx
```

**2 > 1** であることから変数 **min_idx** の値を更新します。
```python:selection_sort
# i = 0
# min_idx = 2
# numbers[min_idx] = 1
# j = 2
# numbers[j] = 1
nums = [3, 2, 1]
#       ↑     ↑
#       i    *M
#             j
# *min_idx
```

ここで**i= 0**のときの変数**min_idx**と他の要素との比較が完了しました。

そして、**比較した中で**最小の値のインデックス番号を**min_idx**に格納することができました。

それでは、**nums[i]**, **nums[min_idx]** の値を交換します。
```python:selection_sort
# i = 0 
# min_idx = 2
# numbers[min_idx] = 1
# j = 2
# numbers[j] = 1
nums = [1, 2, 3]
```
このように、**i**のループが一つ終わると**比較した中で**最小の値を持つ要素をリストの先頭に移動させることができました。選択ソートをこれを繰り返して並び替えを行っていきます。

これで、ソートが完了したように見えますが、まだ残っている処理が実行されます。

**2** のインデックス番号( **1** )を **min_idx** に格納します。
```python:selection_sort
# i = 1
# min_idx = 1
# numbers[min_idx] = 2
nums = [1, 2, 3]
#          ↑
#          i
#         *M
# *min_idx
```

**2**と**3** を比較します。
```python:selection_sort
# i = 1
# min_idx = 1
# numbers[min_idx] = 2
# j = 2
# numbers[j] = 3
nums = [3, 2, 1]
#          ↑  ↑
#          i  j
#         *M
# *min_idx
```
これは、if文の条件にあてはまらないので、何も処理が起きません。

そして、次に**i = 2**となりますが、このとき**3-1**において、**range(3, 3)** となるため、何も処理が起きません。

これでソートが完了します。

## 参考
[現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門](https://www.udemy.com/course/python-algo/?couponCode=ST11MT91624B)
動画を用いた視覚的な説明をしているため、とてもわかりやすいです。アルゴリズムを体系的に詳しく理解したい方はご購入をおすすめします。セール時だと、元の値段よりかなり安く購入できます。