概要

多分他に記事は山程ありそうなので、自分自身の辞書代わり程度に記載します！

競技プログラミングに興味が前からありますが、
最近Pythonに移行したので基礎からやってますー

選択ソートとは？

要素を順番に確認し、最小値 or 最大値の要素を見つけたら
その要素を先頭から順に並び替えます。

所謂ソートアルゴリズムってやつですな。

計算量

常にリスト全体の中から最小（または最大）の要素を探すため、
リストの長さが「𝑛」の場合、比較の回数は 𝑂(𝑛2乗)になります。

リストがほとんどソート済みでも時間計算量は変わりません。

特徴

メリット
・実装が簡単(理解しやすい!)
・メモリ使用量少

デメリット
・比較回数が多いため、効率が悪く、リストが大きいと処理が遅い

例

手順を簡単な例でイメージしてみよう！

次のリスト [29, 10, 14, 37, 13] を昇順にソートしてみましょう！

1. 最小値を探そう

[29, 10, 14, 37, 13] から最小値を探します。
最小値は 10 です。これを先頭の 29 と交換します。

result.py

[10, 29, 14, 37, 13]

2. 次の最小値を探そう

残りのリスト [29, 14, 37, 13] の中から最小値を探します。
最小値は 13 です。これを 29 と交換します。

result.py

[10, 13, 14, 37, 29]

3. 同様に残りのリスト要素から最小値を探そう！

残りのリスト [14, 37, 29] の中で最小値を探します。
最小値は 14 ですね！

今回の場合はすでに正しい位置にあるため、交換は不要になります。

result.py

[10, 13, 14, 37, 29]

4. 残りは？

最後に、残りのリスト [37, 29] の中で最小値 29 を探し、37 が交換です。

result.py

[10, 13, 14, 29, 37]

ソート完了！

実装してみよう！

selection.py

from typing import List
import random

def selection_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(len_numbers):
        # 一時的に最初の要素を保持
        min_index = i
        for j in range(i + 1, len_numbers): # 対象の要素はズレるので+1する
            if numbers[min_index] > numbers[j]:
                # 最小値が見つかったら、indexを入れ替える
                min_index = j

        numbers[i], numbers[min_index] = numbers[min_index], numbers[i]

    return numbers


if __name__ == '__main__':
    # 好きな配列を用意しても、適当な乱数配列でもよし！
    nums = [random.randint(0, 100) for _ in range(10)]
    print(selection_sort(nums))

結果例

result.py

[9, 15, 25, 35, 58, 59, 73, 74, 83, 90]

Process finished with exit code 0

最後に

お疲れ様でした！
他にも似たような記事はありますが、私自身Pythonで競技プログラミングを
今後頑張っていこうと思うので他アルゴリズムも解説しようかと思います！

参考文献